OFFSET
0,3
COMMENTS
Inspired by Eric Angelini's "Cross my primes", cf. links.
Starting with a 2 at the center, place at each move the smallest possible positive integer not used earlier, according to the following rules:
(1) The d digits of the integer are placed on a run of d consecutive squares which must be empty, either in horizontal (left-to-right) or vertical (downward) direction.
(2) At least one of these squares must be adjacent to a nonempty square.
(3) All numbers (with more than 1 digit) formed by filling the squares in that way, reading maximal uninterrupted runs of nonempty squares either left-to-right or downwards, must be primes.
(4) If the same (least) number can be placed in different ways, we choose according to 3 criteria in this order:
(a) We try to place the smallest possible integer also in the subsequent move. If different choices don't lead to the same minimum number placed at the next move, only those with the smallest possible "successor" are allowed: see the placement of 1 in the EXAMPLE.
(b) Among choices equivalent w.r.t. (a), choose the placement with the barycenter (mean of position of first and last digit) closest to the origin, according to the Euclidean norm.
(c) In case of a tie w.r.t. (b), prefer the placement with least maximum square spiral number of the positions of all digits.
The terms a(n) of this sequence give the position of the square where the first digit of the number is placed on the n-th move, through the "clockwise square spiral number" as defined through A174344 and A268038, and with a minus sign for a vertical placement, cf. EXAMPLE for a(15).
Almost all numbers are placed in their natural order, i.e., n at the n-th move.
"Late bird" numbers n placed not at but only after the n-th move are (1, 6, 14, 32, 34, ...); the next cases happen only around n = 250 and then n = 328.
The number of possibilities of placing a given number at the n-th move grows roughly as sqrt(n log n): It is roughly proportional to the number of digits at the border of the convex hull of the filled squares, which is roughly circular. The circumference is proportional to the radius r, while the area proportional to r^2 is also proportional to the number of filled cells. At the n-th move we fill roughly log_10(n) squares with digits, so the area grows like O(n log n) and the circumference is the square root of this.
Since the numbers cannot be split (cf. rule 1), we know that a run of only d consecutive empty squares in either direction will remain empty forever once we have used all numbers < 10^d (cf. EXAMPLE). This contrasts with a variant where the numbers can be split "around" already occupied squares. In that variant one can conjecture that each square will eventually be filled.
LINKS
Eric Angelini, Cross-My-Primes, personal blog cinquantesignes.blogspot.com, April 2020.
M. F. Hasler, Prime scrabble (includes PARI programs), on google docs, May 2020.
EXAMPLE
To the right we show the square spiral used for labeling 20 21 22 23 24...
each position (x,y) of the grid with a nonnegative integer, 19 6--7--8--9 :
cf. A268038. (Counterclockwise numbering would be equally 18 5 0--1 10 :
possible, as would be diamond- or hexagonal or yet 17 4--3--2 11 :
differently shaped spirals. The clockwise square spiral 16 15 14 13 12 :
numbering happens to give the smallest a(2) = 2.)
Since only primes are allowed, we start with a 2 placed at the center (0,0) of the infinite square board, which has the square spiral number 0, whence a(0) = 0.
Now we can't form a prime by adding a 1 to either side of that square. However, we can form the prime 23 by placing the only digit of the number 3 below or right to the initial 2. Since the square with the smallest square spiral number must be preferred, we must place the 3 at (1,0) with square spiral number 1, so a(1) = 1.
Now we can use the number 1 above or below the 3 to form the prime 13 or 31. The first choice would not allow placement of the number 4 in the next move: 431 is prime, but 413 is composite, as is 423; even though 41 would be prime, the 4 can't be above the 2 since 42 is composite. So we make the second choice, 1 placed on (1,-1) with square spiral number 2, and a(2) = 2. After the next moves we arrive at:
8 after 4 placed on (1,1): a(4) = 8 (producing prime 431),
6 4 5 placed on (-1,0): a(5) = 5 (producing prime 523),
7 5 2 3 7 placed on (-2,0): a(6) = 18 (producing prime 7523),
1 6 placed on (-2,1): a(7) = 19 (producing prime 67),
1 0 9 etc. (see below).
There is no way to place 6 after a(5) = 5.
8 produces the prime 8431, 9 produces the prime 84319, and 10 produces the prime 109 by being glued horizontally to the left of the 9.
At move 100 we have:
1
0
0
4
6 8 8 7
8 2 7 5 5 4 6
2 0 2 6 0 6
6 8 6 4 4 2 3 2 2 3 3 3 2
6 6 2 3 4 5
9 2 8 8 5 6 3 7 4 3 0 2 9 3 5 8
8 0 1 7 4 1 6 5 5
7 6 4 5 3 5 1 8 1 1 8 9 3 2 7
6 4 1 1 5 1 8
7 5 5 8 1 4 1 5 7 5 2 3 6 5 7 7
9 8 4 1 1 1 3 2 1 3 8
7 9 2 5 1 2 1 0 9 3 7 1
8 6 7 0 6 6 6 1 2 2 2 9 9
9 3 0 2 6 3 2 8 7 4 5 7 4 9 9
5 4 7 4 7 6 9 1
9 0 5 4 4 4 3 1 5 9 7 9
7 9 7 4 3
9 6 8 4 8 0 9 8 3 9
9 8 3
The first negative term is a(15) = -26, where 26 is the square spiral number of
(3,1) where the first digit of 16 is placed in the 15th move, the second digit being placed just below at (3,0), whence the - sign.
When 98 is placed at the bottom of the above grid, as well 983 as 739 must be prime.
Near this, note how 83 and earlier 73 were placed "sideways" adjacent to an already filled square. (83 with its 3 below the 7 of 74; 73 with its 7 "side by side" to the 9 of 769
Here all 2-digit numbers have been used, so we know that all "holes" of width/height <= 2 will remain empty forever.
PROG
(PARI) See link.
CROSSREFS
KEYWORD
sign,base
AUTHOR
M. F. Hasler and Eric Angelini, May 05 2020
STATUS
approved