Cross-My-Primes


Hello Math-Fun,
this game (hope not old hat) is played on a kind of infinite Scrabble board where all squares are white, and no square has any text on it. The starting "star" square, in the center of the grid, has a 7 on it (the number, not the word, as this game is played with digits only that will form numbers – instead of letters forming words). 

The single player must now form prime numbers at every turn on the board – at the first turn placing the integer 1, at the second turn placing 2, then 3, then 4, then 5, etc. – this is the natural order of the positive integers as they appear (and because 7 starts the game, the player will jump from 6 to 8. No other jump will be allowed during the game). 

Those integers, as in the traditional game of Scrabble, must be attached to the existing structure at least by a digit (one digit per square). 

All visible numbers, before and after any turn, must be prime: they are read horizontally from left to right or vertically from top to bottom (again, like words in a traditional Scrabble game). 

Example here:

We start the game with 7 on the star:
....................7....................

then comes 1 and we form the prime 71;
....................71....................

then comes 2 and we form the prime 271;
...................271....................

then comes 3 and we form the prime 3271;
..................3271....................

then comes 4 and we form the prime 43271;
.................43271....................

then comes 5 and we form the prime 53 (5 on top of 3 on the grid);
..................5.......................
.................43271....................

then comes 6 and we form the prime 61 (6 on top of 1 on the grid);
..................5..6.....................
.................43271.....................

then comes 8 (because 7 is already on the board) and we form the prime 853 (8 on top of 53 on the grid);
..................8........................
..................5..6.....................
.................43271.....................

then comes 9 and we form the prime 29 (9 under 2 on the grid);
..................8........................
..................5..6.....................
.................43271.....................
...................9.......................

then comes 10 and we form the prime 1061 (10 on top of 61 on the grid);
.....................1.....................
..................8..0.....................
..................5..6.....................
.................43271.....................
...................9.......................

now comes 11 – we have many choices here; we can place vertically 11 sticking tot he upper digit 1 of 1061 to form twice the prime 11 (horizontally and vertically) :
......................1....................
.....................11....................
..................8..0.....................
..................5..6.....................
.................43271.....................
...................9.......................
Etc.
After a few discussions with friends, we've decided to forbid to split – as this is too much a help in building the structure. The other problem being that once a number is split, it is difficult to find it looking at a completed grid. This goes against the rules of Scrabble, we know. So, the placement of 11 hereunder is now forbidden, though 101 is a genuine prime:
...........................................
.....................1.....................
..................8.101....................
..................5..6.....................
.................43271.....................
...................9.......................

Is it possible to place, one after the other, starting with 7 in the "center" of the grid, the first 100 natural integers on it? If yes, is there a compact solution that beats the others?

It might be impossible to place the first 100 integers, I do not know – but in this case, is there another start than 7 on the "center star" that would allow that?

This suggests to start a new game every now and then with other primes than 7; one could start a new game with primes like 11, 13, 17 or 17623 (it seems to me that the game halts quickly with the starts 2, 3 and 5).


And now, perhaps, a sequence for the OEIS (any takers?):

We start we the empty board and the first prime on the "star":
...........................................
...........................................
...........................................
....................2......................
...........................................
...........................................
S = 2, ...
We always want to extend S with the smallest integer not yet present in S that can be placed on the grid, according to the above rules; a(2) will be equal to 3 as no possible prime can be built with 1 and 2:
...........................................
...........................................
...........................................
....................23.....................
...........................................
...........................................
S = 2, 3, ...
Now 1 can be placed (forming the prime 31, for instance):
...........................................
...........................................
...........................................
....................23.....................
.....................1.....................
...........................................
S = 2, 3, 1, ...
Now 4 can be placed (forming the prime 431):
...........................................
...........................................
.....................4.....................
....................23.....................
.....................1.....................
...........................................
S = 2, 3, 1, 4 ...
Now 5 can be placed (forming the prime 5431):
...........................................
.....................5.....................
.....................4.....................
....................23.....................
.....................1.....................
...........................................
S = 2, 3, 1, 4, 5, ...
Now 6 cannot be placed (on this grid)  – but 7 yes (forming the prime 75431 for instance):
...........................................
.....................7.....................
.....................5.....................
.....................4.....................
....................23.....................
.....................1.....................
...........................................
S = 2, 3, 1, 4, 5, 7, ...
Now there is a place for 6 – which will form the prime 67:
...........................................
....................67.....................
.....................5.....................
.....................4.....................
....................23.....................
.....................1.....................
...........................................
S = 2, 3, 1, 4, 5, 7, 6, ... etc.
Question:
What is the lexicographically earliest sequence of distinct positive terms fitting the "Cross-My-Primes" rules?
Best,
É.
__________________
Update of May 5th, 2020
Maximilian H. computed quickly the hereunder grid, starting on 2 and placing (without splitting them) the first 100 integers. Only 5 integers (in yellow) appear a bit later than they should – but not very late!
The sequence I was looking for is thus quite boring. Here are the first 37 terms of S (the next ones are 38, 39, 40, ... 98, 99, 100 with no "yellow inversion"):

S = 2,3,1,4,5,7,6,8,9,10,11,12,13,15,14,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,33,32,35,36,34,37,...

How was computed Maximilian's wonderful structure?
1) start with the prime 2;
2) always try to place on the grid the smallest integer not yet present;
3) any new integer must be linked to the previous structure by at least a single digit (like in the game of Scrabble);
4) always try to keep the structure compact;
5) splitting integers is forbidden.
Voilà!

[In French (merci Maximilian!) :
1° - placer toujours le plus petit nombre possible (on ne peut pas placer un plus petit, à n'importe quel instant) ; de plus :

2° - parmi ceux-là, ne considérer que ceux qui permettent le plus petit placement au coup suivant (par exemple, avec le 1 on peut faire 13 et 31, mais on retient le 31 permettant de placer le 4 au coup suivant, ce qui n'est pas possible en faisant un 13) ;

3° - parmi ceux là (minimal au coup n et aussi n+1) on choisit celui dont le "barycentre" (milieu) est le plus proche de l'origine (0,0), là où il y a le 2 bleu initial – pas du barycentre de la structure déjà produite) ;

4° - parmi ceux qui sont toujours "équivalents", on prend celui qui a les plus petits "square spiral numbers" (le max de ces nombres pour chaque case sur laquelle est placé un de ses chiffres doit être minimal).]

(The integers 1 to 9 are in red – except 2, in blue; the yellow integers must be read vertically, from top to bottom – and there is sometimes a mark to separate two of them; the underlined integers must be read horizontally, from left to right.)
Under the structure is a table showing the primes produced by the placement of the successive natural numbers – see what 41 does!
Maximilian has used a very convenient notation to locate any integer k on the grid:
2 has coordinates [0,0], 3 = [1,0], 4 = [1,-1], 5 = [-1,0] and 6 = [-1,-1].
2 forms 2
 2=[0,0]
3 forms 23
 3=[1,0]
1 forms 31
 1=[1,1]
4 forms 431
 4=[1,-1]
5 forms 523
 5=[-1,0]
7 forms 7523
 7=[-2,0]
6 forms 67
 6=[-2,-1]
8 forms 8431
 8=[1,-2]
9 forms 84319
 9=[1,2]
10 forms 109
10=[-1,2]
11 forms 11 and 167
11=[-2,-2]
12 forms 12109
12=[-3,2]
13 forms 113
13=[2,1]
15 forms 157523
15=[-4,0]
14 forms 14157523
14=[-6,0]
16 forms 163
16=[3,-1]
17 forms 17 and 11
17=[-1,-3]
18 forms 1811
18=[-4,-2]
19 forms 19 and 89
19=[2,-3]
20 forms 2011
20=[-1,-5]
21 forms 11321
21=[4,1]
22 forms 222011
22=[-1,-7]
23 forms 223
23=[-2,3]
24 forms 2484319
24=[1,-4]
25 forms 2512109
25=[-5,2]
26 forms 263
26=[-4,4]
27 forms 248431927
27=[1,3]
28 forms 263287
28=[-1,4]
29 forms 229
29=[2,3]
30 forms 30263287
30=[-6,4]
31 forms 11 and 31
31=[4,-2]
33 forms 233
33=[0,-6]
32 forms 32233
32=[-3,-6]
35 forms 351811
35=[-6,-2]
36 forms 3631
36=[4,-4]
34 forms 343631
34=[4,-6]
37 forms 23, 17 and 37
37=[4,2]
38 forms 383
38=[-6,-4]
39 forms 3919 and 29
39=[2,-5]
40 forms 401
40=[-4,-4]
41 forms 41, 541 and 1671223
41=[-3,1]
42 forms 4232233
42=[-5,-6]
43 forms 167122343
43=[-2,5]
44 forms 443
44=[-4,6]
45 forms 45351811
45=[-8,-2]
46 forms 463
46=[1,-8]
47 forms 47 and 47
47=[-3,-5]
48 forms 48463
48=[1,-10]
49 forms 24843192749
49=[1,5]
50 forms 503
50=[-8,-4]
51 forms 1151
51=[5,-1]
52 forms 521
52=[6,-3]
53 forms 953
53=[3,4]
54 forms 54521
54=[6,-5]
55 forms 5545351811
55=[-10,-2]
56 forms 56443
56=[-6,6]
57 forms 557
57=[4,4]
58 forms 5814157523
58=[-8,0]
59 forms 59 and 59
59=[0,6]
60 forms 60343631
60=[4,-8]
61 forms 461 and 3147
61=[-5,-5]
62 forms 622512109
62=[-7,2]
63 forms 115163
63=[7,-1]
64 forms 643
64=[8,-3]
65 forms 65222011
65=[-1,-9]
66 forms 66347
66=[-3,-8]
67 forms 3767
67=[6,2]
68 forms 685545351811
68=[-12,-2]
69 forms 95369
69=[3,6]
70 forms 7030263287
70=[-8,4]
71 forms 71, 1777 and 61
71=[5,3]
72 forms 727 and 7622512109
72=[-8,2]
73 forms 73, 571777 and 545213
73=[5,0]
74 forms 74545213
74=[6,-7]
75 forms 755814157523
75=[-10,0]
76 forms 764232233
76=[-7,-6]
77 forms 577, 37 and 67
77=[4,5]
78 forms 78643
78=[8,-5]
79 forms 79 and 79
79=[-1,7]
80 forms 809
80=[-3,8]
81 forms 6781
81=[5,6]
82 forms 823
82=[-7,-8]
83 forms 83 and 89
83=[2,7]
84 forms 8448463
84=[1,-12]
85 forms 858448463
85=[1,-14]
86 forms 86461
86=[-5,-8]
87 forms 376787
87=[8,2]
88 forms 887
88=[9,0]
89 forms 89 and 83
89=[1,8]
90 forms 6907 and 739
90=[7,0]
91 forms 691
91=[-5,7]
92 forms 92764232233
92=[-9,-6]
93 forms 55793 and 619
93=[6,4]
94 forms 941
94=[-7,8]
95 forms 9560343631
95=[4,-10]
96 forms 9666347
96=[-3,-10]
97 forms 97, 61991 and 37
97=[6,5]
98 forms 987030263287
98=[-10,4]
99 forms 8999, 5779 and 89
99=[4,7]
100 forms 10056443
100=[-9,6]

Bravo et merci, Maximilian, quelle merveille !

Commentaires

  1. If a number might be inserted forming a prime with already existing digits, is it forbidden to do it if it would create a non-prime in some other way (by touching some other existing digits somewhere else)?

    RépondreSupprimer
    Réponses
    1. I find that after the initial disorder (1 after 3 and 6 after 7), one can place each n at the n-th move, at least up to n=999, and that even in the greedy way (using the first of "usually" 2 possibilities, where my program checks first upward and leftward extensions).

      Supprimer
    2. Just to clarify, the above comment concerns the variant with splitting, not the one without splitting mentioned in the part (update May 5) of this story, where many more "inversions" (numbers n placed only after move n) occur, depending on the criteria used to choose among different possible placements of the least possible number.

      Supprimer

Enregistrer un commentaire

Posts les plus consultés de ce blog

A square for three (chess)

Le tripalin se présente

Some strings au cinéma Galeries