3x3 Magic Square of 7 Squares
Study 1
A Characterization of
3-Square Arithmetic Progressions
with a Fixed Starting Value
or
How to Find a 3x3 Magic Square of Squares
Having Monstrously Large Numbers
For the experts involved
With problems, unsolved,
A puzzle that stymies the best devotee:
Magic square of squared numbers
That further encumbers
All entries, distinct, with its size, three by three.
If computers should dare
To seek such a square,
A warning to program designers in charge:
Martin Gardner insists
That "If it exists,
Its numbers are sure to be monstrously large".
Introduction
Results of the Study
Part 1 - Generating All Arithmetic Progressions
The Arithmetic Progression Formula
Forward Recursion Theorem
Reverse Recursion Formulas
5/7 Lemma
Reverse Recursion Reduction Lemma
Finite Generator Theorem
Generator Nonredundancy Theorem
Relative Placement Theorem
Part 2 - Enumerating Potential Magic Squares
Magic Square Requirements
Magic Square Enumeration Procedure
Changing Geometric Progression Lemma
Corresponding Combination Rejection Lemma
Enumeration Termination Theorem
Part 3 - Finding Generators
Prime Factor Reduction
Formula for the Number of Generators
Generators Come In Pairs
The Pre-Generator Method
Composition of Forms
Finding Pre-Generators For Primes
Part 4 - Future Research
Extending the Results
Magic Square Search Ideas
Impossibility Proof Ideas
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 smallest entry.
------- c-(a+b) -------
c+(b-a) c c-(b-a)
c-b c+(a+b) c-a
This configuration contains three arithmetic progressions having the
same starting value:
c-(a+b), c-b, c-(b-a), with step value a;
c-(a+b), c-a, c+(b-a), with step value b; and
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 starting 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.
Suppose we have a 3-square arithmetic progression given by L2, Mn2, Hn2
where 0 < L < Mn < Hn, and suppose that the smallest value, L = 1.
Here is a list of the progressions for n = 1 ... 5.
n L2 Mn2 Hn2 STEP
--- --- ----- ----- -------
1 12 52 72 24
2 12 292 412 840
3 12 1692 2392 28560
4 12 9852 13932 970224
5 12 57412 81192 32959080
Every 3-square arithmetic progression starting from 1 can be produced
using a simple recursion. Note how fast the step values increase in size.
If there were a magic square having 1 as the smallest value, but with
the largest value having 100 digits, that solution could be found in about
66 iterations of the recursion.
But because any choice of the largest step value is more than twice the size
of any step value below it, there can't be a selection of three step values
with the relationship (a, b, a+b). Therefore L = 1 cannot be the smallest
entry in this 7-square configuration. This also means that 1 cannot be the
smallest entry in any 3x3 magic square of distinct squares.
Other starting values can be proved impossible using a termination condition,
derived in this paper. It has been found that the termination condition occurs
surprisingly early in a generated sequence of candidate step values. So the
impossibility of each starting value takes very little time to prove.
Results of the Study
This paper contains a proof that all 3-square arithmetic progressions with
a fixed starting value can be produced by simple recursions of an
easily obtainable finite set of generators.
Each recursively produced sequence consists of values in a near-geometric
progression increasing by about 34 times for each iteration, so the numbers
get very large very fast. This makes it possible to do a quick but complete
search for magic squares having monstrously large numbers.
But better than that, this paper contains a proof that if an enumeration is
done for a particular starting value, then once a certain condition occurs,
it is no longer possible to achieve a solution, and so the enumeration
can be terminated as impossible to satisfy.
Enumerations have been done and it has been found that there is no solution
to the above 7-square configuration having a starting value less than 1014.
It has been known for a long time that a 3x3 magic square of squares
must contain very large numbers, but the current result is new in that
all the numbers must be large. All nine entries of a 3x3 magic
square of distinct squares must be at least the squares of 8-digit numbers.
Part 1
Generating All Arithmetic Progressions
This part of the paper develops and proves a technique for generating
all possible 3-square arithmetic progressions having a fixed starting value.
The technique uses a recursive formula which takes a "generator" progression
and produces an infinite series of progressions with increasing values.
The Arithmetic Progression Formula
The 3-square arithmetic progression under study is
L2, Mn2, Hn2,
where L is fixed.
The step value of the progression = Mn2 - L2 = Hn2 - Mn2.
This is expressed in this paper as
(1) L2 = 2Mn2 - Hn2; 0 < L < Mn < Hn.
We want to represent a given value of L2 as this binary quadratic form
in all possible ways. We also want to generate those representations,
as needed, in Hn order: H1 < H2 < H3, and so on.
The recursion described below will accomplish this, however, it must be noted
that putting a representation using (Mn,Hn) into the recursion does not
in general produce (Mn+1,Hn+1). For example, if L is prime,
then putting (Mn,Hn) into the recursion will produce (Mn+3,Hn+3).
Thus, in this case we need three different recursive sequences in order
to produce all the representations.
In this paper, the number of different recursive sequences needed to produce
all Hn values for a given L is given by g.
That is, putting (Mn,Hn) into the recursion produces (Mn+g,Hn+g).
Forward Recursion Theorem
Given a representation of (1) using (Mn,Hn) for a given L,
then (Mn+g,Hn+g) given by
(2a) Mn+g = 3Mn + 2Hn,
(2b) Hn+g = 3Hn + 4Mn
is also a representation.
Proof
Starting with
2Mn+g2 - Hn+g2,
substitute (2a), (2b),
2(3Mn + 2Hn)2 - (3Hn + 4Mn)2,
expand the terms,
18Mn2 + 8Hn2 + 24HnMn - (9Hn2 + 16Mn2 + 24HnMn),
and cancel, producing
2Mn2 - Hn2,
which from (1) is equal to L2.
Thus
2Mn+g2 - Hn+g2 = L2.
Remark
Note that the recursion has only positive coefficients, therefore
starting with a representation using positive numbers, the recursion produces
a sequence of representations using increasingly larger positive numbers.
Example
The number of different recursion sequences that can be produced for a given L
is given by g. Suppose that L = 7. It will be found that g = 3.
The smallest representation uses
(M1,H1) = ( 13, 17); 72 = 2(132) - 172.
Putting these values into the recursion produces
(M4,H4) = ( 73,103); 72 = 2(732) - 1032;
(M7,H7) = (425,601); 72 = 2(4252) - 6012.
Here is the second smallest representation for L = 7.
It produces a different sequence.
(M2,H2) = ( 17, 23); 72 = 2(172) - 232.
Putting these values into the recursion produces
(M5,H5) = ( 97,137); 72 = 2(972) - 1372;
(M8,H8) = (565,799); 72 = 2(5652) - 7992.
Here is the third smallest representation where Hg = 7L.
(M3,H3) = ( 35, 49); 72 = 2(352) - 492.
Putting these values into the recursion produces
(M6,H6) = ( 203, 287); 72 = 2(2032) - 2872;
(M9,H9) = (1183,1673); 72 = 2(11832) - 16732.
Remark
Note that H1 through H9 are in increasing order,
even though they came from multiple sequences. It will be proved below
that this will always be true for any L.
Reverse Recursion Formulas
Solving for the inverse recursion formulas from (2a), (2b),
(3a) Mn = 3Mn+g - 2Hn+g,
(3b) Hn = 3Hn+g - 4Mn+g.
Remark
Since the forward recursion takes positive values and produces a sequence
of ever-increasing values, the reverse recursion must produce a sequence of
ever-decreasing values.
5/7 Lemma
Given a representation of (1) using (Mn,Hn) for a given L,
if
Hn > 7L,
then
Mn < (5/7)Hn.
Proof
If Hn > 7L then
L < Hn/7
and combining with (1)
2Mn2 = Hn2 + L2 < Hn2 + Hn2/49
or
Mn2 < (25/49)Hn2
or
Mn < (5/7)Hn.
Reverse Recursion Reduction Lemma
Given a representation of (1) using (Mn+g,Hn+g) for a given L,
then applying the reverse recursion (3a),(3b) to produce (Mn,Hn),
if
Hn+g > 7L,
then
Hn > L.
Proof
If Hn+g > 7L, then from the 5/7 Lemma
Mn+g < (5/7)Hn+g.
Combining with (3a),
Hn = 3Hn+g - 4Mn+g > 3Hn+g - 4(5/7)Hn+g
or
Hn > Hn+g/7.
And since Hn+g > 7L,
Hn > L.
Finite Generator Theorem
A generator is a representation of (1) that is not produced by any other
representation using the recursion (2a),(2b). For a given value of L,
there is a finite number, g, of generators using (M1,H1) ... (Mg,Hg)
and L < H1 < ... < Hg < 7L.
Proof
Starting from any representation where Hn > 7L and applying the reverse
recursion (3a),(3b) repeatedly, we will eventually encounter a terminal
representation with Ht < 7L, for some t.
When this happens, the previous representation that produced it
must have had Ht+g > 7L, thus this terminal representation
must have Ht > L by the Reverse Recursion Reduction Lemma.
Therefore, this terminal representation has L < Ht < 7L,
and is the generator of the sequence of representations that were
encountered using the above reverse recursion procedure. When the
forward recursion (2a),(2b) is applied, all representations
in that sequence are reachable.
Since starting from any representation and applying the reverse recursion
always eventually produces a representation with L < Ht < 7L,
then all representations with numbers greater than that range are reachable
by starting with a representation in that range and applying the
forward recursion. Since that range is finite for a given value of L,
the number of generators is finite for a given L.
Remark
Finding all generators is just a matter of testing values for Hn,
n = 1 ... g-1, in the range L ... 7L that satisfy (1);
then adding Hg = 7L, which is always a generator.
Part 3 of this paper shows that there exist faster ways.
Generator Nonredundancy Theorem
All representations using (Mn,Hn) with L < Hn < 7L are generators.
Remark
When searching for generators in the finite range, there is no chance
that one of them could be produced by another in the same range.
Therefore, in a computer procedure, there is no need to check for
duplicate values.
Proof
Given a representation using (Hn,Mn) with L < Hn < 7L,
then from (1),
2Mn2 = Hn2 + L2 > 2L2
thus
Mn > L.
From the recursion (2a),
Hn+g = 3Hn + 4Mn
and since
3Hn + 4Mn > 3L + 4L = 7L
we have
Hn+g > 7L.
Therefore, one application of the recursion on a generator
always produces a representation past the range of the generators.
So there is no chance of finding a non-generator in the generator range.
Relative Placement Theorem
Any two different recursive sequences produce mutually exclusive
sets of representations and their relative placements within the sets
of sequences never change. This is because Hj < Hk implies Hj+g < Hk+g
for any j and k.
Remark
This is important for the orderly enumeration of representations.
The example above with L = 7 and g = 3 shows that the Hn values
are produced in increasing order by applying the recursion once for each
generator sequence, then repeating the recursion once each for the
produced values, and so on.
Proof
Suppose (Mj,Hj) and (Mk,Hk) are used in two different representations
produced from possibly different generated sequences with
Hj < Hk.
We have
2Mj2 - Hj2 = L2,
2Mk2 - Hk2 = L2,
thus
2Mj2 = Hj2 + L2
and since Hj < Hk
2Mj2 < Hk2 + L2
or
2Mj2 < 2Mk2
or
Mj < Mk.
Therefore,
Hj < Hk implies Mj < Mk.
Suppose that g is the number of generators and the forward recursion
(2a),(2b) produces Hj+g from Hj and Hk+g from Hk in the
sets of sequences.
Then
Hj+g = 3Hj + 4Mj
and since Hj < Hk and Mj < Mk
Hj+g < 3Hk + 4Mk
or
Hj+g < Hk+g.
Therefore,
Hj < Hk implies Hj+g < Hk+g
for any j and k, and their relative placement never changes.
This also means that their values can never be the same, thus multiple
recursive sequences produce mutually exclusive values.
Part 2
Enumerating Potential Magic Squares
This part of the paper describes a procedure for enumerating a sequence
of 3-square arithmetic progressions in order to find a magic square.
When certain conditions occur in the sequence, the procedure terminates
because it is no longer possible to satisfy the magic square requirements.
These termination conditions are proved below.
Magic Square Requirements
See the Introduction to this paper for a description of the 7-square
subset of the 3x3 magic square of distinct squares that we are studying.
For a solution to this configuration, we need to find three 3-square
arithmetic progressions having the same starting 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 L2, Mn2, Hn2
is (Hn2 - L2).
So we need to find three representations of L2 that use
(Mi,Hi), (Mj,Hj), (Mk,Hk) and that satisfy the equation
(Hi2 - L2) + (Hj2 - L2) = (Hk2 - L2).
Note that Hk must be the largest term.
Adding 2L2 to both sides gives
(4) Hi2 + Hj2 = Hk2 + L2; Hi < Hj < Hk.
Magic Square Enumeration Procedure
After finding the generators (M1,H1) ... (Mg,Hg), arranged in
increasing Hn value, then the rest of the representations can be
produced in order, one at a time, and successive values of Hn2
put into a list. The increasing order is guaranteed by the
Relative Placement Theorem.
Each a time a new Hn2 is produced, it can be checked with
combinations of Hn2 values that come before it in that list
to try and satisfy (4).
Checking is quicker than you might think. This is because,
most of the time, Hn-22 + Hn-12 < Hn2 + L2.
This means that the biggest sum that can be made
using previous Hn values is too small.
So, after just a single check, all possible combinations
using the latest Hn can be rejected.
It will also be seen below that if the sum is too small by 2L2,
that is, Hn-22 + Hn-12 < Hn2 - L2, then Hn+g, Hn+2g, etc.
can also be rejected.
When this simple case does not occur, checking combinations using Hn
can be done in at worst linear time in the length of the list.
Here is a general procedure.
Set k := n; i := 1; j := k-1
Do
Compare Hi2 + Hj2 to Hk2 + L2;
If too small, increment i;
Else If too large, 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)
Example
Let's use the L = 7 numbers above.
n 1 2 3 4 5 6 7 8 9
Hn 17 23 49 103 137 287 601 799 1673
i=1,j=2,k=3
H32 + L2 = 492 + 72 = 2450.
H12 + H22 = 172 + 232 = 818, too small by more than 2x72.
i=2,j=3,k=4
H42 + L2 = 1032 + 72 = 10658.
H22 + H32 = 232 + 492 = 2930, too small by more than 2x72,
so it's not necessary to check i=1
because the sum will be even smaller.
i=3,j=4,k=5
H52 + L2 = 1372 + 72 = 18818.
H22 + H32 = 492 + 1032 = 13010, too small by more than 2x72,
so it's not necessary to check i=1 or i=2
because the sum will be even smaller.
As the following proofs will show, we need not go any further.
Since we have 3 consecutive rejections (g = 3) and
conditions (5) and (6) below are met for each rejection,
all the rest of the H values will be rejected in the same way.
We have proved that 72 cannot be the smallest entry
in any 3x3 magic square of distinct squares.
Changing Geometric Progression Lemma
If (Mj,Hj) and (Mk,Hk) with j < k are used in (1), then
Hj+g/Hj > Hk+g/Hk
and
Mj+g/Mj < Mk+g/Mk.
Proof
If (Mj,Hj) and (Mk,Hk) with j < k are used in (1), then
Hj < Hk
thus
L2/Hj2 > L2/Hk2.
Dividing (1) by Hn2 gives
L2/Hn2 = 2Mn2/Hn2 - 1.
Substituting j and k for n and combining the above result,
2Mj2/Hj2 - 1 > 2Mk2/Hk2 - 1
or
Mj/Hj > Mk/Hk.
Using the forward recursion formula (2b) and dividing by Hn,
Hn+g/Hn = 3 + 4Mn/Hn.
Substituting j and k for n and combining the above result,
Hj+g/Hj = 3 + 4Mj/Hj > 3 + 4Mk/Hk = Hk+g/Hk,
Therefore
Hj+g/Hj > Hk+g/Hk.
Repeating the derived condition
Mj/Hj > Mk/Hk
we also have
Hj/Mj < Hk/Mk.
Using the forward recursion formula (2a) and dividing by Mn,
Mn+g/Mn = 3 + 2Hn/Mn.
Substituting j and k for n and combining the above result,
Mj+g/Mj = 3 + 2Hj/Mj < 3 + 2Hk/Mk = Mk+g/Mk.
Therefore
Mj+g/Mj < Mk+g/Mk.
Corresponding Combination Rejection Lemma
Given the values Hi, Hj, Hk from a sequence of representations
of (1) for a given L, with i < j < k,
(Case 1)
if
Hi2 + Hj2 < Hk2 - L2
then
Hi+g2 + Hj+g2 < Hk+g2 - L2;
(Case 2)
if
Hi2 + Hj2 > Hk2 + L2
then
Hi+g2 + Hj+g2 > Hk+g2 + L2.
Remark
This means that once one of the above two cases becomes true, it will also
be true for the corresponding combination of values with index offsets of
multiples of g. That is, if it's true for the combination (Hi,Hj,Hk),
then it will be true for (Hi+g,Hj+g,Hk+g), (Hi+2g,Hj+2g,Hk+2g), and so on.
All of them will produce a sum outside of the interval Hk2 ± L2,
and therefore can never satisfy (4). Therefore, it will no longer
be necessary to check those combinations in the rest of the enumeration
for a given value of L.
Proof
(Case 1)
If
Hi2 + Hj2 < Hk2 - L2,
then adding 2L2 to both sides and using (1) we get
2Mi2 + 2Mj2 < 2Mk2.
Multiplying by (Mk+g/Mk)2,
2Mi2(Mk+g/Mk)2 + 2Mj2(Mk+g/Mk)2 < 2Mk+g2.
From the Changing Geometric Progression Lemma with j < k,
Mj+g/Mj < Mk+g/Mk.
Squaring and rearranging, we get
Mj+g2 < Mj2(Mk+g/Mk)2.
Similarly, with i < k,
Mi+g2 < Mi2(Mk+g/Mk)2.
Combining the above results,
2Mi+g2 + 2Mj+g2 < 2Mk+g2
and then subtracting 2L2 from both sides and using (1),
Hi+g2 + Hj+g2 < Hk+g2 - L2.
(Case 2)
If
Hi2 + Hj2 > Hk2 + L2,
then multiplying by (Hk+g/Hk)2, we get
Hi2(Hk+g/Hk)2 + Hj2(Hk+g/Hk)2 > Hk+g2 + L2(Hk+g/Hk)2.
From the Changing Geometric Progression Lemma with j < k,
Hj+g/Hj > Hk+g/Hk.
Squaring and rearranging, we get
Hj+g2 > Hj2(Hk+g/Hk)2.
Similarly, with i < k,
Hi+g2 > Hi2(Hk+g/Hk)2.
Combining the above results,
Hi+g2 + Hj+g2 > Hk+g2 + L2(Hk+g/Hk)2,
and since Hk+g/Hk > 1,
Hi+g2 + Hj+g2 > Hk+g2 + L2.
Enumeration Termination Theorem
If for g consecutive values of Hk, (r+1 < k < r+g), for some r,
(5) H12 + Hk-12 < Hk2 - L2
and for each combination of Hi and Hj, i < j < k,
either
(6) Hi2 + Hj2 < Hk2 - L2
or
(7) Hi2 + Hj2 > Hk2 + L2,
then it is impossible for any Hi, Hj, Hk combination
where i < j < k and k > r+1, to satisfy (4) and the
magic square enumeration for the given value of L can be terminated.
Proof
If (6) or (7) applies, then we know from the Corresponding
Combination Rejection Lemma that all future corresponding
combinations will not satisfy (4).
But this doesn't cover all possible future combinations.
New combinations will be created
because there are more representations in the list.
For example, suppose (7) is met using i=2,j=k-1; the sum is too big.
Then we also know that (7) is met using i=2+g,j=k-1+g. But then,
new combinations where i=1...g+1 and j=k-1+g could have a smaller sum.
These would need to be tested -- unless you knew that (5) was met.
Then all new combinations would have a sum which was too small.
Therefore, after g consecutive rejections using the above criteria,
all combinations, old and new, can be rejected.
Example
Just for completeness, let's try the enumeration for L = 1, to prove
that the comments in the Introduction are true.
Only the first three representations are needed because g = 1.
n 1 2 3
Hn 7 41 239
i=1,j=2,k=3
H32 - L2 = 2392 - 12 = 57,120.
H12 + H22 = 72 + 412 = 1730.
Conditions (5) and (6) are met and since g = 1, we are done. Thus,
1 cannot be the lowest entry in any 3x3 magic square of distinct squares.
Example
L = 41 is the smallest value of L where condition (7) appears.
Since L is prime, g = 3. We only need the first five representations.
n 1 2 3 4 5
Hn 113 119 287 679 713
i=1,j=2,k=3
H32 - L2 = 2872 - 412 = 80,688.
H12 + H22 = 1132 + 1192 = 26,930.
Conditions (5) and (6) are met.
i=2,j=3,k=4
H42 - L2 = 6792 - 412 = 459,360.
H22 + H32 = 1192 + 2872 = 96,530.
Condition (6) is met for the largest values of i and j,
therefore condition (6) is met for all combinations,
condition (5) being one of them.
i=3,j=4,k=5
H52 + L2 = 7132 + 412 = 510,050.
H32 + H42 = 2872 + 6792 = 543,410.
Condition (7) is met, so we need to test k=5 further.
i=2,j=4,k=5
H52 - L2 = 7132 - 412 = 506,688
H22 + H42 = 1192 + 6792 = 475,202.
Condition (6) is met. All the rest of the combinations
will have lower sums than this one, so they all satisfy condition (6).
Condition (5) is also satisfied.
We have 3 consecutive rejections of all combinations, so 412 cannot
be the lowest entry in any 3x3 magic square of distinct squares.
Example
L = 71 is the smallest value of L where a value of Hk cannot be
rejected and more representations have to be generated.
Since L is prime, g = 3.
n 1 2 3 4 5 6 7
Hn 97 391 497 631 2297 2911 3689
i=1,j=2,k=3
H32 - L2 = 4972 - 712 = 241,968.
H12 + H22 = 972 + 3912 = 162,290.
Conditions (5) and (6) are met.
i=2,j=3,k=4
H42 - L2 = 6312 - 712 = 393,120.
H42 + L2 = 6312 + 712 = 403,202.
H22 + H32 = 3912 + 4972 = 399,890.
Neither condition (6) or (7) is met, so we can't reject this combination.
Since the sum is too small for (4) to be satisfied, there's no need to try
i=1,j=3 or i=1,j=2, which would make an even smaller sum.
i=3,j=4,k=5
H52 - L2 = 22972 - 712 = 5,271,168.
H32 + H42 = 4972 + 6312 = 645,170.
Condition (6) is met and thus is met by all other combinations
including condition (5).
k=6
Since all combinations of k=3 were rejected with (5) and (6), all future
combinations of k=6, k=9, etc. are also rejected and need not be tested.
i=5,j=6,k=7
H72 + L2 = 36892 + 712 = 13,613,762.
H52 + H62 = 22972 + 29112 = 13,750,130.
Condition (7) is met, so we need to test k=7 further.
i=4,j=6,k=7
H72 - L2 = 36892 - 712 = 13,603,680.
H42 + H62 = 6312 + 29112 = 8,872,082.
Condition (6) is met. All the rest of the combinations
will have lower sums than this one, so they all satisfy condition (6).
Condition (5) is also satisfied.
We now have 3 consecutive rejections of all combinations, so 712 cannot
be the lowest entry in any 3x3 magic square of distinct squares.
Example
L = 49 is not a prime and g = 5.
n 1 2 3 4 5 6 7
Hn 71 119 161 257 343 457 721
The first 5 tests all meet conditions (5) and (6), so we have
5 consecutive rejections of all combinations.
Example
L = 119 is not a prime and g = 9.
It will be found that k = 3,4,6,7,8 can't be rejected,
but k = 9 through 17 are rejected, making 9 consecutive rejections.
Part 3
Finding Generators
This part of the paper describes efficient methods for finding
generators. For large values of L, finding all the generators
can be more time-consuming than doing the calculations to search for
the magic square requirements and to reject combinations.
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 L values that need to be tested
and also reduces the number of H values that need to be searched
to find the generators. They both come from the same list.
Proof
Given
L2 = 2M2 - H2,
we factor this in the unique factorization domain Z[√2] as
L2 = (M√2 + H)(M√2 - H).
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 L, then it must also be
a factor of (M√2 + H) or (M√2 - H). 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 2H. 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 L
having prime factors of 8k+3 or 8k+5 need not be tested.
Formula for the Number of Generators
If the prime factorization of
L = paqb...rc,
then the number of generators
g = (2a + 1)(2b + 1) ... (2c + 1).
Examples
For L = 1, g = 1.
Given that p, q, r are primes:
If L = p, then g = 3.
If L = p2, then g = 5.
If L = p3, then g = 7.
If L = pq, then g = 9.
If L = p2q, then g = 15.
If L = pqr, then g = 27.
Proof
Generators Come In Pairs
If (Mn,Hn) is a generator for a given L, then so is (Mp,Hp) given by
Mp = 17Mn - 12Hn,
Hp = 24Mn - 17Hn.
Proof
We have to prove that (Mp,Hp) gives a representation of L2 using (1).
Starting with
2Mp2 - Hp2
and substituting the relation above
2(17Mn - 12Hn)2 - (24Mn - 17Hn)2
expand the terms and cancel, producing
2Mn2 - Hn2
which is equal to L2.
We also have to prove that the formula produces generators
from other generators.
If (Mn,Hn) is a generator,
then their values range from
M = L, H = L to M = 5L, H = 7L.
Thus Hp ranges between
24L - 17L and 24x5L - 17x7L
or
7L and L,
the same range as Hn when it is a generator.
Also, the case where Hp = Hn doesn't exist since if
Hn = Hp = 24Mn - 17Hn.
then
(3/4)Hn = Mn
and putting this into (1) gives
2(9/16)Hn2 - Hn2 = Ln2
or
Hn2 = 8L2
or
Hn = L√8
which can never be an integer.
The Pre-Generator Method
In the formula for the number of generators, g is always an odd number.
But Hg = 7L is always a generator.
So that leaves an even number of other generators between L and 7L.
As the above proof shows, these other generators come in related pairs.
Suppose that we have a complete set of generators for a given L,
Applying the reverse recursion to these values
produces all values less than L so that Hn-g < Mn-g < L.
All Mn-g values will be positive, but exactly half of the Hn-g values
will be negative.
If Hn > L√8, then Hn-g > 0.
If Hn < L√8, then Hn-g < 0.
If (Mn-g,-Hn-g) satisfies (1), then so does (Mn-g,Hn-g).
This means that the negative values of Hn-g and positive values of Hn-g
come in pairs of equal absolute value.
Therefore, we can do a faster search for generators by
looking for values of Hn-g in the pre-generator range 0 < Hn-g < L,
which is 1/6 the range of L < Hn < 7L.
For each of these pre-generators,
we list both positive and negative values of Hn-g.
We then put the pre-generators into the forward recursion
to get the generators. Then we add Hg = 7L to the list.
The Prime Factor Reduction also applies to these Hn-g values.
It is sufficient to list values of Hn-g that have prime factors of
only 8k+1 and 8k+7.
Example
For L = 7, g = 3.
In the range 1 ... 7, we find 1 pre-generator.
Listing both the negative and positive pre-generators.
n 1 2
Hn-g -1 1
Mn-g 5 5
Putting these through the forward recursion and adding 7L produces
n 1 2 3
Hn 17 23 49
Example
For L = 119 = 7x17, g = 9.
In the range 1 ... 119, we find 4 pre-generators.
Listing both the negative and positive pre-generators.
n 1 2 3 4 5 6 7 8
Hn-g -79 -49 -41 -17 17 41 49 79
Mn-g 101 91 89 85 85 89 91 101
Putting these through the forward recursion and adding 7L produces
n 1 2 3 4 5 6 7 8 9
Hn 167 217 233 289 391 479 511 641 833
Composition of Forms
Suppose we have already tested Lu and Lv and have saved the
list of pre-generators for each. We then come to Lw = LuLv.
We can directly compute all the pre-generators for Lw using the
lists of pre-generators for Lu and Lv.
To do this we use the following composition and scaling formulas.
(8a) Mw = (2MuMv + HuHv) - (MuHv + HuMv)
(8b) Hw = |(2MuMv + HuHv) - 2(MuHv + HuMv)|
(9a) Mw = (2MuMv - HuHv) - |MuHv - HuMv|
(9b) Hw = (2MuMv - HuHv) - 2|MuHv - HuMv|
(10a) Mw = MuLv
(10b) Hw = HuLv
(11a) Mw = MvLu
(11b) Hw = HvLu
To use the above formulas for the case where Lu and Lv have no
prime factors in common, follow this procedure.
For each (Mu,Hu),
For each (Mv,Hv),
Use (8a),(8b);
Use (9a),(9b).
For each Mu,Hu),
Use (10a),(10b).
For each (Mv,Hv),
Use (11a),(11b).
If Lw is a power of a prime, pa, then its pre-generators
can be computed from the pre-generators for Lu = p and Lv = 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 pre-generator
in each list of pre-generators for prime powers.
For a prime, there is exactly one pre-generator and it is primitive.
For a prime power, follow this procedure.
To compute the scaled pre-generators of Lw:
For each (Mv,Hv),
Use (11a),(11b).
To compute the primitive pre-generator of Lw:
If the power, a, is even
Use (8a),(8b) on both primitive pre-generators.
Else
Use (9a),(9b) on both primitive pre-generators.
Example
Lw = 72.
For Lu = 7, (Mu,Hu) = {(5,1)} and is primitive.
For Lv = 7, (Mv,Hv) = {(5,1)} and is primitive.
The power of the prime is even, so we use (8a),(8b) and (11a),(11b).
Lu Mu Hu Mv Hv Mw Hw
(8a), (8b) --> -- 5 1 5 1 41 31 (primitive)
(11a),(11b) --> 7 - - 5 1 35 7
Example
Lw = 73.
For Lu = 7, (Mu,Hu) = {(5,1)} and is primitive.
For Lv = 72, (Mv,Hv) = {(35,7), (41,31)},
the last one being primitive.
The power of the prime is odd, so we use (9a),(9b) and (11a),(11b).
Lu Mu Hu Mv Hv Mw Hw
(9a), (9b) --> -- 5 1 41 31 265 151 (primitive)
(11a),(11b) --> 7 - - 41 31 287 217
(11a),(11b) --> 7 - - 35 7 245 49
Example
Lw = 391 = 17x23
For Lu = 23, (Mu,Hu) = {(17,7)}.
For Lv = 17, (Mv,Hv) = {(13,7)}.
Lu Lv Mu Hu Mv Hv Mw Hw
(8a), (8b) --> -- -- 17 7 13 7 281 71
(9a), (9b) --> -- -- 17 7 13 7 365 337
(10a),(10b) --> -- 17 17 7 -- - 289 119
(11a),(11b) --> 23 -- - - 13 7 299 161
Example
Lw = 19159 = 49x391 = 72x(17x23)
For Lu = 49, (Mu,Hu) = {(41,31),(35,7)}.
For Lv = 391, (Mv,Hv) = {(281,71),(289,119),(299,161),(365,337)}.
Lu Lv Mu Hu Mv Hv Mw Hw
(8a), (8b) --> -- --- 41 31 281 71 13621 1999
(8a), (8b) --> -- --- 41 31 289 119 13549 289
(8a), (8b) --> -- --- 41 31 299 161 13639 2231
(8a), (8b) --> -- --- 41 31 365 337 15245 9887
(8a), (8b) --> -- --- 35 7 281 71 15715 11263
(8a), (8b) --> -- --- 35 7 289 119 14875 8687
(8a), (8b) --> -- --- 35 7 299 161 14329 6601
(8a), (8b) --> -- --- 35 7 365 337 13559 791
(9a), (9b) --> -- --- 41 31 281 71 15041 9241
(9a), (9b) --> -- --- 41 31 289 119 15929 11849
(9a), (9b) --> -- --- 41 31 299 161 16859 14191
(9a), (9b) --> -- --- 41 31 365 337 16981 14479
(9a), (9b) --> -- --- 35 7 281 71 18655 18137
(9a), (9b) --> -- --- 35 7 289 119 17255 15113
(9a), (9b) --> -- --- 35 7 299 161 16261 12719
(9a), (9b) --> -- --- 35 7 365 337 13951 4711
(10a),(10b) --> -- 391 41 31 -- -- 16031 12121
(10a),(10b) --> -- 391 35 7 -- -- 13685 2737
(11a),(11b) --> 49 --- - - 281 71 13769 3479
(11a),(11b) --> 49 --- - - 289 119 14161 5831
(11a),(11b) --> 49 --- - - 299 161 14651 7889
(11a),(11b) --> 49 --- - - 365 337 17885 16513
Finding Pre-Generators For Primes
The Pre-Generator Method reduces the problem from scanning for generators
in the range L ... 7L to instead scanning in the 1/6 size range 0 ... L.
The Composition of Forms reduces the problem to scanning for pre-generators
only for primes, while pre-generators for composites are directly computed.
This section shows how to further reduce the work in finding the pre-generator
for a prime by scanning in the much smaller range 0 ... √L.
Also, since there is only one pre-generator for a prime,
once you find it, you can stop scanning.
Instead of looking for a representation for L2,
look for the representation,
L = 2m2 - h2,
then use a version of the composition formulas to compute
the pre-generator for L2.
(12a) M = 2m2 + h2 - 2mh
(12b) H = |2m2 + h2 - 4mh|
Examples
L m h M H L m h M H
7 2 1 5 1 89 7 3 65 23
17 3 1 13 7 97 7 1 85 71
23 4 3 17 7 103 8 5 73 7
31 4 1 25 17 113 9 7 85 41
41 5 3 29 1 127 8 1 113 97
47 6 5 37 23 137 9 5 97 7
71 6 1 61 49 151 10 7 109 31
73 7 5 53 17 191 10 3 149 89
79 8 7 65 47 199 10 1 181 161
Remark
Here are some observations that lead to some extra time savings.
All the h values are odd. An m value is odd when L = 8k+1.
An m value is even when L = 8k+7. Will this always be true?
Proof
We have
h2 = 2m2 - L.
2m2 is even and L is odd, therefore h must be odd.
The square of an odd number has the form 8k+1.
The square of an even number has the form 8k or 8k+4.
We have
2m2 = L + h2.
Since h is odd, h2 has the form 8k+1.
If L has the form 8k+1, then 2m2 must have the form 8k+2, and m must be odd.
If L has the form 8k+7, then 2m2 must have the form 8k, and m must be even.
Part 4
Future Research
This part of the paper contains ideas for extending the results to larger
numbers, determining places where a magic square might be hiding, and
for proving the impossiblity of the full 9-square problem.
Extending the Results
The enumeration described in the Introduction was performed using the
Pre-Generator Method, but without the Composition of Forms or √L
Prime scanning. Thus, looking for pre-generators consumed most of the time.
So the enumeration was aborted after examining values of L up to 7 digits.
Using the new methods should speed up the operation enough so that much
larger values for L can be tested. A new implementation would require
a technique to build values of L from a list of 8k+1/8k+7 primes,
similar to the technique that Christian Boyer used in his search.
I look forward to an independent verification of my results and a
possible extension of it, possibly even finding a magic square.
Magic Square Search Ideas
Here are some ideas for trying various values of L to try and find a
magic square without enumerating everything.
The best value of L to use for finding a magic square would be one that
had a lot of different small prime factors. This is because the density
of H values would be greatest, increasing the chance for (4) to be met.
Using higher powers of the same prime does not increase the density
as much as different primes. This can be seen from the formula for the
number of generators.
A procedure to search for a magic square is to try values of L in the
following sequence,
7, 7x17, 7x17x23, 7x17x23x31, etc.
including the next prime for each search.
The idea is that if there is a solution using a subset of these primes,
then you would find a scaled version of the solution. So there is no need
to try every subset when you can do them all at once.
Make sure you have your giant integer arithmetic package ready.
Impossibility Proof Ideas
In order to prove that the full magic square of 9 squares is impossible,
it is sufficient to prove restrictions on its 7-square subsets.
If the restrictions are mutually exclusive, then they can't coexist in
a 9-square solution at the same time.
The results of this study suggest a restriction conjecture because the
termination condition occurs so early. If it can be proved that the
termination will occur before H3g, for example, then there is an
upper limit to the ratio of the highest entry to the lowest entry.
If there exists another 7-square configuration, which also includes the
highest and lowest entries from the 9-square problem, and it shows that
there is a lower limit to this same ratio that is greater than the
upper limit, then the 9-square problem would be proved impossible.