|
| |
|
|
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
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
|
|
|
|
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
(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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
