login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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+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

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[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: 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 22 05:51 EDT 2022. Contains 353933 sequences. (Running on oeis4.)