login
A267758
If a(n) is prime, then a(n) = a(n+1) - a(n-1): lexicographic first permutation of the nonnegative integers with this property.
6
0, 1, 2, 3, 5, 8, 4, 6, 7, 13, 20, 9, 10, 11, 21, 12, 14, 15, 16, 17, 33, 18, 19, 37, 56, 22, 23, 45, 24, 25, 26, 27, 28, 29, 57, 30, 31, 61, 92, 32, 34, 35, 36, 38, 39, 40, 41, 81, 42, 43, 85, 44, 46, 47, 93, 48, 49, 50, 51, 52, 53, 105, 54, 55, 58, 59
OFFSET
0,3
COMMENTS
In practice, the definition implies that if a prime term a(n) has been added, the next term is computed as a(n+1) = a(n) + a(n-1). Will it ever happen that a term computed that ("greedy") way would be equal to a number which already occured previously? This is of course forbidden, so the term a(n) which was "tentatively" added has to be changed, as to be either composite, or to "produce" a "legal" a(n+1). In case a(n) itself was already computed as sum of the two preceding terms (because of a prime a(n-1)), this backtracking must go one step further. But since the sum of two primes > 2 is even, there will never be three primes > 2 in a row.
As a result (independently found by Lars Blomberg, private communication), there cannot be more than the three lines that can already be seen in the graph of a(0..1000): (i) a(n) ~ n if the predecessor is composite, (ii) a(n) ~ 2n if a(n-1) is prime but a(n-2) isn't, (iii) a(n) ~ 3n if a(n-1) and a(n-2) both are prime. - M. F. Hasler, Jan 25 2016
Lars Blomberg also observed that (i) the sequence of the lesser of two consecutive odd primes is (at least up to n = 1000) the same as A217199, and (ii) the "isolated primes" are always (up to n = 10^7) preceded by an even composite number. We can show that the latter implies that a(n+1) = a(n) + a(n-1) (with prime a(n)) will never be equal to a previously used number, which in that case must lie on the "upper line" of the (even) a(m+1) = a(m-2) + 2*a(m-1) ~ 3m, m < n, in order to occur before a(n+1) ~ 2n, so that we would have a sequence "odd, prime, even". - M. F. Hasler, Jan 25 2016
PROG
(PARI) {N=200; a=[]; U=[]; L=0; while(#a<N, while(#U && U[1]==L, U=U[^1]; L++); a=concat(a, L); L++; while(isprime(a[#a]), setsearch(U, a[#a]+a[#a-1])&&error("Duplicate at n=", #a); a=concat(a, a[#a]+a[#a-1]); U=setunion(U, a[-1..-1]))); a; } \\ Using a bitmask for the used numbers > L (= least unused) is slightly faster but requires more memory for very large N.
CROSSREFS
Sequence in context: A030132 A004090 A104205 * A333301 A166015 A268134
KEYWORD
nonn
AUTHOR
Eric Angelini and M. F. Hasler, Jan 21 2016
STATUS
approved