cp's OEIS Frontend

A126684 Union of A000695 and 2*A000695.

%I A126684 #57 Jun 02 2025 17:00:48
%S A126684 0,1,2,4,5,8,10,16,17,20,21,32,34,40,42,64,65,68,69,80,81,84,85,128,
%T A126684 130,136,138,160,162,168,170,256,257,260,261,272,273,276,277,320,321,
%U A126684 324,325,336,337,340,341,512,514,520,522,544,546,552,554,640,642,648,650
%N A126684 Union of A000695 and 2*A000695.
%C A126684 Essentially the same as A032937: 0 followed by terms of A032937. - _R. J. Mathar_, Jun 15 2008
%C A126684 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".
%C A126684 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
%C A126684 Or, base 2 representation Sum{d(i)*2^(m-i): i=0,1,...,m} has even d(i) for all odd i.
%C A126684 Union of A000695 and 2*A000695. - _Ralf Stephan_, May 05 2004
%C A126684 Union of A000695 and A062880. - _Franklin T. Adams-Watters_, Aug 30 2014
%C A126684 Integers, the binary representation of which contains no pair of 1 bits whose difference in bit index is odd. - _Frederik P.J. Vandecasteele_, May 29 2025
%H A126684 Reinhard Zumkeller, <a href="/A126684/b126684.txt">Table of n, a(n) for n = 1..10000</a>
%H A126684 David Eppstein, <a href="https://arxiv.org/abs/1804.07396">Making Change in 2048</a>, arXiv:1804.07396 [cs.DM], 2018.
%F A126684 G.f.: sum(i>=1, T(i, x) + U(i, x) ), where
%F A126684 T := (k,x) -> x^(2^k-1)*V(k,x);
%F A126684 U := (k,x) -> 2*x^(3*2^(k-1)-1)*V(k,x); and
%F A126684 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);
%F A126684 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.
%e A126684 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
%t A126684 nmax = 100;
%t A126684 b[n_] := FromDigits[IntegerDigits[n, 2], 4];
%t A126684 Union[A000695 = b /@ Range[0, nmax], 2 A000695][[1 ;; nmax+1]] (* _Jean-François Alcover_, Oct 28 2019 *)
%o A126684 (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,",")))
%o A126684 (Haskell)
%o A126684 a126684 n = a126684_list !! (n-1)
%o A126684 a126684_list = tail $ m a000695_list $ map (* 2) a000695_list where
%o A126684    m xs'@(x:xs) ys'@(y:ys) | x < y     = x : m xs ys'
%o A126684                            | otherwise = y : m xs' ys
%o A126684 -- _Reinhard Zumkeller_, Dec 03 2011
%o A126684 (Python)
%o A126684 from gmpy2 import digits
%o A126684 def A126684(n):
%o A126684     def bisection(f,kmin=0,kmax=1):
%o A126684         while f(kmax) > kmax: kmax <<= 1
%o A126684         while kmax-kmin > 1:
%o A126684             kmid = kmax+kmin>>1
%o A126684             if f(kmid) <= kmid:
%o A126684                 kmax = kmid
%o A126684             else:
%o A126684                 kmin = kmid
%o A126684         return kmax
%o A126684     def g(x):
%o A126684         s = digits(x,4)
%o A126684         for i in range(l:=len(s)):
%o A126684             if s[i]>'1':
%o A126684                 break
%o A126684         else:
%o A126684             return int(s,2)
%o A126684         return int(s[:i]+'1'*(l-i),2)
%o A126684     def f(x): return n-1+x-g(x)-g(x>>1)
%o A126684     return bisection(f,n-1,n-1) # _Chai Wah Wu_, Oct 29 2024
%Y A126684 Cf. A000695, A062880, A033053, A032937.
%K A126684 easy,nonn,base
%O A126684 1,3
%A A126684 _Jonathan Deane_, Feb 15 2007, May 04 2007
%E A126684 New name (using comment from _Ralf Stephan_) from _Joerg Arndt_, Aug 31 2014