login
The sequence (a(n) - a(n+1); n such that a(n) is prime) yields the original sequence: lexicographically earliest sequence of distinct positive integers with this property and no two nonprime terms in a row.
2

%I #46 Jan 02 2023 12:30:54

%S 1,5,4,11,6,13,9,19,8,29,23,10,31,22,37,18,41,33,43,14,47,24,59,49,61,

%T 30,67,45,53,16,73,55,79,38,83,50,71,28,89,75,101,54,109,85,103,44,97,

%U 48,107,46,149,119,127,60,113,68,131,78,137,121,139,66,151,96,163,84,167,129,157,74,173,123,179,108,181,153,191,102,193,118,199,98,197,143,223,114,211,126

%N The sequence (a(n) - a(n+1); n such that a(n) is prime) yields the original sequence: lexicographically earliest sequence of distinct positive integers with this property and no two nonprime terms in a row.

%C Not a permutation: some numbers (2, 3, 7, 12, 15, 17, 20, ...) will never appear, these are now listed as A330593.

%C Can be computed in an "almost greedy" manner using the following two rules:

%C (1) A prime a(n) = p is always followed by a(n+1) = p - a(N(n)), where N(n) is the number of primes in {a(1), ..., a(n)}. If this a(n+1) > 0 is composite and did not occur earlier, then all terms up to this one are guaranteed to be correct.

%C (2) A nonprime a(n) is followed by a(n+1) = the next available prime p such that a(n+2) = p - a(N(n)+1) > 0 does not occur earlier and does not lead to an impossible successor (negative or repeated term) through rule (1) in case it is prime. If this happens, the next larger prime must be chosen.

%C The strongly oscillating graph of this sequence is the union of approximately linear subgraphs G(k), k = 1, 2, 3..., corresponding to subsequences S(k) given as local maxima resp. minima (depending on the parity of k) of the terms not in one of the earlier subsequences. The graphs G(k), k > 2, lie quite precisely in the middle between the two preceding graphs G(k-1) and G(k-2) and have a slope roughly equal to the average of the two "preceding" slopes: e.g., when G(1) has a slope of about 4.0 near n = 10^3, G(2) has a slope of about 2.0, G(3) has a slope of about 3.0, G(4) has a slope of about 2.5, etc.

%C The subsequences S(k) correspond to roughly every other of the remaining terms, the indices corresponding to their terms are almost always separated by a gap of 2^k and they have density 2^k in range(A330614) = A000027 \ A330593. (S(1) is the subsequence of primes without a(11) = 23. One might also take S(1) as the subsequence of primes, which would only move a(11) = 23 from S(3) to S(1) and a(12) = 10 from S(2) to S(10).) See the link to the OEIS wiki page for more.

%C Among the first 10^4 terms, a(11) = 23 is the only prime that follows another prime. Are there other such terms? - _M. F. Hasler_, Dec 27 2019

%H M. F. Hasler, <a href="/A330614/b330614.txt">Table of n, a(n) for n = 1..10000</a>

%H Eric Angelini, <a href="http://list.seqfan.eu/oldermail/seqfan/2019-December/">Phenix seq by (prime-next term) operation</a>, SeqFan list, Dec 25 2019.

%H M. F. Hasler, <a href="/wiki/User:M._F._Hasler/A330614">A330614 (more details)</a>, OEIS wiki, Dec 30 2019.

%F For n < 10^4, a(n) is prime <=> n <= 10 and even or n >= 11 and odd.

%e a(1) = 1 must be followed by a prime a(2) = p, but such that a(2) - a(3) = a(1), i.e., p - a(3) = 1 or p - 1 = a(3), and such that this does not produce a contradiction. Indeed, p = 2 is impossible since this would require a(3) = 1 which already occurred earlier. Also, p = 3 would require a(3) = 2, and then a(3) - a(4) = a(2) or 2 - a(4) = 3, also impossible. Therefore a(2) = 5 is the smallest possible choice.

%e Since a(2) is prime, a(3) is given by the rule that a(2) - a(3) must reproduce the first term of the sequence, a(1) = 1, whence a(3) = a(2) - 1 = 4.

%e a(3) = 4 must be followed by a prime, but we see that 2 and 3 are not possible: the first try would be 7, which then ought to be followed by 2, leading again to a "contradiction" (no possible successor), so it turns out that a(4) = 11 is the smallest possible choice.

%o (PARI) A330614_upto(N=99,show=0/*set to 1 for verbose output*/)={my(i=1, U=[], A=List(i)); for(n=1, N, U=setunion(U,[A[n]]); show&& printf("a(%d) = %d, ",n,A[n]); #A>n || listput(A, 0); if( isprime(A[n]), if( !setsearch(U, A[n+1] = A[n] - A[i] ) && A[n+1] > 0, i++; next, show&& print1("no, "); until(!isprime(A[n]) || !i--, U=setminus(U, [A[n]]); A[n+1]=0; n--))); forprime( k=A[n+1]+1,oo, !setsearch(U,k) && !setsearch(U, k-A[i]) && [A[n+1]=k, break])); while(!A[#A] || isprime(A[#A]), listpop(A)); Vec(A)}

%Y Cf. A000040 (primes), A018252 (nonprimes).

%Y Cf. A330593: positive integers which do not appear in this sequence.

%K nonn,look

%O 1,2

%A _Eric Angelini_ and _M. F. Hasler_, Dec 25 2019