2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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
 

$\endgroup$
3
  • $\begingroup$ Great work. Does your program do an exhaustive search? $\endgroup$ – Dmitry Kamenetsky Nov 29 '20 at 9:48
  • 1
    $\begingroup$ @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 $\endgroup$ – Primusa Nov 29 '20 at 9:52
  • $\begingroup$ Can you please include the source code in your answer? Also, welcome to Puzzling! $\endgroup$ – melfnt Nov 29 '20 at 10:19
1
$\begingroup$

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
 

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.