積が平方数になる部分集合の数を媒介変数の数から求める

【例題１】 連続した正の整数の集合 {5,6,7,8,9,10,11}の部分集合でその要素の積が平方数になるものの数を求めよ

まずこれらの数を素因数分解して現れた素数との関係を表にします。

	5	6	7	8	9	10	11
2	0	1	0	3	0	1	0
3	0	1	0	0	2	0	0
5	1	0	0	0	0	1	0
7	0	0	1	0	0	0	0
11	0	0	0	0	0	0	1

各々の数が部分集合に含まれるかどうかを2値変数$n_5, n_6, n_7, n_8, n_9, n_{10},n_{11}$で表します。計算を$\pmod 2$で考えると、平方数になるということは部分集合に含まれるすべての素因数が偶数乗すなわち$0 \pmod 2$になるような$n_x$の組み合わせを求めるという問題になります（式（１））。
$\pmod 2$で考えるので行列の要素は$(0,1)$に変更してあります。

\begin{pmatrix} 
0&1&0&1&0&1&0 \\ 
0&1&0&0&0&0&0 \\ 
1&0&0&0&0&1&0 \\ 
0&0&1&0&0&0&0 \\ 
0&0&0&0&0&0&1 \\ 
\end{pmatrix}
\begin{pmatrix} 
n_5 \\ n_6 \\ n_7 \\ n_8 \\ n_9 \\ n_{10} \\ n_{11} \\ 
\end{pmatrix}
= 
\begin{pmatrix} 
0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 
\end{pmatrix}
\ \ \ \ \large \dots 式(１)

これを手計算で解くと、

n_6 = n_7 = n_{11} = 0 \\
n_5 + n_{10} = n_8 + n_{10} = 0
となり、\\
 n_9 = s_1 , n_{10} = s_2　と置くと\\
n_5 = n_8 = s_2 となり 

2つの媒介変数 $s_1, s_2$を使ってすべての変数が表されます。
$s_1, s_2$が$(0,1)$をとる組み合わせは以下の4通りなので空集合を除くと答えは3個となります。

$s_1$	$s_2$	積が平方数になる部分集合
0	0	ー
0	1	$\lbrace 5,8,10 \rbrace$
1	0	$\lbrace 9 \rbrace$
1	1	$\lbrace 5,8,9,10 \rbrace$

今回は手計算で解きましたが式（１）を見ると行列が$5 \times 7$なので媒介変数の数=$7-5=2$が分かれば$2^2-1=3$という答えを出すことが出来ますね。この考え方を利用して一般化を行います。

【例題２】 連続した正の整の集合 $\lbrace k,k+1, \dots, k+n \rbrace$の部分集合でそのその要素の積が平方数になるものの数を求めよ

この場合、列=$n+1$で、行の数は $\lbrace k,k+1, \dots, k+n \rbrace$の素因数分解に1回でも現れる素数の数ということになります。pythonで書くと以下のようになります。

from sympy import primerange

def nprmrange(k1,k2):
  return sum([1 if (k1//p+1)*p <= k2 else 0 for p in primerange(2,k2+1)])

素数の数$pn$分かれば積が平方数になる部分集合の数はは$2^{(n+1-pn)}$となるので答えは以下のように簡単に求まります。

for k1, k2 in [(5,11),(20,30),(50,75)]:
  pn = nprmrange(k1, k2)
  print(f"(k1,k2)=({k1}, {k2}), prime#={pn}, para#={k2-k1+1-pn}, answer={pow(2,k2-k1+1-pn)-1}")
# (k1,k2)=(5, 11), prime#=5, para#=2, answer=3
# (k1,k2)=(20, 30), prime#=8, para#=3, answer=7
# (k1,k2)=(50, 75), prime#=18, para#=8, answer=255

この考え方はProject Euler: Problem 619 Square subsetsを解くのに役に立ちます

（開発環境：Google Colab）