Primes in a magic square
A magic square is an arrangement of integers in a square grid, where the numbers in each row, column and main diagonal all add up to the same number, which is called the magic sum .
If we use 9 distinct numbers from 1 to 27 to make a 3 by 3 magic square, what is the most number of primes that we can use?
Details and assumptions
You may use the fact that there are 9 prime numbers from 1 to 27.
The answer is 7.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
4 solutions
Brilliant observation!
You have written - "this one other number must be 1 mod 3. So it is 1 mod 6"
Why did you change mod 3 to mod 6 ?
Yonsatron writing the solution.
Any number can be taken as long as the common difference between each term are the same. There are 9 numbers within 27, these are 2, 3, 5, 7, 11, 13, 17, 19, 23. Let take odd numbers from 3 to 19 with common difference 2. Hence, there are a maximum of 7 primes in this square.
How did you do that? I could only did 4.
How do you know that you can't use all 9? Or 8 of them?
Label the squares going left to right, then down, with a, b, c... By messing around with algebra we see that each corner is the average of the opposite two side squares, for instance, a=(f+h)/2, and that the center square is the average of the numbers in the same row of column, e.g. e=(b+h)/2; thus we see all the pairwise sums of b, d, f, and h are even. Either they are all odd or all even, but we want lots of primes, so say they are even. Guess and check with different pairs of numbers eventually gives 7 primes, with side squares 3, 23, 7, and 19
The magic square is as follows
17 3 13
7 11 15
9 19 5
Can you prove that there is not a magic square with more than seven primes?
Can you explain. Why is that?
You have to find terms with a common difference, and by observation, the common difference amongst the primes appearing the most is 2 (with 7 primes having that, e.g. 5 − 3 = 2 . So using 3 as the starting integer, A, and the common difference between the terms, D=2 and that the magic square is a 3x3 (NxN), you sub in these values into the magic constant equation: s = N ( 2 A + D ( N 2 + 1 ) ) / 2 , where s is the sum of each main diagonal, row and column. You will derive s = 3 3 and you can rearrange the 9 numbers with D of 2 (3,5,7,9,11,13,15,17) into the magic square above.
Log in to reply
I disagree with the claim that all the terms must have a common difference.
(Initial example was incorrect. I have changed it to a square with magic sum of 177, using 9 prime numbers.)
For example,
1 7 1 1 3 4 7 8 9 5 9 2 9 7 1 5 1 0 1
is a magic square where the entries jump around some. You can see that it is formed by sequences of primes which differ by 12 (and hence we know that the sum is constant without having to check each sum), but we don't have a complete AP.
Log in to reply
The main diagonals don't add up to the magic sum in your counter example
Log in to reply
@Siddhartha Srivastava – Indeed, thanks for pointing that out! I've updated the example.
Oh ... Sorry my bad!
or you can brute force it, leave it running all night, and see that it won't get past 7 primes. //magicprimes.c #include <stdio.h> #define true 1 #define false 0
int isPrime(int n) {
int i;
for (i=1; i<n; i++) {
if (n % i == 0 && i!=1) {
return false;
}
}
return true;
};
int countPrimes(int l[]) {
int n = 0;
int i = 0;
for(i=0; i < 9; i++) {
if (isPrime(l[i])) {
n++;
}
}
return n;
}
int areDistinct(int a, int b, int c, int d, int e, int f, int g, int h, int i) {
return a!=b && a!=c && a!=d && a!=e && a!=f && a!=g && a!=h && a!=i &&
b!=c && b!=d && b!=e && b!=f && b!=g && b!=h && b!=i &&
c!=d && c!=e && c!=f && c!=g && c!=h && c!=i &&
d!=e && d!=f && d!=g && d!=h && d!=i &&
e!=f && e!=g && e!=h && d!=i &&
f!=g && f!=h && f!=i &&
g!=h && g!=i &&
h!=i;
}
int areMagic(int a, int b, int c, int d, int e, int f, int g, int h, int i) {
return a+b+c == d+e+f && d+e+f == g+h+i && a+d+g == b+e+h && b+e+h == c+f+i && a+e+i == c+e+g && a+e+i == a+b+c;
}
int main(char** args, int nArgs) {
int MAX = 28;
int solutions=0;
int maxPrimes=0;
int a=0;
int b=0;
int c=0;
int d=0;
int e=0;
int f=0;
int g=0;
int h=0;
int i=0;
int p=0;
for (a=1; a < MAX; a++) {
for (b=1; b < MAX; b++) {
for (c=1; c < MAX; c++) {
for (d=1; d < MAX ; d++) {
for (e=1; e < MAX; e++) {
for (f=1; f < MAX; f++) {
for (g=1; g < MAX; g++) {
for (h=1; h < MAX; h++) {
for (i=1; i < MAX; i++) {
if (areDistinct(a,b,c,d,e,f,g,h,i)) {
if (areMagic(a,b,c,d,e,f,g,h,i)) {
int l[9] = {a,b,c,d,e,f,g,h,i};
solutions = solutions + 1;
printf("(%d,%d,%d,\n%d,%d,%d,\n%d,%d,%d)\n\n",a,b,c,d,e,f,g,h,i);
p = countPrimes(l);
if (p > maxPrimes) {
maxPrimes = p;
}
printf("countains %d primes\n", p);
printf("max primes ever used: %d\n\n",maxPrimes);
}
}
}
}
}
}
}
}
}
}
}
}
Log in to reply
wish I had the time to optimize this solution. I gave it a try, basically by trying to determine if there were any repeated numbers in the current iteration but I failed to implement this logic correctly.
Then at some point I figured I could've done it using trees and maybe some sort of search within the tree, but my ideas aren't so clear as to how to achieve this. Would love to discuss an algorithmic solution that's not as ridiculously innefficient as the one above (which would probably take years to finish)
Log in to reply
Any idea what is the smallest magic sum for a magic square which uses 9 prime numbers? I gave an example of a magic square which has 9 primes, so the answer is finite.
Here's why you can't have 8 or 9 primes in the magic square.
The case of 9 primes is easy since the sum of all 9 primes from 1 to 27 is 100, and not a multiple of 3.
For 8 primes, first observe that 2 can't be included. Indeed if 2 were the only even number, then the row containing it has an even sum while the other two rows have odd sums. Otherwise there is at most one other even number. These two even numbers must be in different rows or different columns. In the former case, the two rows would have even sums while the remaining row has an odd sum (contradiction); the latter case is similar.
So we must have 3, 5, 7, 11, 13, 17, 19, 23 and one other number (which must be odd, by the same reasoning as in the previous paragraph). Since the sum of all nine numbers is a multiple of 3, this one other number must be 1 mod 3. So it is 1 mod 6, and can only be 1 or 25 since all the rest have been used.
The case of 1 gives us a problem: the sum of each row/column must be 99/3 = 33. Now consider the row and column containing 23. One of them must be 3+7+23 = 33, and the other has no solution.
The case of 25 is also problematic: the sum of each row/column is 41. Consider the row and column containing 3. One of them must be 3+13+25 while the other has no solution.