3x3 Magic Square of 7 Squares
Study 3
Introduction
A necessary condition for a 3x3 magic square of distinct squares
is a solution to any of its 7-square subsets.
This paper studies the following 7-square subset
where a,b,c > 0 and thus, c+(a+b) is the largest entry.
c+a c-(a+b) c+b
c+(b-a) c c-(b-a)
------- c+(a+b) -------
This configuration contains three arithmetic progressions having the
same ending value:
c+(b-a), c+b, c+(a+b), with step value a;
c-(b-a), c+a, c+(a+b), with step value b;
c-(a+b), c, c+(a+b), with step value a+b.
Since these values must be squares, this motivates the study of
3-square arithmetic progressions having a fixed ending value.
If we can find a set of three progressions that also have the
step value relationship (a, b, a+b), we will have found a magic square
containing at least 7 squared entries.
Results of the Study
The largest value in a 3x3 magic square of squares must be the square of
a composite number; either the product of two or more different primes
or at least the third power of a single prime.
The Arithmetic Progression Formula
The 3-square arithmetic progression under study is
Ln2, Mn2, H2,
where H is fixed.
The step value of the progression = H2 - Mn2 = Mn2 - Ln2.
This is expressed in this paper as
(1) H2 = 2Mn2 - Ln2; 0 < Ln < Mn < H.
We want to find all solutions for a given value of H2.
Note that since 0 < Ln < Mn < H, there are only
a finite number of integer solutions for a given H.
Formula for the Number of Solutions
If the prime factorization of
H = paqb...rc,
then the number of solutions is
g = (1/2)[(2a + 1)(2b + 1)...(2c + 1) - 1].
Proof
Examples
Given that p, q, r are primes:
H g
1 1
p 1
p2 2
p3 3
pq 4
p2q 7
pqr 13
Magic Square Requirements
We need to find three 3-square arithmetic progressions having the same
ending value and their step values must have the relationship (a, b, a+b).
In other words, the sum of the step values of the first two arithmetic
progressions equals the step value of the third.
We can also express this with twice the step values.
Twice the step value of arithmetic progression Ln2, Mn2, H2
is (H2 - Ln2). So we need to find three solutions for H2 that use
(Mi,Li), (Mj,Lj), (Mk,Lk) and that satisfy the equation
(H2 - Li2) + (H2 - Lj2) = (H2 - Lk2).
Note that Lk must be the smallest term.
Subtracting 2H2 from both sides and negating,
(2) Li2 + Lj2 = Lk2 + H2; Li > Lj > Lk.
Magic Square Enumeration Procedure
Find all the solutions (M1,L1) ... (Mg,Lg), arranged in
decreasing Ln value. For each k from 3 through g, check combinations
of Li, Lj, i < j < k, for a solution.
Checking combinations for Hk can be done in at worst linear time.
Here is a general procedure.
Set i := 1; j := k-1.
Do
Compare Li2 + Lj2 to Lk2 + H2;
If too large, increment i;
Else If too small, decrement j;
Else just right; (you have found a magic square of 7 squares)
While i < j (which will be at most k-2 times).
Prime Factor Reduction
In a 3-square arithmetic progression, if either the lowest or highest
values have a prime factor of the form 8k+3 or 8k+5, then all three
terms will have that factor. This also means that all 7 of the entries
in a magic square will have that factor. So we can divide out the factor
producing a smaller magic square. Therefore it is not necessary to test
values of L and H having those primes as factors.
This leaves values of L and H having prime factors of only 8k+1 and 8k+7.
The first of these numbers are
1, 7, 17, 23, 31, 41, 47, 49, 71, 73, 79, 89, 97, 103, 113, 119.
This reduces the number of H values that need to be tested
and also reduces the number of L values that need to be searched
to find the generators. They both come from the same list.
Proof
Given
H2 = 2M2 - L2,
we factor this in the unique factorization domain Z[√2] as
H2 = (M√2 + L)(M√2 - L).
If a prime of the form 8k+3 or 8k+5, which is also a prime in
the domain Z[√2], is a factor of H, then it must also be
a factor of (M√2 + L) or (M√2 - L). If it is a factor
of one of them, it is also a factor of the conjugate, so it is a
factor of both. If it is a factor of both, then it is also a factor
of their difference, which is 2L. Since the factor is odd, it is
a factor of L. If it is a factor of H and L and odd, then it is also
a factor of M. Thus, it is a factor of all three terms and can be
factored out to produce a smaller solution. Therefore, values of H
having prime factors of 8k+3 or 8k+5 need not be tested.
Composition of Forms
We can directly compute all the solutions for Hw using the
lists of solutions for Hu and Hv.
To do this we use the following composition and scaling formulas.
(3a) Mw = (2MuMv + LuLv) - (MuLv + LuMv)
(3b) Lw = |(2MuMv + LuLv) - 2(MuLv + LuMv)|
(4a) Mw = (2MuMv - LuLv) - |MuLv - LuMv|
(4b) Lw = (2MuMv - LuLv) - 2|MuLv - LuMv|
(5a) Mw = MuHv
(5b) Lw = LuHv
(6a) Mw = MvHu
(6b) Lw = LvHu
To use the above formulas for the case where Hu and Hv have no
prime factors in common, follow this procedure.
For each (Mu,Lu),
For each (Mv,Lv),
Use (3a),(3b);
Use (4a),(4b).
For each Mu,Lu),
Use (5a),(5b).
For each (Mv,Lv),
Use (6a),(6b).
If Hw is a power of a prime, pa, then its solutions
can be computed from the solutions for Hu = p and Hv = pa-1.
The procedure is different, depending on whether the power is even or odd.
It is also required to keep track of the one primitive solution
in each list of solutions for prime powers.
For a prime, there is exactly one solution and it is primitive.
For a prime power, follow this procedure.
To compute the scaled solutions of Hw:
For each (Mv,Lv),
Use (6a),(6b).
To compute the primitive solution of Hw:
If the power, a, is even
Use (3a),(3b) on both primitive solutions.
Else
Use (4a),(4b) on both primitive solutions.
Example
Hw = 72.
For Hu = 7, (Mu,Lu) = {(5,1)} and is primitive.
For Hv = 7, (Mv,Lv) = {(5,1)} and is primitive.
The power of the prime is even, so we use (3a),(3b) and (6a),(6b).
Hu Mu Lu Mv Lv Mw Lw
(3a), (3b) --> -- 5 1 5 1 41 31 (primitive)
(6a), (6b) --> 7 - - 5 1 35 7
Example
Hw = 73.
For Hu = 7, (Mu,Lu) = {(5,1)} and is primitive.
For Hv = 72, (Mv,Lv) = {(35,7), (41,31)},
the last one being primitive.
The power of the prime is odd, so we use (4a),(4b) and (6a),(6b).
Hu Mu Lu Mv Lv Mw Lw
(4a), (4b) --> -- 5 1 41 31 265 151 (primitive)
(6a), (6b) --> 7 - - 41 31 287 217
(6a), (6b) --> 7 - - 35 7 245 49
Example
Hw = 391 = 17x23
For Hu = 23, (Mu,Lu) = {(17,7)}.
For Hv = 17, (Mv,Lv) = {(13,7)}.
Hu Hv Mu Lu Mv Lv Mw Lw
(3a), (3b) --> -- -- 17 7 13 7 281 71
(4a), (4b) --> -- -- 17 7 13 7 365 337
(6a), (6b) --> 23 -- - - 13 7 299 161
(5a), (5b) --> -- 17 17 7 -- - 289 119
Example
Hw = 19159 = 49x391 = 72x(17x23)
For Hu = 49, (Mu,Lu) = {(41,31),(35,7)}.
For Hv = 391, (Mv,Lv) = {(281,71),(289,119),(299,161),(365,337)}.
Hu Hv Mu Lu Mv Lv Mw Lw
(3a), (3b) --> -- --- 41 31 281 71 13621 1999
(3a), (3b) --> -- --- 41 31 289 119 13549 289
(3a), (3b) --> -- --- 41 31 299 161 13639 2231
(3a), (3b) --> -- --- 41 31 365 337 15245 9887
(3a), (3b) --> -- --- 35 7 281 71 15715 11263
(3a), (3b) --> -- --- 35 7 289 119 14875 8687
(3a), (3b) --> -- --- 35 7 299 161 14329 6601
(3a), (3b) --> -- --- 35 7 365 337 13559 791
(4a), (4b) --> -- --- 41 31 281 71 15041 9241
(4a), (4b) --> -- --- 41 31 289 119 15929 11849
(4a), (4b) --> -- --- 41 31 299 161 16859 14191
(4a), (4b) --> -- --- 41 31 365 337 16981 14479
(4a), (4b) --> -- --- 35 7 281 71 18655 18137
(4a), (4b) --> -- --- 35 7 289 119 17255 15113
(4a), (4b) --> -- --- 35 7 299 161 16261 12719
(4a), (4b) --> -- --- 35 7 365 337 13951 4711
(5a), (5b) --> -- 391 41 31 -- -- 16031 12121
(5a), (5b) --> -- 391 35 7 -- -- 13685 2737
(6a), (6b) --> 49 --- - - 281 71 13769 3479
(6a), (6b) --> 49 --- - - 289 119 14161 5831
(6a), (6b) --> 49 --- - - 299 161 14651 7889
(6a), (6b) --> 49 --- - - 365 337 17885 16513
Finding Solutions For Primes
The Composition of Forms reduces the problem to scanning for solutions
only for primes, while solutions for composites are directly computed.
This section shows how to further reduce the work in finding the solution
for a prime by scanning in the much smaller range 0 ... √H.
Also, since there is only one solution for a prime,
once you find it, you can stop scanning.
Instead of looking for a solution to H2 = 2M2 - L2,
look for the solution to
H = 2e2 - f2,
then use a version of the composition formulas to compute
the solution for H2.
(7a) M = 2e2 + f2 - 2ef
(7b) L = |2e2 + f2 - 4ef|
Examples
H e f M L
7 2 1 5 1
17 3 1 13 7
23 4 3 17 7
31 4 1 25 17
41 5 3 29 1
47 6 5 37 23
71 6 1 61 49
73 7 5 53 17
79 8 7 65 47
A Magic Square Search
The following presents the results of a search for some sample values of H.
Note that in order for a given value of H to have at least 3 solutions,
it must be a composite number consisting of at least the product of two
different primes or at least the cube of one prime.
Prime factors of H are all 8k+1 or 8k+7.
The smallest value of H that meets these conditions is 119.
H = 119 = 7x17
n 1 2 3 4
Ln 79 49 41 17
Note that 792 is less than half of 1192.
This means that 792 + Lj2 < Lk2 + H2 for any choices of 1 < j < k.
Also, all choices of Li, Lj, 1 < i < j, will be even smaller.
So (2) cannot be satisfied.
H = 161 = 7x23
n 1 2 3 4
Ln 127 73 49 23
1272 is greater than half of 1612, so we proceed.
Note that the largest sum, 1272 + 732 < 1612.
This means that all choices of Li, Lj will be too small to satisfy (2).
H = 287 = 7x41
n 1 2 3 4
Ln 241 223 41 7
i=1,j=2,k=3. 2412 + 2232 > 412 + 2872.
i=1,j=3,k=4. 2412 + 412 < 72 + 2872.
i=1,j=2,k=4. 2412 + 2232 > 72 + 2872.
H = 511 = 7x73
n 1 2 3 4
Ln 449 271 119 73
i=1,j=2,k=3. 4492 + 2712 > 1192 + 5112,
but only by 240.
i=1,j=3,k=4. 4492 + 1192 < 732 + 5112.
i=1,j=2,k=4. 4492 + 2712 > 732 + 5112.
H = 833 = 7x7x17
n 1 2 3 4 5 6 7
Ln 617 553 527 343 287 119 97
6172 is less than half of 8332.
H = 1127 = 7x7x23
n 1 2 3 4 5 6 7
Ln 889 713 697 511 343 161 17
i=1,j=2,k=3. 8892 + 7132 < 6972 + 11272.
i=1,j=3,k=4. 8892 + 6972 < 5112 + 11272.
i=1,j=2,k=4. 8892 + 7132 < 5112 + 11272.
i=1,j=4,k=5. 8892 + 5112 < 3432 + 11272.
i=1,j=3,k=5. 8892 + 6972 < 3432 + 11272.
i=1,j=2,k=5. 8892 + 7132 < 3432 + 11272.
i=1,j=5,k=6. 8892 + 3432 < 1612 + 11272.
i=1,j=4,k=6. 8892 + 5112 < 1612 + 11272.
i=1,j=3,k=6. 8892 + 6972 < 1612 + 11272.
i=1,j=2,k=6. 8892 + 7132 > 1612 + 11272,
but only by 2640.
i=1,j=6,k=7. 8892 + 1612 < 972 + 11272,
i=1,j=5,k=7. 8892 + 3432 < 972 + 11272,
i=1,j=4,k=7. 8892 + 5112 < 972 + 11272,
i=1,j=3,k=7. 8892 + 6972 > 972 + 11272,
i=2,j=3,k=7. 7132 + 6972 < 972 + 11272,