3
$\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$

2 Answers 2

2
$\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$ Nov 29, 2020 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, 2020 at 9:52
  • $\begingroup$ Can you please include the source code in your answer? Also, welcome to Puzzling! $\endgroup$
    – melfnt
    Nov 29, 2020 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$ Nov 29, 2020 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.