Searching for a Magic Square of Squares

I've wanted to try running software on the GPU for a couple years now, and had been considering ideas like drawing fractals or running neural networks. But after watching a recent Numberphile video on YouTube, I just had to see if I could apply the power to the GPU to searching for magic squares.

 

A "magic square" is a square arrangement of numbers where the rows, columns, and long diagonals all sum to the same value. Trivial examples include, of course, any square like:

5	5	5
5	5	5
5	5	5

where all the values are the same. Generally, we ignore any square containing any repeated digits.

As explained by Matt Parker in the Numberphile video, it is, counter intuitively, easier to find larger magic squares than smaller ones. This example $8\times 8$ magic square he shows was first published in 1890!

56	34	8	57	18	47	9	31
33	20	54	48	7	29	59	10
26	43	13	23	64	38	4	49
19	5	35	30	53	12	46	60
15	25	63	2	41	24	50	40
6	55	17	11	36	58	32	45
61	16	42	52	27	1	39	22
44	62	28	37	14	51	21	3

Pfeffermann, 1890. All rows, columns, and diagonals sum to 260.

This square also has another property that makes it even more special: it remains a magic square when all the values are squared! All rows, columns, and diagonals sum to 11,180 when the values are squared.

The first known $4\times 4$ magic square of squares was discovered by Euler in 1770:

68²	29²	41²	37²
17²	31²	79²	32²
59²	28²	23²	61²
11²	77²	8²	49²

Euler, 1770. All rows, columns, and diagonals sum to 8,515.

The Challenge

a²	b²	c²
d²	e²	f²
g²	h²	i²

It's apparently so much harder to find a $3\times 3$ magic square of squares than a $4\times 4$ that nobody has ever done it, and it's possible that none exist. This page has a detailed breakdown of the search.

Toward the end of the video a $10,000 prize was announced for anyone who finds a $3\times 3$ square of squares, but for me it was fun just to see whether a GPU-based program would be faster than a CPU-based one.

After some experimentation with rust and the metal crate, I've got both CPU and GPU solutions working on my Apple Silicon Mac. My algorithm is a simple exhaustive search with "checkpointing" so I can halt and resume the search as needed. The GPU one seems to run about 2.4x faster than the CPU one.

My plan is to run a search with a relatively small maximum root, and then, depending on how long that takes, run another search with a larger maximum root (without repeating any previously examined squares). I've allowed the search to return any "near miss" squares found, where one row or column or diagonal doesn't have the same sum as the rest. I'll list my program's best found squares below.

3×3 Status and "Near Miss" Squares

While searching for magic square solutions, we'll come across many "near miss" squares with one row, column, or diagonal sum that doesn't match the others. I'll list the ones my program finds below. Many of them of course have been previously found, but I'd still like to list them here as my program comes across them. I'll try to omit any squares that mirror or rotate an already listed one.

March 31, 2025:

2² 94² 113² 127² 58² 46² 74² 97² 82²

Sums of 21,609 with one diagonal sum of 10,092.

April 1, 2025:

4² 188² 226² 254² 116² 92² 148² 194² 164²

Sums of 86,436 with one diagonal sum of 40,368.

April 2, 2025:

46² 82² 113² 127² 74² 2² 58² 97² 94²

Sums of 21,609 with one diagonal sum of 16,428.

April 2, 2025:

58² 46² 127² 94² 113² 2² 97² 82² 74²

Sums of 21,609 with one diagonal sum of 38,307.

April 3, 2025:

92² 164² 226² 254² 148² 4² 116² 194² 188²

Sums of 86,436 with one diagonal sum of 65,712.

April 3, 2025:

116² 92² 254² 188² 226² 4² 194² 164² 148²

Sums of 86,436 with one diagonal sum of 153,228.

April 3, 2025:

My exhaustive search with a maximum root of 256 has completed. I am pretty confident there are no magic squares of squares where all the values (roots) are less than or equal to 256.

April 5, 2025:

6² 282² 339² 381² 174² 138² 222² 291² 246²

Sums of 194,481 with one diagonal sum of 90,828.

April 6, 2025:

8² 376² 452² 508² 232² 184² 296² 388² 328²

Sums of 345,744 with one diagonal sum of 161,472.