MULTIMAGIE.COM - Wroblewski-Pfoertner magic squares, orders 42 and 44

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:

first known magic square of cubes of prime numbers
first known magic square of fourth powers having an order smaller than 243

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
The second problem and its context
The Wroblewski's work on semi-magic solutions
The Pfoertner's final work on the diagonals
The solutions with the two magic squares (downloadable Excel files)

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:

The smallest 4×4 magic square of squares of prime numbers,
S2 = 509,020, by C. Boyer
29²	191²	673²	137²
71²	647²	139²	257²
277²	211²	163²	601²
653²	97²	101²	251²

The smallest 5x5 magic square of squares of prime numbers,
S2 = 34,229, by C. Boyer
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.

Smallest known magic squares of powers
(before the Wroblewski-Pfoertner's square of 4th powers)
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 Pan Fengchu, 2004)
of 5th powers	Unknown!	729x729 (from the pentamagic square of Li Wen, 2003)

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.

First known and smallest known
4x4 semi-magic square of fourth powers
S4 = 2,072,924,729,248,210,594,
by L. Morgenstern - C. Boyer
14101⁴	938⁴	931⁴	37762⁴
35866⁴	20881⁴	21038⁴	13393⁴
24806⁴	30191⁴	30418⁴	9263⁴
413⁴	32026⁴	31787⁴	1106⁴

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".

S42.TXT, a 42x42 semi-magic square of cubes of consecutive prime numbers (from 11^3 to 1537^3, S3 = 33151363766492)
S44.TXT, a 44x44 semi-magic square of consecutive fourth powers (from 1^4 to 1936^4, S4 = 123784061778806)

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:

Download the 42x42 magic square of cubes of prime numbers (zipped Excel file, 69Kb)
Download the 44x44 magic square of 4th powers (zipped Excel file, 34Kb)

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:

*Status in October 2007 of smallest known magic squares of powers*
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 of Li Wen, 2003)

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