4x4 Magic square of squares of different integers

[2024.06.08]相異なる平方数から成る4x4魔法陣

相異なる正整数の平方数から成る4x4魔法陣を探すプログラム"msq4.c"(C)

■問題

       相異なる正整数の平方数から成る4x4魔法陣A(ここでは、Aを4x4平方数魔法陣と呼ぶ)を求めよ。

ここで、4x4平方数魔法陣Aとは、以下の条件(*)を満たす行列Aとする。
・A=(a[i,j]^2)は4行4列の行列で、その[i,j]成分は相異なる正整数a[i,j]の平方数a[i,j]^2である。
・縦,横,斜めの4個の成分の合計がある正整数Lに等しい。
       a[i,1]^2+a[i,2]^2+a[i,3]^2+a[i,4]^2=L (i=1,2,3,4),
       a[1,j]^2+a[2,j]^2+a[3,j]^2+a[4,j]^2=L (j=1,2,3,4),
       a[1,1]^2+a[2,2]^2+a[3,3]^2+a[4,4]^2=L,
       a[1,4]^2+a[2,3]^2+a[3,2]^2+a[4,1]^2=L

結果を簡潔に表示するために、行列A=(a[i,j]^2)の代わりに、A^*=(a[i,j])を使うことがある。

■(90°回転と鏡映で生成される)２面体群D₈の元で写されたものを同一視するために、行列Aの要素に以下の条件(**)を付けて良い。
       a[1,1] < min{ a[1,4], a[4,1], a[4,4] },
       a[4,1] < a[1,4],

このような4x4平方数魔法陣は存在する。|A|=max{a[i,j]}が最小になるものは、L=2823のときで、それは以下の4個である。

■平方数魔法陣はgcd({a[i,j]})=1、つまり、primitiveなものだけに制限して良い。
また、max{a[1,1],a[1,4],a[4,1],a[4,4]} <= Nのとき、 max{a[i,j]:i,j=1,2,3,4} <= 2*Nである。

■max{a[i,j]} <= Nの範囲で、A=(a[i,j]^2)が上記の条件を満たす平方数魔法陣となるような正整数行列A^*=(a[i,j])を求める。
アルゴリズムは以下の通り。
(1)a[1,1],a[4,4],a[1,4],a[4,1]を(**)を満たすように与えて、以下を繰り返す。
このとき、L=a[1,1]^2+a[1,4]^2+a[4,1]^2+a[4,4]^2である。
(2)a[2,2],a[2,3]を与えて、以下をくり返す。
(3)a[3,2]^2=a[1,1]^2+a[4,4]^2-a[2,3]^2 および a[3,3]^2=a[1,4]^2+a[4,1]^2-a[2,2]^2より、a[3,2],a[3,3]を求める。
(4)a[3,1]^2-a[2,4]^2=a[2,2]^2+a[2,3]^2-a[1,1]^2-a[4,1]^2=a[1,4]^2+a[4,4]^2-a[2,3]^2-a[3,3]^2より、a[2,4],a[3,1]を求める。
(5)a[2,1]^2=L-a[1,1]^2-a[3,1]^2-a[4,1]^2 および a[3,4]^2=L-a[1,4]^2-a[2,2]^2-a[4,4]^2より、a[2,1],a[3,4]を求める。
(6)a[4,3]^2-a[1,2]^2=a[1,1]^2+a[1,4]^2-a[2,3]^2-a[3,3]^2=a[2,2]^2+a[3,2]^2-a[4,1]^2-a[4,4]^2より、a[1,2],a[4,3]を求める。
(7)a[1,3]^2=L-a[1,1]^2-a[1,2]^2-a[1,4]^2 および a[4,2]^2=L-a[4,1]-2-a[4,3]^2-a[4,4]^2より、a[1,3],a[4,2]を求める。
(8)行列(a[i,j]^2)が平方数魔法陣の残りの条件を満たし、gcd({a[i,j]:1 <= i <= 4,1 <= j <= 4})=1であれば、(a[i,j])を出力する。

■max{a[i,j]} <= 100の範囲で、A=(a[i,j]^2)が上記の条件(*),(**)を満たす4x4平方数魔法陣となるような正整数行列A^*=(a[i,j])を求める。
[Cプログラムによる計算]

-bash-3.1$ gcc -O2 msq4.c -lm -o msq4
-bash-3.1$ ./msq4 -h
Usage: msq4 n
n : max{a[1,1],a[4,4],a[1,4],a[4,1],a[2,2],a[2,3]}<=n
-n            include non-primitive solutions
-s            max{a[*,*]}<=n
-a a0 a1      a0<=a[1,1]<=a1
-x x0         min{a[2,2],a[2,3]}>=x0
-L L0         a[1,1]^2+a[1,4]^2+a[4,1]^2+a[4,4]^2>=L0
-p            a[i,j] are all primes
-h            help
       where 16<=n<=100000.

-bash-3.1$ time ./msq4 100
[1,62,61,72,104,27,34,7,42,79,68,11,13,44,57,86]
[1,61,62,72,42,68,79,11,104,34,27,7,13,57,44,86]
[1,48,29,38,58,11,32,9,28,41,42,19,21,22,31,52]
[1,29,48,38,28,42,41,19,58,32,11,9,21,31,22,52]
[1,13,52,99,83,60,35,31,69,25,85,8,32,91,39,43]
[1,52,13,99,69,85,25,8,83,35,60,31,32,39,91,43]
[1,74,13,88,107,8,41,14,28,53,94,31,34,71,52,67]
[1,13,74,88,28,94,53,31,107,41,8,14,34,52,71,67]
[1,63,2,99,97,54,19,33,51,43,93,26,42,71,69,47]
[1,2,63,99,51,93,43,26,97,19,54,33,42,69,71,47]
[3,38,1,37,43,11,18,23,2,13,47,21,31,33,17,22]
[3,1,38,37,2,47,13,21,43,18,11,23,31,17,33,22]
[3,71,7,84,101,12,39,17,24,47,91,33,37,69,48,61]
[3,7,71,84,24,91,47,33,101,39,12,17,37,48,69,61]
[3,84,7,94,113,34,27,36,6,57,104,43,56,67,66,63]
[4,62,78,69,114,27,28,14,37,94,66,12,18,36,59,98]
[4,78,62,69,37,66,94,12,114,28,27,14,18,59,36,98]
[4,53,2,39,54,17,28,19,7,26,51,32,37,24,31,38]
[4,2,53,39,7,51,26,32,54,28,17,19,37,31,24,38]
[4,47,18,86,78,46,31,28,49,12,82,26,38,74,44,33]
[4,18,47,86,49,82,12,26,78,31,46,28,38,44,74,33]
[4,54,7,59,53,49,26,24,46,28,51,31,39,19,56,38]
[4,7,54,59,46,51,28,31,53,26,49,24,39,56,19,38]
[5,60,70,65,106,23,27,16,33,86,64,13,20,35,55,90]
[5,70,60,65,33,64,86,13,106,27,23,16,20,55,35,90]
[5,47,4,70,50,56,17,35,55,19,58,20,40,38,59,25]
[5,4,47,70,55,58,19,20,50,17,56,35,40,59,38,25]
[5,80,3,89,103,39,25,40,11,47,100,45,60,65,61,53]
[5,3,80,89,11,100,47,45,103,25,39,40,60,61,65,53]
[5,87,16,90,110,36,23,45,15,61,102,40,60,58,69,65]
[6,57,12,61,69,20,15,42,7,30,75,24,48,51,34,33]
[6,12,57,61,7,75,30,24,69,15,20,42,48,34,51,33]
[7,58,29,59,79,11,37,2,31,49,62,23,22,43,41,61]
[7,29,58,59,31,62,49,23,79,37,11,2,22,41,43,61]
[8,54,46,53,82,11,24,22,21,62,58,16,26,32,43,66]
[8,46,54,53,21,58,62,16,82,24,11,22,26,43,32,66]
[8,74,71,53,107,1,34,28,14,88,67,31,41,13,52,94]
[8,71,74,53,14,67,88,31,107,34,1,28,41,52,13,94]
[8,80,5,81,89,45,20,52,24,40,95,43,67,55,60,44]
[8,5,80,81,24,95,40,43,89,20,45,52,67,60,55,44]
[9,44,27,22,42,13,36,1,32,33,26,21,19,6,23,48]
[9,27,44,22,32,26,33,21,42,36,13,1,19,23,6,48]
[9,73,51,42,57,30,75,1,78,45,35,21,19,39,18,87]
[9,51,73,42,78,35,45,21,57,75,30,1,19,18,39,87]
[9,62,11,72,83,24,33,26,12,29,82,39,46,63,36,43]
[9,11,62,72,12,82,29,39,83,33,24,26,46,36,63,43]
[9,83,64,72,116,12,21,47,3,89,88,24,52,36,63,91]
[9,64,83,72,3,88,89,24,116,21,12,47,52,63,36,91]
[10,80,49,67,101,17,20,50,8,74,85,25,55,35,58,76]
[10,49,80,67,8,85,74,25,101,20,17,50,55,58,35,76]
[11,43,23,18,38,3,37,1,33,31,22,17,13,2,21,47]
[11,23,43,18,33,22,31,17,38,37,3,1,13,21,2,47]
[11,54,32,62,82,8,26,21,22,53,66,16,24,46,43,58]
[11,32,54,62,22,66,53,16,82,26,8,21,24,43,46,58]
[11,48,22,41,58,1,21,28,9,38,52,19,32,29,31,42]
[11,22,48,41,9,52,38,19,58,21,1,28,32,31,29,42]
[11,58,43,49,79,7,22,31,2,59,61,23,37,29,41,62]
[11,43,58,49,2,61,59,23,79,22,7,31,37,41,29,62]
[11,59,17,68,77,28,31,29,8,23,79,41,49,61,32,37]
[11,17,59,68,8,79,23,41,77,31,28,29,49,32,61,37]
[11,68,33,74,73,54,19,52,26,17,88,51,72,59,46,23]
[11,33,68,74,26,88,17,51,73,19,54,52,72,46,59,23]
[12,83,36,89,116,9,52,3,47,72,91,24,21,64,63,88]
[12,36,83,89,47,91,72,24,116,52,9,3,21,63,64,88]
[12,49,59,82,106,13,33,16,23,64,86,27,29,78,28,71]
[12,59,49,82,23,86,64,27,106,33,13,16,29,28,78,71]
[12,71,69,47,101,3,37,24,17,84,61,33,39,7,48,91]
[12,69,71,47,17,61,84,33,101,37,3,24,39,48,7,91]
[12,49,26,82,74,38,33,44,47,4,86,18,46,78,28,31]
[12,26,49,82,47,86,4,18,74,33,38,44,46,28,78,31]
[13,42,1,36,44,9,22,27,6,19,48,23,33,32,21,26]
[13,1,42,36,6,48,19,23,44,22,9,27,33,21,32,26]
[13,49,78,64,106,12,29,23,16,82,71,27,33,59,28,86]
[13,78,49,64,16,71,82,27,106,29,12,23,33,28,59,86]
[13,99,1,52,64,25,85,27,83,35,60,31,39,32,43,91]
[13,1,99,52,83,60,35,31,64,85,25,27,39,43,32,91]
[13,72,11,99,111,29,33,32,9,41,108,43,52,87,49,51]
[15,34,12,75,69,48,6,7,42,33,61,24,20,51,57,30]
[15,12,34,75,42,61,33,24,69,6,48,7,20,57,51,30]
[17,80,35,74,101,10,55,8,50,67,76,25,20,49,58,85]
[17,35,80,74,50,76,67,25,101,55,10,8,20,58,49,85]
[17,54,19,28,53,4,39,2,24,37,38,31,26,7,32,51]
[17,19,54,28,24,38,37,31,53,39,4,2,26,32,7,51]
[17,26,51,88,59,72,23,46,68,11,74,33,54,73,52,19]
[17,51,26,88,68,74,11,33,59,23,72,46,54,52,73,19]
[17,59,4,58,50,40,5,55,35,25,70,20,56,38,47,19]
[17,4,59,58,35,70,25,20,50,5,40,55,56,47,38,19]
[17,99,71,98,127,14,39,83,6,73,133,41,91,97,22,81]
[19,69,2,93,97,42,1,51,33,47,99,26,54,71,63,43]
[19,2,69,93,33,99,47,26,97,1,42,51,54,63,71,43]
[20,45,10,90,82,54,29,12,51,28,78,34,30,70,60,35]
[20,10,45,90,51,78,28,34,82,29,54,12,30,60,70,35]
[20,60,5,95,89,67,8,24,52,44,81,43,45,55,80,40]
[20,5,60,95,52,81,44,43,89,8,67,24,45,80,55,40]
[21,98,52,86,124,2,43,54,22,84,106,37,62,59,66,92]
[21,105,5,97,113,43,39,69,11,49,123,57,87,75,65,59]
[22,76,66,37,86,27,62,4,53,74,44,42,36,2,43,94]
[22,66,76,37,53,44,74,42,86,62,27,4,36,43,2,94]
[22,103,11,94,107,46,38,71,14,43,121,58,89,74,62,53]
[23,60,35,86,106,5,20,33,16,65,90,13,27,70,55,64]
[23,35,60,86,16,90,65,13,106,20,5,33,27,55,70,64]
[23,49,3,91,79,63,29,13,61,37,71,33,27,59,73,41]
[23,3,49,91,61,71,37,33,79,29,63,13,27,73,59,41]
[23,8,41,79,61,49,37,32,59,11,68,17,28,77,29,31]
[23,41,8,79,59,68,11,17,61,37,49,32,28,29,77,31]
[23,69,47,99,81,61,33,77,63,13,111,29,79,93,41,27]
[24,83,26,33,62,9,72,11,63,46,43,36,29,12,39,82]
[24,26,83,33,63,43,46,36,62,72,9,11,29,39,12,82]
[24,95,20,93,99,52,31,72,23,36,117,56,88,75,60,41]
[25,64,27,85,99,13,52,1,32,39,91,43,35,83,31,60]
[25,27,64,85,32,91,39,43,99,52,13,1,35,31,83,60]
[25,69,71,83,113,29,41,45,49,85,87,11,39,67,55,91]
[25,71,69,83,49,87,85,11,113,41,29,45,39,55,67,91]
[25,61,3,100,103,60,5,11,40,53,89,45,39,65,80,47]
[25,3,61,100,40,89,53,45,103,5,60,11,39,80,65,47]
[25,69,8,85,91,32,43,39,13,1,99,52,60,83,31,35]
[25,8,69,85,13,99,1,52,91,43,32,39,60,31,83,35]
[25,76,18,90,102,6,41,52,14,38,108,39,60,87,34,50]
[26,56,7,51,53,39,4,46,24,38,59,31,49,19,54,28]
[26,7,56,51,24,59,38,31,53,4,39,46,49,54,19,28]
[27,62,36,94,114,4,18,37,14,69,98,12,28,78,59,66]
[27,36,62,94,14,98,69,12,114,18,4,37,28,59,78,66]
[27,62,44,79,104,1,13,42,7,72,86,11,34,61,57,68]
[27,44,62,79,7,86,72,11,104,13,1,42,34,57,61,68]
[27,76,2,74,86,22,36,53,4,37,94,42,62,66,43,44]
[27,2,76,74,4,94,37,42,86,36,22,53,62,43,66,44]
[29,69,67,85,113,25,39,49,45,83,91,11,41,71,55,87]
[29,67,69,85,45,91,83,11,113,39,25,49,41,55,71,87]
[29,73,3,71,79,27,23,61,13,41,91,33,63,59,49,37]
[29,3,73,71,13,91,41,33,79,23,27,61,63,49,59,37]
[29,107,20,75,111,40,55,37,23,71,93,64,68,15,79,85]
[29,20,107,75,23,93,71,64,111,55,40,37,68,79,15,85]
[30,57,1,75,73,9,42,51,39,19,87,18,45,78,21,35]
[30,1,57,75,39,87,19,18,73,42,9,51,45,21,78,35]
[40,107,15,71,111,29,68,23,37,75,85,64,55,20,79,93]
[40,15,107,71,37,85,75,64,111,68,29,23,55,79,20,93]
[52,125,41,98,127,14,80,83,50,73,133,64,91,92,62,95]
[53,104,34,97,103,46,4,107,44,77,127,14,94,73,83,56]
[56,103,34,97,119,2,49,88,17,76,127,46,82,89,68,71]
[56,89,62,97,119,2,49,88,17,76,127,46,82,103,44,71]
140 primitive solutions.

real    70m25.578s
user    68m8.042s
sys     0m0.000s

■max{a[i,j]} <= 200の範囲で、A=(a[i,j]^2)が上記の条件(*),(**)を満たす4x4平方数魔法陣となるような正整数行列A^*=(a[i,j])を求めると、このようになる。Lの小さい順に並び替えると、このようになる。

■max{a[i,j]} <= 1000の範囲で、A=(a[i,j]^2)が上記の条件(*),(**)を満たし、素数の平方数から成る4x4平方数魔法陣となるような(素数から成る)行列A^*=(a[i,j])を求めると、以下のようになる。
[Cプログラムによる計算]

-bash-3.1$  time ./msq4 1000 -L 2564 -p -a 3 997
[23,409,641,397,761,283,263,89,353,691,331,157,179,107,383,739]
[23,641,409,397,353,331,691,157,761,263,283,89,179,383,107,739]
[29,277,71,653,673,163,139,101,191,211,647,97,137,601,257,251]
[29,71,277,653,191,647,211,97,673,139,163,101,137,257,601,251]
[29,757,691,563,971,227,601,113,487,709,673,419,433,491,277,929]
[29,691,757,563,487,673,709,419,971,601,227,113,433,277,491,929]
[139,257,71,647,673,137,29,191,101,251,653,97,163,601,277,211]
[139,71,257,647,101,653,251,97,673,29,137,191,163,277,601,211]
[193,79,571,701,769,311,317,269,439,479,659,67,199,727,11,541]
[193,571,79,701,439,659,479,67,769,317,311,269,199,11,727,541]
[227,757,491,709,971,29,433,487,113,563,929,419,601,691,277,673]
[227,491,757,709,113,929,563,419,971,433,29,487,601,277,691,673]
[263,383,641,331,761,179,23,353,89,739,397,157,283,107,409,691]
[263,641,383,331,89,397,739,157,761,23,179,353,283,409,107,691]
[311,79,727,479,769,193,199,439,269,701,541,67,317,571,11,659]
[311,727,79,479,269,541,701,67,769,199,193,439,317,11,571,659]
16 primitive solutions.

real    3275m10.000s
user    3133m19.200s
sys     0m0.210s

素数の平方数から成る4x4平方数魔法陣A(16個)をLの小さい順に並べ替えて、A^*を表示すると、以下のようになる。

L:[a11,a12,a13,14,a21,a22,a23,a24,a31,a32,a33,a34,a41,a42,a43,a44]
------------------------------------------------------------------
509020:[29, 277, 71, 653, 673, 163, 139, 101, 191, 211, 647, 97, 137, 601, 257, 251]
509020:[29, 71, 277, 653, 191, 647, 211, 97, 673, 139, 163, 101, 137, 257, 601, 251]
509020:[139, 257, 71, 647, 673, 137, 29, 191, 101, 251, 653, 97, 163, 601, 277, 211]
509020:[139, 71, 257, 647, 101, 653, 251, 97, 673, 29, 137, 191, 163, 277, 601, 211]
736300:[23, 409, 641, 397, 761, 283, 263, 89, 353, 691, 331, 157, 179, 107, 383, 739]
736300:[23, 641, 409, 397, 353, 331, 691, 157, 761, 263, 283, 89, 179, 383, 107, 739]
736300:[263, 383, 641, 331, 761, 179, 23, 353, 89, 739, 397, 157, 283, 107, 409, 691]
736300:[263, 641, 383, 331, 89, 397, 739, 157, 761, 23, 179, 353, 283, 409, 107, 691]
860932:[193, 79, 571, 701, 769, 311, 317, 269, 439, 479, 659, 67, 199, 727, 11, 541]
860932:[193, 571, 79, 701, 439, 659, 479, 67, 769, 317, 311, 269, 199, 11, 727, 541]
860932:[311, 79, 727, 479, 769, 193, 199, 439, 269, 701, 541, 67, 317, 571, 11, 659]
860932:[311, 727, 79, 479, 269, 541, 701, 67, 769, 199, 193, 439, 317, 11, 571, 659]
1368340:[29, 757, 691, 563, 971, 227, 601, 113, 487, 709, 673, 419, 433, 491, 277, 929]
1368340:[29, 691, 757, 563, 487, 673, 709, 419, 971, 601, 227, 113, 433, 277, 491, 929]
1368340:[227, 757, 491, 709, 971, 29, 433, 487, 113, 563, 929, 419, 601, 691, 277, 673]
1368340:[227, 491, 757, 709, 113, 929, 563, 419, 971, 433, 29, 487, 601, 277, 691, 673]