This page is designed to make available some material on 3x3 distinct prime magic squares, for use by: fans of magic squares and prime numbers, and possibly even serious number theorists. More importantly, this material can be used to introduce the concept of algorithmic complexity to novices - this page will be updated in June to include such material.
What is a 3x3 distinct prime magic square?
It's exactly what it sounds like: a collection of 9 distinct prime numbers organised into a 3x3 grid in such a way that all of the rows, columns, and diagonals sum to the same value (which is three times the value at the centre of the grid).
Why study 3x3 distinct prime magic squares?
That's a good question. I wrote the prime number generator long ago as a coding exercise, and the 3x3 distinct prime magic square generator was written to answer a puzzle in the department newsletter. I was surprised at how many such squares there are, so just left the generator running.... it eats cycles quietly on my workstation and happily churns out new squares. Whether anyone else is interested in these squares isn't clear, but I thought I'd put the material up on the web in case anyone wanted to look at them. The algorithmic content is useful in that it makes a nice example of how vastly improved algorithms can follow from a deeper understanding of a problem.
If you are aware of an application of these squares in any problem area, or of interesting mathematical observations concerning these squares, please do let me know. I'm not currently aware of any practical use for them whatsoever!
What's available on this page?
The material here is mostly associated with three small programs:
The first two programs take very little time at all to run, the generators are resource hungry, but their output is made available through this page, for those who are interested. All of the programs will be publicly available under the GPL. (They'll be downloadable from here when I get around to fixing up the files to include the GPL statements)
And please let me know (at email@example.com) if you find this material interesting or useful for anything other than a mathematical amusement. Serious mathematicians who'd like simple analyses done on the squares found so far are welcome to contact me with suggestions. This is a low priority background activity, but I'm open to suggestions for analyses that might expose interesting patterns amongst the results.
A number of properties of 3x3 distinct prime magic squares are used to reduce the work required of the generating program. For example:
The row total of a 3x3 magic square is three times the centre value.
Proof of Lemma 1:
Consider the four "lines" (1 row, 1 column and 2 diagonals) that pass through the centre. Summing them gives a total of 4 times the row total, and it includes the centre value 4 times and all other values once. Adding all the values together once is the same as summing the three rows, i.e. it gives three times the row total, so the additional three centre values must sum to the row total also.
There are only two ways of laying out nine distinct values that can possibly form a 3x3 magic square - all other layouts are guaranteed not to be a magic square.
Sketch of proof of Lemma 2:
This was proven by a constructive technique - all possible ways of laying out the nine values were considered (using symmetry to reduce the number of cases). In each case, we sought out rows, columns and diagonals in which it was guaranteed that one must exceed another. For example if the 9 symbols 1st,2nd,3rd,4th,5th,6th,7th,8th,9th are used to represent the nine distinct values in ascending sequence, any square in which one row contains (say) 1st,4th,7th and another contains (say) 2nd,5th,8th is guaranteed not to be a magic square as the 2nd, 5th & 8th values must sum to more than the 1st, 4th & 7th.
Results of program proving Lemma 2:
The two potential layouts for a 3x3 distinct magic square are:
6th 7th 2nd
1st 5th 9th
8th 3rd 4th
7th 6th 2nd
1st 5th 9th
8th 4th 3rd
where 1st..9th represent the nine values in ascending order. Here are examples of each form:
71 89 17
5 59 113
101 29 47
103 79 37
7 73 139
109 67 43
Some trivial observations on the distribution of the squares and how long it took to find them using the O(N^3) variant:
Some trivial observations on the distribution of the squares and how long it took to find them using the O(N^5) variant:
Some trivial observations on the distribution of the squares and how long it took to find them using the O(N^9) variant:
To be written.... but it's a LOT faster than the O(N^5) variant.
The construction of the squares began on Monday 5th February 2001, with around 200 squares being generated in the first second. By Friday 16th February 2001, nearly 300,000 squares had been found, with the largest prime used in a square being 41443. Getting that far had used over 11 days of CPU time on an old DEC Alpha 3000 running OSF. The 750,000th square was found on Friday April 20th 2001, by which time over 73 days of CPU time had been consumed.
Since the O(N^5) program is structured as a five-deep nesting of for-loops, the program is slowing dramatically and will not generate significantly more squares than have already been found. It'll be left running as a background task though, so some further progress can be expected.
The data has been formatted into a multi-volume listing of some of the squares. These are being made available as I get round to processing them. To construct a volume: acquire a copy of the relevant front cover, the background sheet and the volume contents from here.
The simplest and most naive program consists of a nine-deep nesting of loops. It simply generates all possible sets of nine distinct prime numbers and checks whether they forma magic square. The performance is, as you'd expect, appalling. It took five seconds to find the first two values, and a whole weekend to find about two dozen valid squares.
The second variant is loosely based on the first. However the fact that opposite pairs in the magic square must sum to twice the centre value is used to reduce the amount of work done - this five-deep nesting of loops performs noticeably better than the naive one, and was used to generate the first 800,000 3x3 distinct prime magic squares as described above.
There is, however, a much more efficient algorithm. This uses the fact that a 3x3 magic square can be fully defined by two parameters and the centre value. The parameters correspond to (p5-p2) and (p2-p1) where p1, p2 and p5 are the first second and fifth values in ascending order. (There are other equivalent derivations). This leads to a three-deep nesting of loops and an O(N^3) algorithm. It was developed after the second program had been left running for over two months, and when first run generated 55,920 squares in the first 3 minutes whilst running in parallel with the O(N^5) algorithm - i.e. whilst sharing the same CPU. The O(N^5) program took 9.5 hours to generate that many squares with the same CPU to itself.
Incidentally, generating each of these programs took around 1.5-2.5 hours, including debugging and checking of initial results, they aren't especially complicated. They do, however, provide an alternative to the standard examples of sorting to illustrate algorithm complexity. They further show that a more efficient algorithm need not involve more complex code.
The code is all available here, with no warranty expressed or implied (not least because the code was written in a hurry and isn't exactly perfect!). I retain all copyright etc in it, so please don't try to make money from it :-)
Page created and maintained by
Dr Peter Dickman
Department of Computing Science
University of Glasgow.
Last modified on 20th April 2001
(with a minor improvement to the presentation in December 2003 thanks to input from the Fitzsimon family in Brisbane, and a slight tidy up in May 2007).