Problems & Puzzles: Puzzles

Puzzle 1079 Forest of prime numbers

Rodolfo Kurchan sent the following nice puzzle

Introduction: His puzzle is a variation of an original puzzle created by two undergraduate students from Michigan State University, according to a video uploaded by Neil Sloane. These students named their puzzle as "The stepping stones puzzle". It would be a good idea that you take a look of this video to understand more easily the Kurchan's variation, exposed immediately after.

The Forest of prime numbers, by Rodolfo Kurchan:

We have an infinite board of grid squares.

We have a only one number 1 placed somewhere.

And we are going to place n green-stones in some other fixed places, that worth 2 each

From there we have to allocate the consecutive prime numbers from 3 onwards trying to get as much as possible prime numbers (no duplicated prime numbers are allowed) for each case.

Each number that is allocated has to be the sum of its neighbors already placed in directions horizontally, vertically and diagonally (like a chess king)

Example: n=1 (which means that only one green "2" is allocated. Largest prime allocated is "13".

    1
  11 3
13 2 5
    7

For example, in this first case the number 3 is the sum of 1 + 2, 5 is the sum of 2 + 3, 7 is 2 + 5, 11 is 1 + 2 + 3 + 5 and 13 is 2 + 11. It is impossible to allocate the prime 17, following the rules.

What are your best solution starting with  n=2, 3, ... green stones?

The best solution means that the largest number of consecutive primes from 3 onwards are placed in order without duplicates.

Other two solutions by R. Kurchan:

n=2, largest prime =23

 

 

1

23

 

 

11

3

 

19

13

2

5

17

2

 

 

7

 

 

 

n=3, largest prime =31

 

 

 

1

23

 

 

11

3

 

19

13

2

5

17

2

 

29

7

31

 

2

 

 

 

 

 

Q1) Can you confirm that the Kurchan's above solutions are the best solutions with n=1, 2 and 3 green stones or improve them?

Q2) Can you find best solutions using n>3 green stones?


During the week from 19 to 25 March, 2022, contributions came from Dmitry Kamenetsky, Giorgos Kalogeropoulos, Fred Schneider.

***

Dmitry wrote:

I believe the first 3 solutions by Kurchan are optimal, but I cannot prove it.

Here are my best solutions for n=4 to 9:


 
n=4 score 41
 .  2 37 31  .  1  .
23  2  .  2 29  .  3
 . 19 17 13 11  2  5
 .  .  . 41  .  7  .

n=5 score 47
 . 23 19 41  .  1  .
 2  .  2 17  3 37  2
13 11  7  5 29  2 43
 . 31  .  .  .  2 47

n=6 score 59
 .  .  .  .  . 43  .  .
 .  .  .  . 47  2 41  .
 .  .  .  . 53  2 37  .
 .  .  1 59  .  2 29  2
13 11  3  .  2 23  . 31
 .  2  5 17 19  .  .  .
 .  .  7  .  .  .  .  .

n=7 score 67
 . 13  .  .  .  .  .  .
 .  2 11  1  .  .  .  .
 7  5  3  .  .  .  .  .
 . 17  . 67 31  .  .  .
 . 19  2 29  2 37 41  .
 .  . 23  2  .  2  2 43
 .  .  .  . 59 53 47  .
 .  .  . 61  2  .  .  .

n=8 score 79
 .  .  7  . 59  .  .  .  .  .  .
13  2  5 17 19 23  2 31  .  .  .
 . 11  3  .  2  . 29  . 37 41  .
 .  .  1 79 73  .  2  2  2  2 43
 .  .  .  .  . 71 67 61 53 47  .
 .  .  .  .  .  .  2  .  .  .  .

n=9 score 97
 .  . 19 89  .  .  .  .  .  .
61  2 53 17  .  .  .  .  .  .
 . 59  2 13  2  .  .  .  .  .
 .  .  2  7 23  . 97  .  2 43
 .  . 67 47  1 29 31 37 41  .
 .  .  . 11  3 71  2  .  2  .
 .  .  .  2  5  . 73 79 83  .
 .  .  .  .  .  .  .  .  2  .

***

Giorgos wrote:

Q2. For n=4 I found the following solution:
n = 4, largest prime = 41  

 

 
   
I am not sure if this is the best solution

***

Fred wrote:

I took a different approach.  I just tried to see how far I could go. The best I could come up with was 54 stones (from prime 3 to prime 211). Itís the best solution I found.  I think it could be optimal but Iím not positive.

The extension at 131 is a very tight constraint and in general, I think one has to add a lot of 2 stones to accommodate the complex distribution of gaps.

 
That said, Iíll try to look at it some more during the week.  If I find something better, Iíll send an update.

 

***

From 1-3 May, 2022, Giorgio Vecchi sent, through Rodolfo Kurchan, the following improvements to the following solutions already published here from Dmitry Kamenetsky:

For n=5, prime=53

For n=6, prime=61

 

For n=7, prime =73

 

For n=8, prime 89

 

Vecchi claims that for n=9 the prime=97 solution obtained by Kamenetsky is the optimal. He claims also that all the four above solutions obtained by him are optimal.

 

 

 

Records   |  Conjectures  |  Problems  |  Puzzles