cp's OEIS Frontend

A253073 Lexicographically earliest sequence of distinct numbers such that neither a(n) nor a(n-1)+a(n) is prime.

%I A253073 #28 Feb 08 2015 16:46:06
%S A253073 0,1,8,4,6,9,12,10,14,16,18,15,20,22,24,21,25,26,28,27,30,32,33,35,34,
%T A253073 36,38,39,42,40,44,46,45,48,50,49,51,54,52,56,55,57,58,60,62,63,65,64,
%U A253073 66,68,70,72,69,74,76,77,75,78,80,81,84,82,86,85,87,88
%N A253073 Lexicographically earliest sequence of distinct numbers such that neither a(n) nor a(n-1)+a(n) is prime.
%C A253073 Conjecture: this is a permutation of the nonprimes. [Proof outline given below by Semeon Artamonov and Pat Devlin.]
%C A253073 Let x be a number that's missing.
%C A253073 Then eventually every term must be of the form PRIME - x. (Otherwise, x would appear as that next term.)
%C A253073 In particular, this means there are only finitely many multiples of x that appear in the sequence. To make this cleaner, let Y be a multiple of x larger than all multiples of x appearing in the sequence.
%C A253073 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 A253073 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).
%H A253073 Reinhard Zumkeller, <a href="/A253073/b253073.txt">Table of n, a(n) for n = 1..10000</a>
%o A253073 (Haskell)
%o A253073 a253073 n = a253073_list !! (n-1)
%o A253073 a253073_list = 0 : f 0 a018252_list where
%o A253073    f u vs = g vs where
%o A253073      g (w:ws) | a010051' (u + w) == 1 = g ws
%o A253073               | otherwise = w : f w (delete w vs)
%o A253073 -- _Reinhard Zumkeller_, Feb 02 2015
%Y A253073 Cf. A254337, A002808, A253074.
%Y A253073 Cf. A018252, A010051.
%K A253073 nonn
%O A253073 1,3
%A A253073 _N. J. A. Sloane_, Feb 01 2015, based on a suggestion from _Patrick Devlin_