%I #25 Jul 17 2021 01:46:40
%S 0,1,2,3,24,4,5,7,8,6,9,10,11,13,18,12,16,19,29,25,42,14,15,17,20,21,
%T 22,23,26,38,45,27,28,33,40,32,31,39,30,41,48,49,36,35,34,37,43,66,47,
%U 50,46,51,52,53,55,54,44,56,83,63,59,68,64,67,72,85,57,70,79,78,58,60,61,121,76,71,90,73
%N For any n >= 0, exactly four sums a(n+i) + a(n+j) are prime, for 0 <= i < j <= 4: lexicographically earliest such sequence of distinct nonnegative integers.
%C That is, there are exactly four primes (counted with multiplicity) among the 10 pairwise sums of any five consecutive terms. (It is possible to have 4 primes among the pairwise sums of any 4 consecutive elements, see A329449.)
%C This map is defined with offset 0 so as to have a permutation of the nonnegative integers in case each of these eventually appears, which is not yet proved (cf. below). The restriction to positive indices would then be a permutation of the positive integers with the same property, but not the lexicographically earliest such, which starts (1, 2, 3, 4, 23, 8, 5, 6, 10, 7, 9, 11, 12, ...).
%C Concerning the existence of the sequence with infinite length: If the sequence is to be computed in a greedy manner, this means that for given P(n) := {a(n-1), a(n-2), a(n-3), a(n-4)} and thus N(n) := #{ primes x + y with x, y in P(n), x < y} in {0, ..., 4}, we have to find a(n) such that we have exactly 4 - N(n) primes in a(n) + N(n). It is easy to prove that this is always possible when 4 - N(n) = 0 or 1. Otherwise, similar to A329452, ..., A329455, we see that P(n) is an "admissible constellation" in the sense that a(n-5) + P(n) already gave the number of primes required now. So a (weaker) variant of the k-tuple conjecture ensures we can find this a(n). But the sequence need not be computable in greedy manner! That is, if ever for given P(n) no convenient a(n) would exist, this just means that the considered value of a(n-1) (and possibly a(n-2)) was incorrect, and the next larger choice has to be made. Given this freedom, there is no doubt that this sequence is well defined up to infinity.
%C Concerning surjectivity: If a number m would never appear, this means that m + P(n) will never have the required number of 4 - N(n) primes for all n with a(n) > m, in spite of having found for each of these n at least two other solutions, a(n-4) + P(n) and a(n) + P(n) which both gave 4 - N(n) primes. This appears extremely unlikely and thus as strong evidence in favor of surjectivity.
%C See examples for further computational evidence.
%H Eric Angelini, <a href="http://cinquantesignes.blogspot.com/2019/11/prime-sums-from-neighbouring-terms.html">Prime sums from neighbouring terms</a>, personal blog "Cinquante signes" (and post to the SeqFan list), Nov. 11, 2019.
%e We start with a(0) = 0, a(1) = 1, a(2) = 2, a(3) = 3, the smallest possibilities which do not lead to a contradiction. Indeed, the four sums 0 + 2, 0 + 3, 1 + 2 and 2 + 3 are prime.
%e Now the next term must not give an additional prime when added to any of {0, 1, 2, 3}. We find that a(4) = 24 is the smallest possible choice.
%e Then there are 2 primes (1+2, 2+3) among the pairwise sums using {1, 2, 3, 24}, so the next term must produce two more prime sums. We find that a(5) = 4 is correct, with 1+4 and 3+4.
%e a(10^5) = 99948.
%e a(10^6) = 999923 and all numbers below 999904 occurred by then.
%o (PARI) A329455(n, show=0, o=0, N=4, M=4, p=[], U, u=o)={for(n=o, n-1, show>0&& print1(o", "); U+=1<<(o-u); U>>=-u+u+=valuation(U+1, 2); p=concat(if(#p>=M, p[^1], p), o); my(c=N-sum(i=2, #p, sum(j=1, i-1, isprime(p[i]+p[j])))); if(#p<M && sum(i=1, #p, isprime(p[i]+u))<=c, o=u)|| for(k=u, oo, bittest(U, k-u) || sum(i=1, #p, isprime(p[i]+k))!=c || [o=k, break]));show&&print([u]); o} \\ Optional args: show=1: print a(o..n-1), show=-1: print only [least unused number] at the end; o=1: start with a(1)=1; N, M: get N primes using M+1 consecutive terms.
%Y Other sequences with N primes among pairwise sums of M consecutive terms, starting with a(o) = o, sorted by decreasing N: A329581 (N=11, M=8, o=0), A329580 (N=10, M=8, o=0), A329579 (N=9, M=7, o=0), A329577 (N=7, M=7, o=0), A329566 (N=6, M=6, o=0), A329449 (N=4, M=4, o=0), this A329456 (N=4, M=5, o=0), A329454 (3, 4, 0), A329455 (3, 5, 0), A329411 (2, 3, o=1 and 0), A329452 (2, 4, 0), A329412 (2, 4, 1), A329453 (2, 5, 0), A329413 (2, 5, 1), A329333 (N=1, M=3, o=0 and 1), A329450 (0, 3, 0), A329405 (0, 3, 1).
%K nonn
%O 0,3
%A _M. F. Hasler_, based on an idea from _Eric Angelini_, Nov 15 2019