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:

1. If r & c are not of the same parity, no magical rectangle exist (Theorem 1)

2. You may construct a magical rectangle by means of relatively simple algorithms, in the following cases:

2.a. When (r, c) = (2, 2.k), for k=>2 (Theorem 2)

2.b. When (r, c) = (n, n2), n>2 (Theorem 3)

2.c When (r, c) = (a.n, b.n), such that a.b=n, n>2 (Corollary to Theorem 3)

2.d When (r, c) = (m.p, n.q), such that you have previously obtained the magic rectangles mxn and pxq. (Theorem 4)

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.

Question:

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?

Solution:

Contributions came from Luke Pebody, Faride Firoozbakht, J. C. Rosa and Enoch Haga.

Peboy wrote:

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
47 41 79 11 07
59 53 13 29 31

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
047 037 053 083 067 019 023
089 097 059 017 013 043 011

The smallest total for 4x6 is 1080

003 005 017 059 079 107
029 083 037 007 071 043
047 061 023 053 019 067
101 031 013 041 073 011

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.
(2) The column sum must be an even number, and the total is 6 times this, so is a multiple of 3.
(3) Therefore the total is a multiple of 24.
(4) The some of the first 24 odd primes is 1058, and the smallest multiple of 24 above this is 1080.

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.)

Smallest:

2833 2851 2857
2861 2843 2837

100th Smallest:

1812359 1812383 1812401
1812403 1812379 1812361

2x4

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
887 877 859 857

or 8 primes with differences b+c,a,b,c,b,a,b+c such as the second smallest:

6101 6133 6143 6151
6163 6131 6121 6113

3x3

Used dumb method

Smallest:

21821 21859 21893
21871 21863 21839
21881 21851 21841

Second Smallest:

24091 24109 24137
24113 24121 24103
24133 24107 24097

...

100th Smallest

7168877 7168921 7168949
7168927 7168919 7168901
7168943 7168907 7168897

2x5

970447 970469 970537 970549 970573
970583 970561 970493 970481 970457

2x6

8750867 8750873 8750891 8750921 8750933 8750957
8750947 8750941 8750923 8750893 8750881 8750857

2x7: Smallest prime 8021753

2x8: None below 500,000,000

3x4:

1803497 1803551 1803563
1803533 1803569 1803509
1803541 1803517 1803553
1803577 1803511 1803523

3x5:

[ 20743, 20809, 20857 ],
[ 20873, 20747, 20789 ],
[ 20887, 20773, 20749 ],
[ 20753, 20807, 20849 ],
[ 20759, 20879, 20771 ]

Moreover, Pebody obtained three theoretic results:

Theorem: Magic Rectangle M(4k,2n) exists
Theorem: Magic Rectangle M(a,b) exists => M(2a,2b) exists
Theorem: If k odd, M(a,b) exists => M(a,kb) 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.

***

 

 

 
Records   |  Conjectures  |  Problems  |  Puzzles