

A249129


Lexicographically earliest sequence of distinct nonnegative integers such that a(2n) = a(n) + a(n+1) for all n >= 0.


6



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, 26, 27, 28, 30, 29, 31, 33, 32, 36, 34, 37, 35, 40, 38, 42, 39, 44, 41, 45, 43, 46, 47, 48, 50, 49, 51, 53, 52, 55, 54, 58, 56, 59, 57, 60, 61, 64, 62, 65, 63, 68
(list;
graph;
refs;
listen;
history;
text;
internal format)



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+2k1) = 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 evenindexed 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 oddindexed 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
Index entries for sequences that are permutations of the natural numbers


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[n1]+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

Cf. A245057 (inverse), A249161 (a(n)n), A249168 (records in a(n)n), A249029 (first differences), A246490 (when a(n)=n).
Sequence in context: A347423 A255234 A256995 * A065561 A245708 A126917
Adjacent sequences: A249126 A249127 A249128 * A249130 A249131 A249132


KEYWORD

nonn,nice


AUTHOR

Eric Angelini and M. F. Hasler, Oct 21 2014


EXTENSIONS

Definition changed by N. J. A. Sloane, May 04 2019


STATUS

approved



