OFFSET
0,3
COMMENTS
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
Is there a proof of the plausible conjecture that every number appears? - N. J. A. Sloane, Oct 17 2018
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
From Charlie Neder, Jun 19 2019: (Start)
Theorem: Every nonnegative integer appears.
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)
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..10000
E. Angelini, Two neighbors sum -- and odd ranks in S, SeqFan list, Oct 21 2014
EXAMPLE
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.
Taking n=1, we require a(1)+a(2)=a(2), so we take the smallest value for a(2), 2.
Taking n=2, we require a(2)+a(3)=a(4), and we can take a(3)=3, a(4)=5.
And so on ...
PROG
(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}
(Haskell)
import Data.List (delete)
a249129 n = a249129_list !! n
a249129_list = 1 : 0 : 2 : f 3 2 [3..] where
f :: Int -> Int -> [Int] -> [Int]
f k x zs'@(z:zs)
| r == 0 = y : f (k+1) y (delete (x + y) $ delete y zs')
| r == 1 = z : f (k+1) z (delete (x + z) zs)
where y = a249129 k' + a249129 (k' + 1)
(k', r) = divMod k 2
-- Reinhard Zumkeller, Oct 22 2014
(Python)
def a249129():
seq = {0:1}
acc = 0
i = 0
while True:
if i in seq:
if i+1 in seq:
if 2*i not in seq:
seq[2*i] = seq[i]+seq[i+1]
elif 2*i in seq:
seq[i+1] = seq[2*i]-seq[i]
else:
while acc in seq.values():
acc += 1
seq[i+1] = acc
seq[2*i] = seq[i] + seq[i+1]
else:
while acc in seq.values():
acc += 1
seq[i] = acc
yield seq[i]
i += 1
# Christian Perfect, Dec 02 2014
CROSSREFS
KEYWORD
nonn,nice,changed
AUTHOR
Eric Angelini and M. F. Hasler, Oct 21 2014
EXTENSIONS
Definition changed by N. J. A. Sloane, May 04 2019
STATUS
approved