Problems & Puzzles: Puzzles
Puzzle 266. Magic rectangles
By analogy to the 'magic squares', a rectangular matrix rxc (r=quantity of rows; c = quantity of columns) filled with the consecutive integers from 1 to r.c, is called 'magic' if the elements of every row sum up to the same integer R, and the elements of every column sum up to the same quantity C.
Necessarily the sum S of all the integers of a rectangular square are related to R and C as follows:
S = r.R = c.C
Only if the rectangle is filled with the integers from 1 to r.c S is given by:
S = r.c(r.c+1)/2
The Professor Marián Trenkler, in a round article published in 1999 (see his paper 19) has obtained the basic and fundamental results nowadays known for these mathematical objects, which I summarize in the following lines:
Despite of the great achievement that represent the results mentioned above, there are many (r, c) simple combinations for which we can not assure (decide) that a Magic rectangle exists and/or how to produce them by regular smart/simple procedures.
For example there is not a theorem in which to base the affirmation of the existence (or the inexistence) of (3, 5) and (3, 7) magic rectangles. Nevertheless they exist! (please see them in the Professor Trenkler's paper.
All this discussion is about rectangular matrixes filled with numbers form 1 to r.c.
Please notice that for the question of this puzzle, we will discard this fundamental condition of the Trenkler's results.
1. Find the smallest solution for the following prime magic rectangles (composed exclusively by prime numbers): a) (3, 5), b) (3, 7), c) (4, 6)
2. Find any prime magic rectangle composed exclusively by consecutive primes?
Contributions came from Luke Pebody, Faride Firoozbakht, J. C. Rosa and Enoch Haga.
Q1. The lowest possible total for a 3x5 prime magic rectangle is 555. There are (up to isomorphism) 79 such rectangles. One of them is -
05 17 19 71 73
Blind stupidity really. I got a program to run over all odd n.
Step 1 was to create all ways of expressing 3n as the sum of 3 prime numbers. Step 2 was to find all ways in which 5 of these could be disjoint. Step 3 was to take each way X_1,X_2,X_3,X_4,X_5 found in step 2. Then search for sets of 5 primes, one from each of X_1,X_2,X_3,X_4,X_5 which add to 5n. Finally, step 4 (within the loop started in step 3) was to try and find 3 disjoint sets from Step 3.
Same method has worked for 3x7: Smallest total is 987 There are 580 such solutions (up to isomorphism), and 1 of them is as follows:
005 007 029 041 061 079 107
The smallest total for 4x6 is 1080
003 005 017 059 079 107
There are many many such. 1080 is clearly the smallest possible total:
(1) The row sum must be an even number, and the total is 4 times this,
so is a multiple of 8.
Q2. 2x2 impossible: Any 2x2 magic rectangle has equal elements on the diagonals.
2x3 Fairly easy to find - they are 6 consecutive primes whose differences are of the form x,y,2x,y,x. Particularly common seem consecutive regions of the form x-10,x-8,x-2,x+2,x+8,x+10 (x=21,5859,45129,51429,54411,130641,229761 etc.)
2833 2851 2857
1812359 1812383 1812401
This time there are 2 ways it can work - 8 primes with differences a,b,a,c,a,b,a such as the smallest:
853 863 881 883
or 8 primes with differences b+c,a,b,c,b,a,b+c such as the second smallest:
6101 6133 6143 6151
Used dumb method
21821 21859 21893
24091 24109 24137
7168877 7168921 7168949
970447 970469 970537 970549 970573
8750867 8750873 8750891 8750921 8750933 8750957
2x7: Smallest prime 8021753
2x8: None below 500,000,000
1803497 1803551 1803563
[ 20743, 20809, 20857 ],
Moreover, Pebody obtained three theoretic results:
Theorem: Magic Rectangle M(4k,2n) exists
(proofs in process?)
Faride Firoozbakht obtained the same solutions than Pebody for the 2x3 and 2x4 cases for Q2.
J. C. Rosa wrote:
Question 1 a)
The smallest 3x5 prime magic rectangle is :
5 7 23 71 79
17 73 47 29 19
89 31 41 11 13
R=185 ; C=111 ; S=555
Question 2 : Example of a 3x5 magic rectangle
composed exclusively by 15 consecutive primes:
20743 20753 20759 20873 20887
20809 20807 20879 20747 20773
20857 20849 20771 20789 20749
R=104015 ; C=62409 ; S=412045
Enoch Haga obtained the same solution than Pebody for the 2x3 of Q2.