# Prime stepping stones

Start by placing number $$1$$ anywhere on an infinite square grid. Now place numbers $$2, 3, 4, \ldots, K$$ in order. A number $$k$$ can be placed if the following rules hold:

• It must be adjacent (horizontally or vertically) to the previous number $$k-1$$.
• It must have at least one neighbour (horizontally or vertically) number $$m$$ already placed such that $$k+m$$ is prime. Note that $$m$$ can be $$k-1$$.

What is the largest number $$K$$ that you can place? You can use a computer if you want.

Found with the assistance of a computer program. It couldn't find anything larger so I think this is an upper bound.

47

                   1  6  7
31 30 29  2  5  8  9
47 42 41 32 27 28  3  4 11 10
46 43 40 33 26 15 14 13 12
45 44 39 34 25 16 17 18
38 35 24 23 20 19
37 36    22 21


• Great work. Does your program do an exhaustive search? – Dmitry Kamenetsky Nov 29 '20 at 9:48
• @DmitryKamenetsky yes, source code here: pastebin.com/Nup7qB4J it does a brute force search up to N == 100 on a 100 by 100 grid with 1 starting in the center, but since the best we've found is < 100 / 2, it should be exhaustive – Primusa Nov 29 '20 at 9:52
• Can you please include the source code in your answer? Also, welcome to Puzzling! – melfnt Nov 29 '20 at 10:19

I can do

43
which is about the limit of what I'm willing to do manually ;-)

       37 36 31 30 27 26 25 24
42 41 38 35 32 29 28 15 16 23 22
43 40 39 34 33 12 13 14 17 20 21
10 11  4  3 18 19
9  8  5  2  1
7  6


• This is a great start Paul! I wonder how far can we push this? Perhaps there is no limit to $K$? – Dmitry Kamenetsky Nov 29 '20 at 5:56