OFFSET
1,3
COMMENTS
Previous name was: If A = {a_1, a_2, a_3...} is the Moser-de Bruijn sequence A000695 (consisting of sums of distinct powers of 4) and A' = {2a_1, 2a_2, 2a_3...} then this sequence, let's call it B, is the union of A and A'. Its significance, alluded to in the entry for the Moser-de Bruijn sequence, is that its sumset, B+B, = {b_i + b_j : i, j natural numbers} consists of the nonnegative integers; and it is the fastest-growing sequence with this property. It can also be described as a "basis of order two for the nonnegative integers".
The sequence is the fastest growing with this property in the sense that a(n) ~ n^2, and any sequence with this property is O(n^2). - Franklin T. Adams-Watters, Jul 27 2015
Or, base 2 representation Sum{d(i)*2^(m-i): i=0,1,...,m} has even d(i) for all odd i.
LINKS
Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
David Eppstein, Making Change in 2048, arXiv:1804.07396 [cs.DM], 2018.
FORMULA
G.f.: sum(i>=1, T(i, x) + U(i, x) ), where
T := (k,x) -> x^(2^k-1)*V(k,x);
U := (k,x) -> 2*x^(3*2^(k-1)-1)*V(k,x); and
V := (k,x) -> (1-x^(2^(k-1)))*(4^(k-1) + sum(4^j*x^(2^j)/(1+x^(2^j)), j = 0..k-2))/(1-x);
Generating function. Define V(k) := [4^(k-1) + Sum ( j=0 to k-2, 4^j * x^(2^j)/(1+x^(2^j)) )] * (1-x^(2^(k-1)))/(1-x) and T(k) := (x^(2^k-1) * V(k), U(k) := x^(3*2^(k-1)-1) * V(k) then G.f. is Sum ( i >= 1, T(i) + U(i) ). Functional equation: if the sequence is a(n), n = 1, 2, 3, ... and h(x) := Sum ( n >= 1, x^a(n) ) then h(x) satisfies the following functional equation: (1 + x^2)*h(x^4) - (1 - x)*h(x^2) - x*h(x) + x^2 = 0.
EXAMPLE
All nonnegative integers can be represented in the form b_i + b_j; e.g. 6 = 5+1, 7 = 5+2, 8 = 0+8, 9 = 4+5
MATHEMATICA
nmax = 100;
b[n_] := FromDigits[IntegerDigits[n, 2], 4];
Union[A000695 = b /@ Range[0, nmax], 2 A000695][[1 ;; nmax+1]] (* Jean-François Alcover, Oct 28 2019 *)
PROG
(PARI) for(n=0, 350, b=binary(n); l=length(b); if(sum(i=1, floor(l/2), component(b, 2*i))==0, print1(n, ", ")))
(Haskell)
a126684 n = a126684_list !! (n-1)
a126684_list = tail $ m a000695_list $ map (* 2) a000695_list where
m xs'@(x:xs) ys'@(y:ys) | x < y = x : m xs ys'
| otherwise = y : m xs' ys
-- Reinhard Zumkeller, Dec 03 2011
(Python)
from gmpy2 import digits
def A126684(n):
def bisection(f, kmin=0, kmax=1):
while f(kmax) > kmax: kmax <<= 1
while kmax-kmin > 1:
kmid = kmax+kmin>>1
if f(kmid) <= kmid:
kmax = kmid
else:
kmin = kmid
return kmax
def g(x):
s = digits(x, 4)
for i in range(l:=len(s)):
if s[i]>'1':
break
else:
return int(s, 2)
return int(s[:i]+'1'*(l-i), 2)
def f(x): return n-1+x-g(x)-g(x>>1)
return bisection(f, n-1, n-1) # Chai Wah Wu, Oct 29 2024
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Jonathan Deane, Feb 15 2007, May 04 2007
EXTENSIONS
New name (using comment from Ralf Stephan) from Joerg Arndt, Aug 31 2014
STATUS
approved