A329455 - OEIS

%I #13 Dec 21 2024 12:19:06

%S 0,1,2,4,8,6,3,10,14,11,5,9,15,26,12,17,13,7,18,16,20,21,19,23,27,40,

%T 22,31,24,25,29,28,30,32,33,39,34,36,35,38,41,46,37,43,48,42,55,47,44,

%U 45,52,49,50,53,56,58,54,57,51,73,76,61,59,63,64,68,60,69,67,62,65,66,70,71,72,79,77,74,81,86,78,89,82,85,80,99,84,83,75,92,87,88,90,91,93,94,100

%N There are exactly three primes in {a(n+i) + a(n+j), 0 <= i < j <= 4} for any n >= 0: lexicographically earliest such sequence of distinct nonnegative integers.

%C That is, there are exactly three primes among the 10 pairwise sums of any five consecutive terms.

%C It is unknown whether this is a permutation of the nonnegative numbers. There is 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), a(n-4)} 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) = 0 or 1, and for S(n) = 0 or 1, this is similar to the case of A329452 or A329453. 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 3 primes among the pairwise sums using {0, 1, 2, 4}, and the next term must not produce an additional prime as sum with these. The terms 0 and 1 exclude primes and (primes - 1). We find that a(4) = 8 is the smallest possibility.

%e Then there are 2 primes (1+2 and 1+4) among the pairwise sums using {1, 2, 4, 8}, and the next term must produce exactly one additional prime as sum with these terms. We find that a(5) = 6 is the smallest possibility (since 5+2 and 5+8 would give 2 primes).

%o (PARI) A329455(n, show=0, o=0, N=3, 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 Cf. A329454 (3 primes among a(n+i)+a(n+j), 0 <= i < j <= 3).

%Y Cf. A329452 (2 primes among a(n+i)+a(n+j), 0 <= i < j <= 3), A329453 (2 primes among a(n+i)+a(n+j), 0 <= i < j <= 4).

%Y Cf. A329333 (1 odd prime among a(n+i)+a(n+j), 0 <= i < j <= 2), A329450 (0 primes among a(n+i)+a(n+j), 0 <= i < j <= 2).

%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