# The 3x3 Distinct Prime Magic Squares Page

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!

The material here is mostly associated with three small programs:

• A reasonably efficient prime number generator based on the Sieve of Eratosthenes
• A trivial program that demonstrates that there can only be two sorts of 3x3 magic squares containing nine distinct primes
• Several variations of a program that exhaustive constucts 3x3 distinct prime magic squares

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)

Enjoy!
And please let me know (at pd@dcs.gla.ac.uk) 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.

## Background Mathematics

A number of properties of 3x3 distinct prime magic squares are used to reduce the work required of the generating program. For example:

Lemma 1:
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.

Lemma 2:
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

and:

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

## Observations on the results

Some trivial observations on the distribution of the squares and how long it took to find them using the O(N^3) variant:

• This version generated 800,000 magic squares containing distinct primes in about 50 CPU minutes on an old Alpha - the same feat took the O(N^5) algorithm over 80 CPU days.
• After 10.5 CPU hours this program had found approaching 6,000,000 squares.

Some trivial observations on the distribution of the squares and how long it took to find them using the O(N^5) variant:

• All 3x3 distinct prime magic squares containing only primes less than 10,000 were found in the first 45 minutes (approximately), there are 15,817 such squares in all.
• More than 150,000 3x3 distinct prime magic squares exist containing primes less than 30,000; it took around 3 days to find all of them.
• There are 171 different 3x3 distinct prime magic squares that have 27691 as the largest prime in them.
There are more interesting questions and observations though, for example:
• There don't seem to be any 3x3 distinct prime magic squares that include the value 3. Is this a bug in the generator or a real fact? And if it is true, can anyone prove it in general? In fact there's a fairly simple proof by failed construction.
• A much more interesting question is whether there are any other primes which cannot appear as the least prime in a 3x3 distinct prime magic square?
• There are certainly primes which don't appear as the largest in a square, including:
all the primes under 113, 127, 131, 137, 149, 151, 157, 163, 173, 179....
Indeed it would appear that relatively few primes appear as the largest in a square. Do they have a distinguishing property?

Some trivial observations on the distribution of the squares and how long it took to find them using the O(N^9) variant:

• It took four seconds for this version to find the first two squares, and after 300 CPU hours it had found just 49....

## Performance timings of the O(N^3) variant

To be written.... but it's a LOT faster than the O(N^5) variant.

## Performance timings of 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.

## Accessing the Data

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 Variant Programs

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 at the Department of Computing Science at the University of Glasgow.
EMail: pd@dcs.gla.ac.uk