login
Lexicographically earliest permutation of the nonnegative integers filling an infinite square array by falling antidiagonals so that the elements on any 2 X 2 square sum to a prime.
1

%I #10 Jun 14 2022 06:57:11

%S 0,1,2,3,4,5,6,9,8,7,10,11,16,17,12,13,14,23,18,25,15,19,22,31,26,29,

%T 21,20,24,35,30,27,28,32,33,34,36,49,40,39,46,38,41,44,37,42,48,43,54,

%U 45,51,52,55,58,47,50,53,57,56,59,69,70,63,66,81,60,61,78,65,67,64,68,73,72,79,76

%N Lexicographically earliest permutation of the nonnegative integers filling an infinite square array by falling antidiagonals so that the elements on any 2 X 2 square sum to a prime.

%C In A337116 the infinite 2D lattice is filled along a square spiral satisfying the same constraint of 2 X 2 squares adding up to primes.

%e The square array starts

%e 0 1 3 6 10 13 19 24 36 42 ...

%e 2 4 9 11 14 22 35 49 48 ...

%e 5 8 16 23 31 30 40 43 ...

%e 7 17 18 26 27 39 54 ...

%e 12 25 29 28 46 45 ...

%e 15 21 32 38 51 ...

%e 20 33 41 52 ...

%e 34 44 55 ...

%e 37 58 ...

%e 47 ...

%e ...

%e a(4) is in the second row and column. It must sum up with a(0) = 0, a(1) = 1 and a(2) = 2 to a prime. The smallest possible solution is to reach the prime p = 7 with a(4) = 4.

%e Similarly, a(7) which is on the second row, third column, must sum up with a(1) = 1 (above to the left), a(3) = 3 (above) and a(4) = 4 (to the left) to a prime; the smallest solution is to reach the prime p = 17 using a(7) = 9.

%o (PARI) A353591_upto(N, M=Map(), r,c, U=[-1])={vector(N, i, if(r && c, my(s=mapget(M,[r-1,c-1])+mapget(M,[r-1,c])+mapget(M,[r,c-1]), p=nextprime(s+U[1]+1)); while(setsearch(U, N=p-s), p=nextprime(p+1)), N=U[1]+1); mapput(M,[r,c], N); if(c, c--;r++, r=!c=r+1); U=setunion(U, [N]); while(#U>1 && U[2]==U[1]+1, U=U[^1]); N)}

%Y Cf. A000040 (the primes), A337116 (same idea with square spiral instead of array by antidiagonals), A353590 (same idea with squares instead of primes).

%K nonn

%O 0,3

%A _M. F. Hasler_, May 29 2022