Problems & Puzzles: Puzzles

Puzzle 1.- The Gordon Lee puzzle

You are asked to fill a matrix nxn with numbers (0 --> 9) and to count the distinct primes embedded in the matrix, regarding that you can read the lines or part of them, in form vertical, horizontal or diagonal orientation, in both directions.

This puzzle was first proposed (1989) by Gordon Lee for a 6x6 matrix, and answered by Stephen C. Root, of Westboro, Mass.

317333
995639
118142
136373
349199
379379……….. the current record matrix with 187 primes inside.

( Recently Marcus Oswald produced 5 more solutions, all of them with 187 primes )

http://www.geocities.com/MotorCity/7983/primesearch.html

Jaime Ayala and Carlos Rivera extended the Gordon Lee puzzle to other size of matrixes and obtained the current records :

113
754
937 ………………with 30 primes inside

1139
6451
7397
3929……………..with 63 primes inside

11933
99563
89417
33731
32939……………with 116 primes inside

http://www.astro.virginia.edu/~eww6n/math/PrimeArray.html

Would you like to try to beat those records ?


Solution

This 13/04/99 - almost a year after we post the Gordon Lee puzzle - James Bonfield from the Medical Research Council - Laboratory of Molecular Biology, Cambridge, England, came up with other solutions to the 4x4 matrixes that make even with the current record for this size of matrixes: 63 primes

1139
7692
5479
1733

7739
6591
9421
1733

3973
3251
7916
3347

***

Well, this is the month of the Gordon Lee Puzzle. At 17/04/99, Wilfred Whiteside, from Houston Tx., wrote:

"I found a second prime (5x5) array with 116 primes"

3 8 2 1 9
3 3 7 9 7
1 9 4 6 9
9 1 5 7 1
9 1 7 3 9

For the 7x7 case he has found the following matrix with 276 primes:

1 9 3 1 3 3 3
9 9 4 1 9 9 9
1 3 6 9 7 9 1
3 7 7 5 7 2 7
9 6 2 3 8 3 3
9 3 1 1 9 3 3
9 9 1 9 4 3 9

Regarding the prediction of the number of primes in each kind of matrix, he comments: "It is interesting that a simple power law fudge formula 1.626n^2.6475 comes within plus minus 1 of the number of primes for n=1 to n=6 and predicts that for n=7 you would have around 280 primes and around 400 primes for the n=8 case". And adds "My gut feeling is that 276 wouldn't hold up long as a record if it were posted, not with guys like Marcus Oswald out there.  My 276 result is probably analagous to finding a 6x6 with 184 primes.  So I'm guessing that 280 primes is probably about where the upper limit is".

If you think that this is too much work... wait to see the next Whiteside results:

"For fun [Bolds are mine, CR] I've started playing around with 3-D arrays.  So far I have found 5 3x3x3 arrays that have 82 primes in them (if my program is working correctly - it is hard to have full confidence in it without anyone else's results to compare).  The 5  3-D arrays are:

7 3 3   7 8 4   9 6 7
6 6 1   3 0 5   4 2 1
4 7 1   9 9 1   1 7 9

9 7 1   8 1 1   3 3 7
1 6 3   5 0 9   7 7 2
6 1 7   7 4 9   3 9 1

9 7 1   3 8 6   7 4 3
4 5 7   6 0 7   2 3 9
1 1 3   2 9 3   7 9 1

9 7 1   3 8 6   7 4 3
4 5 7   6 0 7   1 3 9
1 1 3   2 9 3   7 9 1

9 7 1   3 8 6   7 4 3
4 5 7   6 0 1   1 3 9
1 1 3   2 9 3   7 9 1

It is intersting that all the record 2-D matrixes have no zeros in them (which I guess isn't all that suprising), but so far my best 3-D  3x3x3's all have a central zero which produces enough 3 digit primes that have their second digit equal to zero to outweigh the loss of two digit primes that its presence causes.  If my program is testing correctly, there are [n(3n-2)]^2 numbers that have to be pulled out of a nxnxn array and tested for primality and uniqueness.  For the 3x3x3 case this means 441 numbers have to be pulled out and tested as opposed to the 65 tests for a 3x3 array.  Thats a lot of numbers to test for such a small array and of course it gets far worse very quickly as n is increased.  I doubt I will ever explore beyond the 4x4x4 case.

Any doubth that just "for fun" is a powerful string


Wilfred Whiteside has finished his study of the 3x3x3 matrix and at 24/04/99 wrote his results:

"The 8 unique arrays found so far (all containing 82 primes) are listed below.

 1 1 3   7 6 3   4 6 7
 1 5 4   9 0 8   9 3 7
 9 1 7   7 2 6   1 4 9

 1 1 3   5 3 8   7 9 3
 1 7 5   0 6 8   9 4 7
 9 2 9   3 1 3   7 1 6

 1 1 3   4 5 7   9 7 1
 2 9 3   6 0 1   3 8 6
 7 9 1   1 3 9   7 4 3

 1 1 3   4 5 7   9 7 1
 2 9 3   6 0 1   3 8 6
 7 9 1   2 3 9   7 4 3

 1 1 3   4 5 7   9 7 1
 2 9 3   6 0 7   3 8 6
 7 9 1   1 3 9   7 4 3

 1 1 3   4 5 7   9 7 1
 2 9 3   6 0 7   3 8 6
 7 9 1   2 3 9   7 4 3

 1 1 3   4 5 7   9 7 1
 2 9 3   6 0 7   3 8 6
 7 9 1   8 3 9   7 4 3

 1 1 7   7 1 3   9 8 3
 3 9 2   6 0 7   1 5 7
 7 9 1   1 4 9   6 7 3


Wilfred Whiteside, at 29/04/99 improved his own record for the 7x7 matrix jumping from 276 to 281 primes.

"Here is the 7x7 array with 281 primes (closely matches that fudged polynomial I made up):

 9 3 3 7 3 1 3
 3 3 3 3 2 9 9
 4 9 8 7 7 9 6
 9 1 9 5 1 6 7
 1 1 2 4 3 7 7
 9 3 9 7 4 9 9
 9 9 9 1 7 3 3


At (8/5/99) Eric W. Weisstein wrote:

"I have proved by exhaustive enumeration that the 30-prime solution to the 3x3 prime array is unique (modulo rotation and reflection) and that no 3x3 solution with more primes exists".


Alberto Hernández Narváez, from Monterrey, México, sent (22/07/99) the following 8x8 record matrix:

.1  3  1  6  3  3  9  3
 1  9  3  4  9  1  9  9
 3  3  3  9  1  1  3  9
 6  3  3  8  9  2  9  9
 9  7  3  7  5  4  7  1
 7  3  2  7  1  3  4  7
 3  1  9  9  6  7  9  3
 9  3  9  6  7  7  9  3

Embedded primes= 373

Alberto got this matrix developing a generalized code based in another made by me time ago for the 6x6 original problem. He ran this new code over an initial matrix that contains the 281 primes 7x7 solution of Whiteside in certain position of the matrix (shown in coloured numbers) and zeros at the first row and column. 373 primes are a kind of close from the 400 predicted by Whiteside for this level of matrixes. BTW, Whiteside himeself has confirmed on request the primality of the 373 solution sent by Alberto.


Wilfred Whiteside, at 29/04/99 improved the Hernández solution for the 8x8 matrix. This is the new record:

 3 9 9 7 3 1 9 2
 3 3 1 1 2 9 1 3
 8 9 3 2 9 3 5 9
 2 7 3 1 7 4 1 1
 3 4 4 5 1 9 6 7
 3 9 7 7 8 9 7 3
 9 9 5 7 7 3 3 3
 9 3 1 6 9 1 9 3

"There were 11 even digits in this Gordon matrix. Note that you can change the top row to 3 9 9 7 3 1 9 9 and it still has 379 primes...The 379 prime solution was found after about 20 days of 100MHz cpu time, so I am most likely nowhere near the best solution.  It still looks to me that the best solution will have around 400 primes", says Whiteside.
***

The last October 31, Wilfred Whiteside improved his better solution for the 8x8 matrix. Now he got a solution with 382 primes inside.

 3 3 9 3 1 3 1 9
 3 9 7 3 5 8 3 9
 3 6 4 9 1 9 3 6
 9 9 3 1 1 2 3 1
 9 4 2 1 9 9 7 9
 1 7 5 8 6 9 9 7
 7 9 3 7 3 3 9 6
 3 3 1 9 3 1 3 3

Please notice that "There were 10 even digits in this Gordon matrix".
***
By his side James Bonfield started tackling the 4x4x4 version of this puzzle and found several (7) solutions with 233 primes inside

3911    3391    1477    9941
9295    2612    2647    7163
7871    5805    8355    3079
7691    1832    3277    1739

***

His last solution (13/03/2000) contains 283 primes:

  

1 9 3 3   7 1 7 7   1 0 3 1   1 1 3 3
9 1 4 5   7 4 8 1   5 0 7 8   7 9 1 9
7 6 9 9   5 6 3 2   2 5 2 1   3 6 9 2
7 1 9 3   7 8 8 3   3 6 7 1   3 7 1 9

***

Now, Marcus Oswald has beatten the Whiteside's record for the 8x8 (382 primes embedded), producing 3 solutions having 385 primes embedded. This is his email:

"...during the weekend my computer found three 8x8 matrices including 385 primes. If there is no error in my testing routine this would be a new record for a 8x8 matrix. The three matrices are:

1 3 5 1 1 9 3 3
9 3 1 1 2 9 1 3
9 3 9 8 3 8 6 9
6 5 3 9 7 4 3 3
7 5 4 7 9 9 3 2
9 7 9 1 6 1 7 3
3 3 9 2 3 3 3 3
3 3 3 7 1 9 9 3
385

3 3 1 9 9 7 3 9
9 1 8 7 7 9 3 9
3 3 3 2 9 3 3 9
3 2 9 7 1 4 0 2
7 7 3 7 6 9 1 3
3 1 5 7 4 3 3 8
9 3 9 4 1 9 9 3
7 3 3 9 7 9 9 3
385

3 3 1 9 9 7 3 9
9 1 8 7 7 9 3 9
3 3 3 2 9 3 3 9
3 2 9 7 1 4 3 2
7 7 3 7 6 9 1 3
3 1 5 7 4 3 3 8
9 3 9 4 1 9 9 3
7 3 3 9 7 9 9 3
385

The second matrix has even a 0-digit in it! And the second and the third matrix only differ in this single digit.

***

Much later (May 2003) he (Marcus) wrote again:

I also found new best solutions for the 8x8 problem, 3 grids with 386 primes and 6 grids with 387 primes:

3 3 3 7 1 9 9 3
9 6 9 1 1 9 3 9
3 1 8 7 4 3 3 6
2 7 3 7 6 9 9 1
9 5 9 7 1 4 2 9
9 3 2 2 9 3 3 9
9 7 8 1 7 9 3 9
3 3 7 3 9 7 3 3

386

3 3 3 7 1 9 9 3
9 6 9 1 1 9 3 9
3 1 8 7 4 3 3 6
2 1 3 7 6 9 9 1
9 5 9 7 1 4 2 9
9 3 2 2 9 3 3 9
9 7 8 1 7 9 3 9
3 3 7 3 9 7 3 3

386

3 3 3 2 9 3 3 9
9 3 3 6 1 3 6 3
5 4 3 1 4 2 9 7
1 6 5 7 7 3 8 3
1 1 9 7 1 8 7 9
9 3 9 4 3 9 7 3
3 3 9 9 7 6 9 9
9 9 9 1 6 9 3 3

386

3 3 3 9 1 7 3 9
3 6 1 7 2 3 9 3
9 3 6 8 3 8 9 7
1 8 3 1 7 4 1 9
1 3 4 7 7 7 6 1
5 9 9 9 2 3 3 3
9 3 3 2 1 7 3 3
7 9 9 1 9 6 7 9

387

1 3 9 9 9 1 3 3
9 3 1 1 9 3 3 3
9 9 9 5 6 3 7 1
3 9 4 1 7 9 2 3
4 7 3 1 7 4 1 9
9 6 9 8 9 5 3 3
3 9 7 1 8 9 7 3
9 3 7 3 3 7 9 3

387

1 3 3 2 7 1 3 3
9 9 3 3 2 9 3 3
1 9 8 4 7 3 3 1
3 8 9 7 7 6 9 9
9 7 5 1 1 5 1 9
3 7 9 3 4 9 1 9
3 9 1 7 3 9 3 3
9 3 9 9 7 3 9 1

387

1 3 9 9 9 1 3 3
9 5 1 1 9 3 3 3
3 9 9 5 6 3 9 3
1 3 4 1 7 7 7 9
0 1 3 1 7 4 3 2
3 1 9 5 9 8 3 3
3 9 7 7 8 9 7 3
3 3 4 9 3 7 3 9

387

3 3 3 7 1 9 9 3
7 9 7 7 8 9 9 3
3 9 5 3 4 7 9 3
3 1 8 1 6 6 9 9
9 6 9 7 1 9 2 1
3 3 3 4 6 9 3 1
1 3 2 1 3 1 3 3
9 7 3 9 7 9 3 9

387

3 3 3 7 1 9 9 3
7 9 7 7 8 9 9 3
3 9 5 3 4 7 9 3
3 1 8 1 6 6 9 9
9 3 9 7 1 9 2 1
3 6 3 4 0 9 3 1
7 9 2 1 3 1 3 3
3 7 9 9 1 3 3 9

387

The next problem I want to attack (if I have a little bit more time) is to prove the optimum value of 63 for the 4x4 problem.

***

Wilfred Whiteside got a better solution (390 primes versus 387 primes, the better record by M. Oswald) sent on August 18, 2003:

Someone at work ...did a search on my name on Google. He found the Gordon Lee puzzle results and informed me that I had been soundly passed up on the 8x8 case. For 2 weeks I tried and could get nowhere above 386 except for one with 387. Then, this weekend, 390 came from out of the depths. But I think there are much better ones out there, but my simple algorithm converges very slowly as the matrix size increases (it might take many cpu years for it to pick candidates near the top of the "Gordon Mountain.") Attached is a file with the primes found in the 8x8. I checked nearest neighbors and found no better solution within 3 digits (ie. a better solution will differ from this one by at least 4 digits). A few of the neighbors had 389 primes in them.

 

3 3 9 9 7 6 9 3
3 3 3 0 1 3 9 9
9 3 9 4 1 9 9 9
2 1 3 1 7 7 4 7
3 9 2 4 1 7 2 3
3 7 5 8 9 5 1 1
9 3 7 3 3 7 9 3
9 9 9 1 7 3 3 3 = candidate with 390 primes

So, the competition is still alive...

***

On March 2005, this first puzzle of my pages is still alive and well alive, indeed!.

Mike Oakes wrote:

I have proved that the maximum score for the 4x4 puzzle is 63, and that the 4 solutions you give on your puzzle page are (modulo rotations and reflections) the only distinct ones.
 
The proof took 58.2 cpu days on an AMD Athlon (Barton) XP2800+ PC, with a clock speed of 2.08 GHz.
 
The program (1500 lines of Pascal) can evaluate 200,000 matrices per second, but even at this rate would take over 1500 years to look at all the 10^16 possible patterns, or "only" 200 years if symmetries are taken into account.
 
So, the program has some (safe!) optimizations/cutoffs to prevent it looking at configurations which could not possibly score as much as 63.

***

 

Jean-Charles Meyrignac wrote (11/9/05):

Hi ! Just to mention that our contest is over:
http://www.recmath.org/contest/index.php

At this moment, I posted the results here:
http://euler.free.fr/contest/FinalResults.htm

And you can find the best grids here:
http://euler.free.fr/contest/BestSolutions1.htm
http://euler.free.fr/contest/BestSolutions2.htm

If you look carefully, you'll see that 4 people beated the 390 record on the
8x8 grid ! Wilfred Whiteside found 394 primes, Tim Glasson and Vadim Trofimov found 392
primes, and I found 391 primes. Feel free to publish anything on your site !
The euler.free.fr links won't be permanent, so I recommend that you put the
recmath.org link instead. We'll soon put these results on recmath.org.

So, the new 8x8 record in from Whiteside: 394 primes. Congratulations Wilfred!

***
 


Records   |  Conjectures  |  Problems  |  Puzzles