login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A253074 Lexicographically earliest sequence of distinct numbers such that a(n-1)+a(n) is not prime. 15
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, 26, 28, 27, 29, 31, 32, 30, 33, 35, 34, 36, 38, 37, 39, 41, 40, 42, 43, 44, 46, 45, 47, 48, 50, 49, 51, 53, 52, 54, 56, 55, 57, 58, 59, 60, 61, 62, 63, 65, 64, 66 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

Conjecture: this is a permutation of the nonnegative numbers. [Proof outline below due to Patrick Devlin and Semeon Artamonov]

Let x be a number that's missing.

Then eventually every term must be of the form PRIME - x. (Otherwise, x would appear as that next term.)

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.

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.

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).

Essentially the same as A055266. - R. J. Mathar, Feb 13 2015

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

LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

PROG

(Haskell)

a253074 n = a253074_list !! (n-1)

a253074_list = 0 : f 0 [1..] where

   f u vs = g vs where

     g (w:ws) | a010051' (u + w) == 1 = g ws

              | otherwise = w : f w (delete w vs)

-- Reinhard Zumkeller, Feb 02 2015

(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

CROSSREFS

Cf. A055266, A254337, A253073, A010051.

Sequence in context: A349377 A349376 A134892 * A055266 A338843 A075077

Adjacent sequences:  A253071 A253072 A253073 * A253075 A253076 A253077

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Feb 01 2015, based on a suggestion from Patrick Devlin

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 4 02:40 EST 2021. Contains 349469 sequences. (Running on oeis4.)