login
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
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)
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
Cf. A245057 (inverse), A249161 (a(n)-n), A249168 (records in a(n)-n), A249029 (first differences), A246490 (when a(n)=n).
Sequence in context: A255234 A364225 A256995 * A065561 A245708 A126917
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