|
%I #63 Jan 02 2023 12:30:50
%S 1,0,2,3,5,4,8,6,9,7,12,10,14,11,15,13,16,17,19,18,22,20,24,21,25,23,
%T 26,27,28,30,29,31,33,32,36,34,37,35,40,38,42,39,44,41,45,43,46,47,48,
%U 50,49,51,53,52,55,54,58,56,59,57,60,61,64,62,65,63,68
%N Lexicographically earliest sequence of distinct nonnegative integers such that a(2n) = a(n) + a(n+1) for all n >= 0.
%C I conjecture that a(n) ~ n. The differences d(n) = a(n)-n are in A249161. The first occurrences of the small differences are at d(0)=1, d(1)=-1, d(2)=0, d(6)=2, d(9)=-2, d(122)=3, d(127)=-3, d(922)=4, d(929)=-4, d(1994)=5, d(2003)=-5, d(3986)=6, d(3997)=-6,... It seems that if d(n) is the first occurrence of k>0, then n is even and d(n+2k-1) = -k is the first occurrence of the opposite value. - _M. F. Hasler_, Oct 22 2014
%C Is there a proof of the plausible conjecture that every number appears? - _N. J. A. Sloane_, Oct 17 2018
%C The old definition was: "Lexicographically earliest permutation of the nonnegative integers such that a(2n) = a(n) + a(n+1) for all n >= 0", but the present definition seems simpler. - _N. J. A. Sloane_, May 04 2019
%C From _Charlie Neder_, Jun 19 2019: (Start)
%C Theorem: Every nonnegative integer appears.
%C Proof: For n > 0, a(2n+1) is unrestricted and can be the least unused element, so it is sufficient to prove that choosing the least unused element will not force two even-indexed terms to be equal and cause a contradiction. However, if both bisections are strictly increasing up to some index 2k+1, then a(2k+2) > a(2k) since a(k+2) > a(k), and a(2k+3) > a(2k+1) since the least unused element must be greater than a(2k+1), so no contradictions can arise and choosing the odd-indexed terms this way guarantees that every number appears. (End)
%H Alois P. Heinz, <a href="/A249129/b249129.txt">Table of n, a(n) for n = 0..10000</a>
%H E. Angelini, <a href="http://list.seqfan.eu/oldermail/seqfan/2014-October/013843.html">Two neighbors sum -- and odd ranks in S</a>, SeqFan list, Oct 21 2014
%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%e Taking n=0 gives a(0)+a(1)=a(0), so a(1)=0. The smallest value for a(0) is 1, and this works. So a(0)=1, a(1)=0.
%e Taking n=1, we require a(1)+a(2)=a(2), so we take the smallest value for a(2), 2.
%e Taking n=2, we require a(2)+a(3)=a(4), and we can take a(3)=3, a(4)=5.
%e And so on ...
%o (PARI) {a=vector(200);a[1]=1;a[3]=2;u=0;for(n=4,#a, a[n]=if( n%2, a[n\2+2]+a[n\2+1], k=2; while(bittest(u,k++),); u+=1<<k; k); u=bitor(u,1<<(a[n-1]+a[n])); n<#a && a[n+1] && u=bitor(u,1<<(a[n+1]+a[n])));a}
%o (Haskell)
%o import Data.List (delete)
%o a249129 n = a249129_list !! n
%o a249129_list = 1 : 0 : 2 : f 3 2 [3..] where
%o f :: Int -> Int -> [Int] -> [Int]
%o f k x zs'@(z:zs)
%o | r == 0 = y : f (k+1) y (delete (x + y) $ delete y zs')
%o | r == 1 = z : f (k+1) z (delete (x + z) zs)
%o where y = a249129 k' + a249129 (k' + 1)
%o (k', r) = divMod k 2
%o -- _Reinhard Zumkeller_, Oct 22 2014
%o (Python)
%o def a249129():
%o ...seq = {0:1}
%o ...acc = 0
%o ...i = 0
%o ...while True:
%o ......if i in seq:
%o .........if i+1 in seq:
%o ............if 2*i not in seq:
%o ...............seq[2*i] = seq[i]+seq[i+1]
%o .........elif 2*i in seq:
%o ............seq[i+1] = seq[2*i]-seq[i]
%o .........else:
%o ............while acc in seq.values():
%o ...............acc += 1
%o ............seq[i+1] = acc
%o ............seq[2*i] = seq[i] + seq[i+1]
%o ......else:
%o .........while acc in seq.values():
%o ............acc += 1
%o .........seq[i] = acc
%o ......yield seq[i]
%o ......i += 1
%o # _Christian Perfect_, Dec 02 2014
%Y Cf. A245057 (inverse), A249161 (a(n)-n), A249168 (records in a(n)-n), A249029 (first differences), A246490 (when a(n)=n).
%K nonn,nice
%O 0,3
%A _Eric Angelini_ and _M. F. Hasler_, Oct 21 2014
%E Definition changed by _N. J. A. Sloane_, May 04 2019
|
