cp's OEIS Frontend

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.

%I A267758 #29 May 10 2025 09:02:31
%S A267758 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,
%T A267758 23,45,24,25,26,27,28,29,57,30,31,61,92,32,34,35,36,38,39,40,41,81,42,
%U A267758 43,85,44,46,47,93,48,49,50,51,52,53,105,54,55,58,59
%N 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.
%C A267758 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 occurred 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.
%C A267758 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
%C A267758 _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
%H A267758 M. F. Hasler, <a href="/A267758/b267758.txt">Table of n, a(n) for n = 0..1000</a>
%H A267758 Eric Angelini, <a href="https://web.archive.org/web/*/http://list.seqfan.eu/oldermail/seqfan/2016-January/015978.html">Prime a(n) as difference of its neighbours</a>, SeqFan list, Jan. 21, 2016.
%H A267758 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%o A267758 (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.
%Y A267758 Cf. A217199.
%K A267758 nonn
%O A267758 0,3
%A A267758 _Eric Angelini_ and _M. F. Hasler_, Jan 21 2016