Magic square of cubes of prime numbers, order 42
Magic
square of fourth powers, order 44
In 2007, Jaroslaw Wroblewski (University of Wroclaw, Poland) and Hugo Pfoertner (MTU Aero Engines, Germany) solved two interesting and very difficult problems:
Their magic square #1 solves one of my open problems published in The Mathematical Intelligencer in 2005. And their magic square #2 greatly improves the previous record, their order 44 being far smaller than 243. Here is the story of their discoveries, five parts in this page:
The first problem and its context
In 2005, I gave these first known 4x4 and 5x5 magic squares of squares of prime numbers in the Supplement of my paper on magic squares of squares published in The Mathematical Intelligencer:
29² |
191² |
673² |
137² |
71² |
647² |
139² |
257² |
277² |
211² |
163² |
601² |
653² |
97² |
101² |
251² |
11² |
23² |
53² |
139² |
107² |
13² |
103² |
149² |
31² |
17² |
71² |
137² |
47² |
67² |
61² |
113² |
59² |
41² |
97² |
83² |
127² |
29² |
73² |
7² |
109² |
What is more difficult than magic squares of squares? Magic squares of cubes! That's why, among the 10 open problems published in my paper, I asked this one:
Open problem 6 - Construct a magic square of cubes of prime numbers
Two years after its publication, Wroblewski and Pfoertner will be the first to solve this problem!
The second problem and its context
Started by Leonhard Euler in 1770 with his 4x4 magic squares of squares, and later by Edouard Lucas in 1876 with his unsuccessful search of 3x3 magic squares of squares, the smallest possible magic square of any power is an extremely difficult problem: ON ANY POWER > 1, WE DO NOT KNOW WHAT THE SMALLEST POSSIBLE MAGIC SQUARE IS! We don't know if a 3x3 magic square of squares is possible. We don't know if 4x4 or 5x5 or 6x6 or 7x7 or 8x8 magic squares of cubes are possible, and so on...
Before the Wroblewski-Pfoertner square, the smallest known magic square of 4th powers was coming from the 243x243 tetramagic square of Pan Fengchu (see the Multimagic records): when the numbers of a tetramagic square are squared, or are cubed, or are raised to the 4th power, the magic square is still magic.
Magic square |
Smallest possible |
Smallest known |
of squares |
Unknown! Maybe 3x3? |
4x4 (L. Euler, 1770) |
of cubes |
Unknown! Maybe 4x4? |
9x9 (C. Boyer, 2006) |
of 4th powers |
Unknown! |
243x243 (from
the tetramagic square |
of 5th powers |
Unknown! |
729x729
(from the pentamagic square |
If we don't take care of the diagonals (meaning searching semi-magic squares instead of magic squares), then we know some answers on the smallest possible question. For example we know 3x3 semi-magic squares of squares, and 4x4 semi-magic square of cubes. On our problem here with 4th powers, we know 4x4, 8x8, 9x9 semi-magic squares.
14101^{4} |
938^{4} |
931^{4} |
37762^{4} |
35866^{4} |
20881^{4} |
21038^{4} |
13393^{4} |
24806^{4} |
30191^{4} |
30418^{4} |
9263^{4} |
413^{4} |
32026^{4} |
31787^{4} |
1106^{4} |
The gap between the smallest known semi-magic and magic squares of 4th powers was incredibly large: 4x4 versus 243x243. My question asked in this website was:
Who will construct a magic square of 4th powers smaller than 243x243?
Wroblewski and Pfoertner will be the first to solve this problem!
The Wroblewski's work on semi-magic solutions
Jaroslaw
Wroblewski (Wroclaw 1962 -)
playing during the "LVII Olimpiada Matematyczna" of Poland, in
2006. Click on the image to enlarge it.
Jaroslaw Wroblewski & Jean-Charles Meyrignac was the winning team of the Al Zimmermann's programming contest of March-May 2007 called "searching Kurchan pandiagonal multiplicative squares". They won the three parts of the contest: look at http://www.recmath.org/contest/Kurchan/index.php. Previously, in February 2006, Jaroslaw Wroblewski was the first person able to construct a bimagic square smaller than 8x8: a long-awaited result, since 1890! Look at his 6x6 bimagic square.
Reusing his winning code of the Zimmermann's contest, but modified for the two above problems, he succeeded to produce two semi-magic squares, June 6th 2007. As he said, it is a "byproduct of the contest".
Here are some of his comments on the used method for S42.TXT:
1) Pick the primes so that the magic sum = (sum_of_primes)/(matrix_size)
is integer and of the same parity as the square size (primes are odd).
2)
Place the entries at random and keep optimizing.
My optimizing routine
takes 2 rows and swaps some of the entries in those rows so that no entry
changes it's column and one of the rows gets as close to magic sum as possible.
Alternately it takes 2 columns and does a similar optimization on them.
Apparently it converges to a semi-magic square when the terms are well below
2^(matrix_size). Currently I can work on sizes up to 51, perhaps I could
get a bit higher, but it would require writing another routine.
I strongly
believe that it is possible to permute rows and columns to get both diagonals
magic, but at the moment I have no program that could do that.
These semi-magic squares are not magic squares. Who would be able to find two magic diagonals? This difficult problem will be solved by Hugo Pfoertner.
The Pfoertner's final work on the diagonals
Hugo Pfoertner (Rosenheim 1950 -)
Photo of a conference of the NATO
Research and Technology Organization, Budapest, 2005. Click on the image to enlarge it.
As Jaroslaw Wroblewski, Hugo Pfoertner was also an excellent competitor on the three parts of the same Al Zimmermann's contest: his final placings are 13th (maximal part), 5th (minimal part), and 4th (Kurchan part). Hugo is employed in the research and development of MTU Aero Engines, Germany. In his leasure time, he enjoys solving mathematical problems using computers: look at www.pfoertner.org.
Finding two magic diagonals in a semi-magic square is a very difficult task. Imagine that there are 44! = 2.66*10^54 possible diagonals in a 44x44 semi-magic square, and that the probability to discover two crossing diagonals having the correct sum, as big as 123784061778806 for the 44x44, is extremely low.
Hugo Pfoertner started on the smaller square, 42x42, and one month later succeeded to find two good diagonals, July 9th: the first problem was solved! For this first found square, the total CPU time was four weeks on up to ten CPUs (Itanium-2 or 3.4GHz Pentium).
And October 8th, 2007, I received this message from Hugo:
The 44X44 4th-power square problem is now solved. It took a rather
massive computational effort to find the required permutations. Searching
for the correct diagonal by row permutations started on June 11 and produced
a matching matrix on August 27. Using this matrix as a starting point, simulaneous
row/column permutations produced a matching anti-diagonal on October 7.
Most
of the time the permutation program was running on 57 Processors of a 5
years-old SGI machine http://www.sgi.com/products/remarketed/origin3000.
This computer, which was scheduled for retirement, used to be one of the
workhorses in MTU's R&D department. Due to its planned disassembly only
a minor regular workload had remained on the machine. Additionally the idle time on 14 Processors of SGI Altix machines was used
http://www.sgi.com/products/remarketed/altix350.
The accumulated CPU times to find a matrix with matching diagonal were 148
CPU months on Origin 3000 processors and 22.4 CPU month on the Itanium-2
processors of the Altix machines. Finding the correct antidiagonal took
80 CPU months on the Origin 3000 and 17.5 CPU months on the Altix 350.
In
total 18.8 CPU years were spent on the Origin 3000 and 3.3 CPU years
on the Altix 350. The resulting magic square is probably one of the more
expensive members of this species ;-)
Hugo Pfoertner thanks his employer, MTU Aero Engines, for giving him access to these significant computational resources.
http://www.mtu.de/en/index.html
The solutions with the two magic squares
Here are these two excellent and impressive Wroblewski-Pfoertner's squares:
With their first square, my Open problem 6 is now solved. And with their second square, the table of the records seen above can now be updated:
Magic square |
Smallest possible |
Smallest known |
of squares |
Unknown! Maybe 3x3? |
4x4 (L. Euler, 1770) |
of cubes |
Unknown! Maybe 4x4? |
9x9 (C. Boyer, 2006) |
of 4th powers |
Unknown! |
44x44 (J. Wroblewski - H. Pfoertner, 2007) |
of 5th powers |
Unknown! |
729x729
(from the pentamagic square |
But maybe other people will try to improve their results, with squares smaller than 44x44 or 42x42? If yes, send me a message!
As a (temporary?) conclusion, some remarks from Jaroslaw:
It is known that there exist 12x12 magic-square-of-cubes-of-primes,
but the proof is not constructive (take the known trimagic
12x12; take 144 primes in arithmetic progression that exist by
Green-Tao
theorem; then replace each number 'n' in trimagic with 'n'-th
term of the progression).
At the moment I do not see how one could significantly
decrease 42x42 size of known example with the approach I used.
IMPORTANT! The above status of 2007 has now changed, with new smaller magic squares of cubes, 4th powers and 5th powers! Look here.
Return to the home page http://www.multimagie.com