%I #22 Dec 21 2024 12:13:38
%S 0,1,2,4,5,3,8,6,11,7,10,12,9,19,22,14,15,16,13,18,21,40,43,20,27,46,
%T 17,26,33,24,35,38,32,23,29,30,31,28,25,34,36,39,37,64,42,41,67,47,60,
%U 49,48,52,45,55,44,58,69,51,50,62,53,77,54,56,83,57,66,74,65,61,102,70,71,79,78,59,68,63,72,95,86,81,76,73,75,82,106
%N There are exactly three primes among a(n+i) + a(n+j), 0 <= i < j <= 3, for any n >= 0: lexicographically earliest such sequence of distinct nonnegative integers.
%C That is, there are exactly three primes (counted with multiplicity) among the 6 pairwise sums of any four consecutive terms.
%C It remains unknown whether this is a permutation of the nonnegative numbers. There is some hope that this could be the case, and it seems coherent to choose offset 0 not only in view of this. The restriction to positive indices would then be a permutation of the positive integers, but not the smallest one with the given property.
%C Concerning the existence of the sequence: If the sequence is to be computed in a greedy manner, this means that for given n, we assume given P(n) := {a(n-1), a(n-2), a(n-3)} and thus S(n) := #{ primes x + y with x, y in P(n), x < y} which may equal 0, 1, 2 or 3. We have to find a(n) such that we have exactly 3 - S(n) primes in a(n) + P(n). It is easy to prove that this is always possible when 3 - S(n) is 0 or 1, and similar to the case of A329452 and A329453 when S(n) = 1. When S(n) = 0, however, we must find three primes in the same configuration as the elements of P(n). It is almost surprising that this can always be found up to n = 10^6. However, the sequence does not need to be computable in a greedy manner. That is, if for given P(n) no a(n) would exist such that a(n) + P(n) contains 3 - S(n) primes, this simply means that the considered value of a(n-1) was incorrect, and the next larger choice has to be made. Given this freedom, well-definedness of this sequence up to infinity is far more probable than, for example, the k-tuple conjecture.
%C Computational results are as follows:
%C a(10^5) = 99954 and all numbers below 99915 have appeared at that point.
%C a(10^6) = 1000053 and all numbers below 999845 have appeared at that point.
%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.
%H Eric Angelini, <a href="/A329333/a329333.htm">Prime sums from neighbouring terms</a> [Cached copy of html file, with permission]
%H Eric Angelini, <a href="/A329333/a329333.pdf">Prime sums from neighbouring terms</a> [Cached copy of pdf file, with permission]
%e We start with a(0) = 0, a(1) = 1, a(2) = 2, the smallest possibilities which do not lead to a contradiction.
%e Now there are already 2 primes, 0 + 2 and 1 + 2, among the pairwise sums, so the next term must generate exactly one further prime. It appears that a(3) = 4 is the smallest possible choice.
%e Then there are again two primes among the pairwise sums using {1, 2, 4}, and the next term must again produce one additional prime as sum with these. We find that a(4) = 5 is the smallest possibility.
%t Nest[Block[{k = 3}, While[Nand[FreeQ[#, k], Count[Subsets[Append[Take[#, -3], k], {2}], _?(PrimeQ@ Total@ # &)] == 3], k++]; Append[#, k]] &, {0, 1, 2}, 84] (* _Michael De Vlieger_, Nov 15 2019 *)
%o (PARI) A329454(n, show=0, o=0, N=3, M=3, p=[], U, u=o)={for(n=o, n-1, show&& 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])); o} \\ Optional args: show=1: print a(o..n-1); o=1: start with a(1)=1; N, M: get N primes using M+1 consecutive terms.
%Y Cf. A329452 (2 primes among a(n+i)+a(n+j), 0 <= i < j < 4), A329453 (2 primes among a(n+i)+a(n+j), 0 <= i < j < 5).
%Y Cf. A329333 (1 odd prime among a(n+i)+a(n+j), 0 <= i < j < 3), A329450 (no primes among a(n+i)+a(n+j), 0 <= i < j < 3).
%Y Cf. A329405 ff: variants defined for positive integers.
%K nonn
%O 0,3
%A _M. F. Hasler_, based on an idea from _Eric Angelini_, Nov 15 2019