Prime tree game

Question

Let's play a game. On the first step you place the number 1. On the $n$-th step starting from $n=2$ you place the number $n$ such that:

• It is adjacent (horizontally or vertically) to one or more existing numbers, either below or to the right of them.
• The sum of any pair of adjacent numbers is a prime.

For example, here is a game with 5 steps:

1-2-5
  |
  3
  |
  4

Note that here we cannot move 4 to the right of 3 as it would also be below 5 giving an invalid (non-prime) sum of 9.

What is the most number of steps that you can make in this game?

Answer 1

The answer is PROBABLY

infinity, i.e. one can continue this procedure forever.

I don't have a proof yet, but experimenting with it will yield something like

My strategy is

to go as deep as possible below the number $1$ (i.e. whenever a number can be added to that column, add it there), and then grow out "branches" to the right that are at least one row apart, so that they don't interfere with each other. The number $8$ in the image above is an exception.

Now my reasoning is that

in view of the prime number theorem, there are just "so many primes" that the procedure will likely become easier and easier, with more and more places that we can grow out the branches.

One idea to rigorously prove it is to use some result similar to

Bertrand's postulate

and reason that

after the starting, the number of "branch growing positions" is always large enough to ensure the continuation of the game.

Note that according to the above strategy, the first column is totally determined. It's the sequence $(a_n)_n$ where $a_{n + 1}$ is the smallest integer larger than $a_n$ such that $a_n + a_{n + 1}$ is prime.

This sequence has logarithmic density by the prime number theorem, just as the sequence of primes. So at step $n$ we have about $n/2\log(n)$ growing positions, which is a lot!

There are of course many details to fill in, such as the parity problem. Therefore I don't think a rigorous solution would be easy.

---

EDIT:

There was an error in my picture above: I put $18$ to the right of $15$.

But this is very easy to correct. In the beginning you might need to manually change several values, but in my case I only encountered problem with $44$, in which case I moved $38$ down to the side of $21$. After that, everything is automatic. For example:

This is one possible arrangement for $1$ to $999$:
1, 18
2, 5, 6, 11, 12, 17, 20, 23, 24, 29, 30, 41, 48, 49, 54, 59, 68, 71, 78, 85, 88, 93, 98, 99, 124, 127, 144, 149, 158, 159, 172, 175, 178, 181, 186, 187, 196, 205, 214, 217, 222, 227, 230, 233, 234, 245, 246, 253, 256, 265, 276, 281, 282, 287, 290, 303, 304, 313, 318, 323, 324, 329, 330, 343, 348, 353, 356, 363, 364, 369, 370, 373, 378, 383, 386, 401, 408, 413, 414, 425, 428, 431, 432, 445, 462, 467, 470, 483, 484, 487, 496, 501, 508, 513, 518, 521, 528, 533, 536, 551, 552, 557, 560, 563, 566, 585, 586, 595, 598, 603, 610, 613, 616, 621, 628, 631, 646, 657, 662, 665, 696, 703, 706, 721, 730, 741, 746, 747, 752, 759, 764, 767, 776, 777, 782, 785, 794, 803, 806, 807, 812, 815, 822, 835, 858, 863, 870, 871, 876, 877, 882, 895, 916, 945, 956, 957, 974, 975, 998, 999
3, 8
4, 9, 14, 15, 26, 27, 32, 35, 44, 45, 56, 57, 74, 75, 76, 81, 82, 97, 102, 109, 114, 119, 120, 131, 132, 137, 140, 143, 150, 161, 170, 179, 180, 193, 204, 215, 216, 241, 250, 259, 262, 279, 284, 285, 292, 295, 298, 301, 306, 307, 312, 319, 334, 339, 344, 347, 354, 355, 384, 385, 388, 399, 410, 411, 416, 423, 434, 443, 464, 465, 472, 475, 478, 489, 494, 497, 500, 509, 512, 519, 530, 531, 538, 549, 554, 555, 568, 583, 588, 593, 600, 601, 622, 627, 632, 645, 656, 663, 698, 701, 708, 715, 718, 729, 754, 757, 766, 783, 784, 787, 792, 809, 810, 817, 820, 837, 856, 865, 868, 873, 874, 879, 880, 897, 904, 907, 924, 943, 946, 961, 970, 979, 994
7
10, 19, 34, 39, 40, 43, 46, 61, 66, 73, 94, 103, 108, 125, 126, 145, 148, 163, 168, 169, 184, 189, 190, 199, 202, 207, 212, 219, 224, 225, 236, 243, 248, 251, 258, 263, 278, 293, 294, 299, 300, 317, 326, 327, 332, 341, 350, 351, 358, 361, 366, 367, 376, 381, 392, 395, 402, 407, 420, 437, 440, 441, 442, 469, 502, 507, 514, 517, 522, 527, 534, 535, 558, 559, 564, 565, 606, 607, 624, 625, 634, 643, 648, 649, 654, 667, 694, 705, 724, 735, 736, 753, 758, 765, 788, 791, 818, 819, 838, 855, 866, 867, 886, 891, 892, 909, 914, 933, 934, 939, 950, 951, 962, 969, 980, 993
13
16, 63, 64, 67, 72, 77, 80, 83, 96, 101, 110, 113, 116, 117, 122, 129, 134, 135, 146, 147, 164, 167, 206, 213, 218, 221, 228, 229, 238, 249, 254, 255, 266, 275, 288, 289, 394, 403, 406, 417, 422, 435, 446, 461, 468, 473, 474, 479, 488, 495, 524, 525, 526, 543, 544, 547, 570, 581, 582, 589, 592, 609, 614, 615, 644, 653, 666, 695, 704, 719, 720, 731, 740, 743, 744, 749, 750, 761, 762, 769, 774, 779, 780, 799, 802, 825, 832, 861, 862, 885, 898, 903, 908, 915, 932, 935, 938, 941, 948, 953, 954, 959, 972, 977, 996
21, 38
22, 315, 316, 337, 340, 393, 404, 405, 418, 421, 436, 447, 460, 481, 486, 491, 492, 505, 516, 523, 540, 569, 618, 619, 640, 661, 700, 709, 714, 733, 738, 755, 756, 797, 800, 801, 826, 831, 890, 893, 894, 929, 942, 947, 960, 971, 978, 995
25, 676
28, 33, 104, 107, 162, 239, 240, 269, 272, 335, 338, 345, 346, 397, 426, 427, 450, 457, 480, 503, 506, 515, 546, 571, 580, 591, 596, 597, 604, 633, 658, 669, 692, 737, 830, 833, 834, 859, 888, 889, 900, 901, 910, 913, 918, 983, 990
31
36, 53, 60, 139, 154, 183, 260, 261, 380, 389, 398, 455, 456, 485, 548, 575, 576, 577, 636, 641, 642, 659, 660, 713, 734, 789, 790, 823, 840, 853
37
42, 65, 86, 87, 92, 105, 106, 123, 128, 153, 194, 195, 268, 273, 274, 333, 454, 579, 608, 623, 626, 671, 690, 691, 796, 813, 814, 843, 850, 883, 928, 985, 988, 991
47, 62
50, 359, 360, 391, 396, 541, 672, 689, 710, 723, 728, 771, 772, 795, 824, 839, 854, 887, 902, 921, 926, 963, 968, 981, 992
51
52, 439, 448, 459, 482, 539, 578, 635, 668, 693, 860, 899, 912, 919, 982
55
58, 165, 166, 267, 320, 419, 438, 449, 458, 573, 590, 639, 680, 681, 686, 687, 712, 841, 852, 925, 964, 967, 984, 989
69, 574
70, 237, 242, 375, 452, 545, 572, 677, 684, 827, 842, 851
79
84, 95, 138, 155, 198, 203, 374, 377, 504, 605, 674, 699, 844, 849, 884, 927, 944, 987
89
90, 173, 174, 209, 210, 311, 336, 451, 678, 683, 770, 773, 798, 829
91
100, 711, 848, 911, 920
111, 152
112, 675, 922
115
118, 271, 390, 673, 688
121
130, 679, 682, 685, 846, 847
133
136
141, 542
142
151, 270
156
157
160, 453, 638, 845, 966
171
176
177, 314
182
185, 828
188
191
192, 637, 670
197
200, 923
201
208
211
220
223
226
231
232
235
244
247
252, 965, 986
257
264
277
280
283
286
291
296
297
302
305
308
309
310
321
322
325
328
331
342
349
352
357
362
365
368
371
372
379
382
387
400
409
412
415
424
429
430
433
444
463
466
471
476
477
490
493
498
499
510
511
520
529
532
537
550
553
556
561
562
567
584
587
594
599
602
611
612
617
620
629
630
647
650
651
652
655
664
697
702
707
716
717
722
725
726
727
732
739
742
745
748
751
760
763
768
775
778
781
786
793
804
805
808
811
816
821
836
857
864
869
872
875
878
881
896
905
906
917
930
931
936
937
940
949
952
955
958
973
976
997

As you can see, there are already quite a lot of "spares" in the bottom.

With a program, I have verified that

It works at least until $10^5$. So, hopefully forever.