A353591 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.

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, 21, 20, 24, 35, 30, 27, 28, 32, 33, 34, 36, 49, 40, 39, 46, 38, 41, 44, 37, 42, 48, 43, 54, 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

Offset: 0

Author

M. F. Hasler, May 29 2022

Keywords

• nonn

Comments

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.

Examples

			The square array starts
   0   1   3   6  10  13  19  24  36  42  ...
   2   4   9  11  14  22  35  49  48  ...
   5   8  16  23  31  30  40  43  ...
   7  17  18  26  27  39  54  ...
  12  25  29  28  46  45  ...
  15  21  32  38  51  ...
  20  33  41  52  ...
  34  44  55  ...
  37  58  ...
  47  ...
  ...
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.
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.
		

Crossrefs

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

Programs

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)}