cp's OEIS Frontend

A253074 Lexicographically earliest sequence of distinct numbers such that a(n-1)+a(n) is not prime.

%I A253074 #43 Nov 26 2019 10:34:57
%S A253074 0,1,3,5,4,2,6,8,7,9,11,10,12,13,14,16,17,15,18,20,19,21,23,22,24,25,
%T A253074 26,28,27,29,31,32,30,33,35,34,36,38,37,39,41,40,42,43,44,46,45,47,48,
%U A253074 50,49,51,53,52,54,56,55,57,58,59,60,61,62,63,65,64,66
%N A253074 Lexicographically earliest sequence of distinct numbers such that a(n-1)+a(n) is not prime.
%C A253074 Conjecture: this is a permutation of the nonnegative numbers. [Proof outline below due to Patrick Devlin and Semeon Artamonov]
%C A253074 Let x be a number that's missing.
%C A253074 Then eventually every term must be of the form PRIME - x. (Otherwise, x would appear as that next term.)
%C A253074 In particular, this means there are only finitely many multiples of x that appear in the sequence. Let Y be a multiple of x larger than all multiples of x appearing in the sequence.
%C A253074 Let q be a prime not dividing Y. Then since none of the terms Y, 2Y, 3Y, ..., 2qY appear, it must be that, eventually, every term in the sequence is of the form PRIME - Y and also of the form PRIME - 2Y and also of the form PRIME - 3Y, ... and also of the form PRIME - 2qY.
%C A253074 That means we have a prime p and a number Y such that p, p+Y, p+2Y, p + 3Y, p+4Y, ..., p+2qY are all prime. But take this sequence mod q. Since q does not divide Y, the terms 0, Y, ..., 2qY cover every residue class mod q twice. Therefore, p + kY covers each residue class mod q twice. Consequently, there are two terms congruent to 0 mod q. One can be q, but the other must be a multiple of it (contradicting its primality).
%C A253074 Essentially the same as A055266. - _R. J. Mathar_, Feb 13 2015
%C A253074 Simplified version of the proof: Assume x isn't in the sequence, then eventually all terms must be of the form PRIME - x, else x would appear next. In particular, no multiple of x can appear from there on. Assume k*x is the largest multiple of x in the sequence. Take a prime p not dividing x. Then m*x can't appear in the sequence for k+1 <= m <= k+p, and all terms are eventually of the form PRIME - m*x  for all m in {k+1, ..., k+p}. Take one such term N > p, i.e., N + (k+1)*x, ..., N + (k+p)*x  are all prime. Consider this sequence mod p. Since gcd(x,p)=1, the p terms cover each residue class mod p, so one is a multiple of p, in contradiction with their primality. - _M. F. Hasler_, Nov 25 2019
%H A253074 Reinhard Zumkeller, <a href="/A253074/b253074.txt">Table of n, a(n) for n = 1..10000</a>
%o A253074 (Haskell)
%o A253074 a253074 n = a253074_list !! (n-1)
%o A253074 a253074_list = 0 : f 0 [1..] where
%o A253074    f u vs = g vs where
%o A253074      g (w:ws) | a010051' (u + w) == 1 = g ws
%o A253074               | otherwise = w : f w (delete w vs)
%o A253074 -- _Reinhard Zumkeller_, Feb 02 2015
%o A253074 (PARI) A253074_upto(n=99, a, u, U)={vector(n,n, for(k=u,oo, bittest(U,k-u)|| isprime(a+k)||[a=k,break]); (a>u && U+=1<<(a-u))|| U>>=-u+u+=valuation(U+2,2); a)+if(default(debug),print([u]))} \\ additional args allow to tweak computation. If debug > 0, print least unused number at the end. - _M. F. Hasler_, Nov 25 2019
%Y A253074 Cf. A055266, A254337, A253073, A010051.
%K A253074 nonn
%O A253074 1,3
%A A253074 _N. J. A. Sloane_, Feb 01 2015, based on a suggestion from _Patrick Devlin_