cp's OEIS Frontend

A000695 Moser-de Bruijn sequence: sums of distinct powers of 4.

%I A000695 M3259 N1315 #311 Jun 05 2025 23:58:10
%S A000695 0,1,4,5,16,17,20,21,64,65,68,69,80,81,84,85,256,257,260,261,272,273,
%T A000695 276,277,320,321,324,325,336,337,340,341,1024,1025,1028,1029,1040,
%U A000695 1041,1044,1045,1088,1089,1092,1093,1104,1105,1108,1109,1280,1281,1284,1285
%N A000695 Moser-de Bruijn sequence: sums of distinct powers of 4.
%C A000695 Although this is a list, it has offset 0 for both historical and mathematical reasons.
%C A000695 Numbers whose set of base-4 digits is a subset of {0,1}. - _Ray Chandler_, Aug 03 2004, corrected by _M. F. Hasler_, Oct 16 2018
%C A000695 Numbers k such that the sum of the base-2 digits of k = sum of the base-4 digits of k. - _Clark Kimberling_
%C A000695 Numbers having the same representation in both binary and negabinary (A039724). - _Eric W. Weisstein_
%C A000695 This sequence has many other interesting and useful properties. Every term k corresponds to a unique pair i,j with k = a(i) + 2*a(j) (i=A059905(n), j=A059906(n)) -- see A126684. Every list of numbers L = [L1,L2,L3,...] can be encoded uniquely by "recursive binary interleaving", where f(L) = a(L1) + 2*a(f([L2,L3,...])) with f([])=0. - _Marc LeBrun_, Feb 07 2001
%C A000695 This may be described concisely using the "rebase" notation b[n]q, which means "replace b with q in the expansion of n", thus "rebasing" n from base b into base q. The present sequence is 2[n]4. Many interesting operations (e.g., 10[n](1/10) = digit reverse, shifted) are nicely expressible this way. Note that q[n]b is (roughly) inverse to b[n]q. It's also natural to generalize the idea of "basis" so as to cover the likes of F[n]2, the so-called "fibbinary" numbers (A003714) and provide standard ready-made images of entities obeying other arithmetics, say like GF2[n]2 (e.g., primes = A014580, squares = the present sequence, etc.). - _Marc LeBrun_, Mar 24 2005
%C A000695 a(n) is also equal to the product n X n formed using carryless binary multiplication (A059729, A063010). - _Henry Bottomley_, Jul 03 2001
%C A000695 Numbers k such that A004117(k) is odd. - _Pontus von Brömssen_, Nov 25 2008
%C A000695 Fixed point of the morphism: 0 -> 01; 1 -> 45; 2 -> 89; ...; n -> (4n)(4n+1), starting from a(0)=0. - _Philippe Deléham_, Oct 22 2011
%C A000695 If n is even and present, so is n+1. - _Robert G. Wilson v_, Oct 24 2014
%C A000695 Also: interleave binary digits of n with 0's. (Equivalent to the "rebase" interpretation above.) - _M. F. Hasler_, Oct 16 2018
%C A000695 Named after the Austrian-Canadian mathematician Leo Moser (1921-1970) and the Dutch mathematician Nicolaas Govert de Bruijn (1918-2012). - _Amiram Eldar_, Jun 19 2021
%C A000695 Conjecture: The sums of distinct powers of k > 2 can be constructed as the following (k-1)-ary rooted tree. For each n the tree grows and a(n) is then the total number of nodes. For n = 1, the root of the tree is added. For n > 1, if n is odd one leaf of depth n-2 grows one child. If n is even all leaves of depth >= (n - 1 - A000225(A001511(n/2))) grow the maximum number of children. An illustration is provided in the links. - _John Tyler Rascoe_, Oct 09 2022
%D A000695 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000695 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000695 T. D. Noe, <a href="/A000695/b000695.txt">Table of n, a(n) for n = 0..1023</a>
%H A000695 Jean-Paul Allouche and Jeffrey Shallit, <a href="http://dx.doi.org/10.1016/0304-3975(92)90001-V">The ring of k-regular sequences</a>, Theoretical Computer Sci., Vol. 98 (1992), pp. 163-197.
%H A000695 Jean-Paul Allouche and Jeffrey Shallit, <a href="http://www.cs.uwaterloo.ca/~shallit/Papers/as0.ps">The ring of k-regular sequences</a>, Theoretical Computer Sci., Vol. 98 (1992), pp. 163-197.
%H A000695 David Applegate, Marc LeBrun and N. J. A. Sloane, <a href="http://neilsloane.com/doc/carry1.pdf">Carryless Arithmetic (I): The Mod 10 Version</a>.
%H A000695 David Applegate, Omar E. Pol and N. J. A. Sloane, <a href="/A000695/a000695_1.pdf">The Toothpick Sequence and Other Sequences from Cellular Automata</a>, Congressus Numerantium, Vol. 206 (2010), pp. 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
%H A000695 David Applegate, Marc LeBrun and N. J. A. Sloane, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Sloane/carry2.html">Dismal Arithmetic</a>, J. Int. Seq., Vol. 14 (2011), Article 11.9.8.
%H A000695 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, pp. 59-60, pp. 750-751.
%H A000695 Robert Baillie and Thomas Schmelzer, <a href="https://library.wolfram.com/infocenter/MathSource/7166/">Summing Kempner's Curious (Slowly-Convergent) Series</a>, Mathematica Notebook kempnerSums.nb, Wolfram Library Archive, 2008.
%H A000695 N. G. de Bruijn, <a href="http://dx.doi.org/10.1090/S0025-5718-1964-0167447-9">Some direct decompositions of the set of integers</a>, Math. Comp., Vol. 18, No. 88 (1964), pp. 537-546.
%H A000695 Karl Dilcher and Larry Ericksen, <a href="https://doi.org/10.37236/4822">Hyperbinary expansions and Stern polynomials</a>, Elec. J. Combin, Vol. 22, No. 2 (2015), #P2.24.
%H A000695 Roger B. Eggleton, <a href="http://dx.doi.org/10.1155/2015/216475">Maximal Midpoint-Free Subsets of Integers</a>, International Journal of Combinatorics Volume 2015, Article ID 216475, 14 pages.
%H A000695 S. J. Eigen, Y. Ito, and V. S. Prasad, <a href="http://dx.doi.org/10.1016/j.jnt.2004.04.001">Universally bad integers and the 2-adics</a>, J. Number Theory, Vol. 107, No. 2 (2004), pp. 322-334.
%H A000695 Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="https://arxiv.org/abs/2210.10968">Identities and periodic oscillations of divide-and-conquer recurrences splitting at half</a>, arXiv:2210.10968 [cs.DS], 2022, p. 44.
%H A000695 Bin Lan and James A. Sellers, <a href="http://www.emis.de/journals/INTEGERS/papers/p23/p23.Abstract.html">Properties of a Restricted Binary Partition Function a la Andrews and Lewis</a>, Electronic Journal of Combinatorial Number Theory, Volume 15 #A23.
%H A000695 Lukasz Merta, <a href="https://arxiv.org/abs/1803.00292">Composition inverses of the variations of the Baum-Sweet sequence</a>, arXiv:1803.00292 [math.NT], 2018. See m(n) p. 11.
%H A000695 Leo Moser, <a href="http://www.jstor.org/stable/2689100">An application of generating series</a>, Math. Mag., Vol. 35, No. 1 (1962), pp. 37-38.
%H A000695 Leo Moser, <a href="/A000695/a000695.pdf">An application of generating series</a>, Math. Mag., Vol. 35, No. 1 (1962), pp. 37-38. [Annotated scanned copy]
%H A000695 John Tyler Rascoe, <a href="/A000695/a000695.jpg">Illustration of terms</a>.
%H A000695 Vladimir Shevelev, <a href="http://arxiv.org/abs/1603.04434">Two analogs of Thue-Morse sequence</a>, arXiv:1603.04434 [math.NT], 2016-2017.
%H A000695 N. J. A. Sloane, <a href="/wiki/Catalog_of_Toothpick_and_CA_Sequences_in_OEIS">Catalog of Toothpick and Cellular Automata Sequences in the OEIS</a>
%H A000695 Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences with (relatively) simple ordinary generating functions</a>, 2004.
%H A000695 Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>.
%H A000695 Ralf Stephan, <a href="https://arxiv.org/abs/math/0307027">Divide-and-conquer generating functions. I. Elementary sequences</a>, arXiv:math/0307027 [math.CO], 2003.
%H A000695 Stephen Nicholas Swatman, Ana-Lucia Varbanescu, Andy D. Pimentel, Andreas Salzburger, and Attila Krasznahorkay, <a href="https://arxiv.org/abs/2309.07002">Finding Morton-Like Layouts for Multi-Dimensional Arrays Using Evolutionary Algorithms</a>, arXiv:2309.07002 [cs.NE], 2023.
%H A000695 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Moser-deBruijnSequence.html">Moser-de Bruijn Sequence</a>.
%H A000695 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Negabinary.html">Negabinary</a>.
%H A000695 Wikipedia, <a href="http://en.wikipedia.org/wiki/Morton_code">Morton code</a>.  (also known as Z-order curve. Cf. Marc LeBrun's comments about binary interleaving.)
%H A000695 <a href="/index/Ar#2-automatic">Index entries for 2-automatic sequences</a>.
%F A000695 G.f.: 1/(1-x) * Sum_{k>=0} 4^k*x^2^k/(1+x^2^k). - _Ralf Stephan_, Apr 27 2003
%F A000695 Numbers k such that the coefficient of x^k is > 0 in Product_{n>=0} 1+x^(4^n). - _Benoit Cloitre_, Jul 29 2003
%F A000695 For n >= 1, a(n) = a(n-1) + (4^t+2)/6, where t is such that 2^t||2n,or t=A007814(2n). a(n) = (A145812(n+1) - 1)/2. - _Vladimir Shevelev_, Nov 07 2008
%F A000695 To get a(n), write n as Sum b_j*2^j, then a(n) = Sum b_j*2^(2j). The Diophantine equation a(k)+2a(l)=n has the unique solution: k=Sum b_(2j)*2^j, l=Sum b_(2j+1)*2^j. - _Vladimir Shevelev_, Nov 10 2008
%F A000695 If a(k)*a(l)=a(m), then k*l=m (the inverse, generally speaking, is not true). - _Vladimir Shevelev_, Nov 21 2008
%F A000695 Let F(x) be the generating function, then F(x)*F(x^2) = 1/(1-x). - _Joerg Arndt_, May 12 2010
%F A000695 a(n+1) = (a(n) + 1/3) & -1/3, where & is bitwise AND, -1/3 is represented as the infinite dyadic ...010101 (just as -1 is ...111111 in two's complement) and +1/3 is ...101011. - _Marc LeBrun_, Sep 30 2010
%F A000695 a(n) = Sum_{k>=0} {A030308(n,k)*b(k)} with b(k) = 4^k = A000302(k). - _Philippe Deléham_, Oct 18 2011
%F A000695 A182560(6*a(n)) = 0. - _Reinhard Zumkeller_, May 05 2012
%F A000695 G.f.: x/(1-x^2) + 4*x^2/((1-x)*(W(0) - 4*x - 4*x^2)), where W(k) = 1 + 4*x^(2^k) + 5*x^(2^(k+1)) - 4*x^(2^(k+1))*(1 + x^(2^(k+1)))^2/W(k+1); (continued fraction). - _Sergei N. Gladkovskii_, Jan 04 2014
%F A000695 liminf a(n)/n^2 = 1/3 and limsup a(n)/n^2 = 1. - _Gheorghe Coserea_, Sep 15 2015
%F A000695 Let f(x) = (Sum_{k=-oo..oo} floor(x*2^k)/4^k)/2. Then f(x) is a real-valued extension of a(n), which a(n) approximates in the sense that f(x) = lim_{k->oo} a(floor(x*2^k))/a(2^k). - _Velin Yanev_, Nov 28 2016
%F A000695 G.f. A(x) satisfies x/(1 - x^2) = A(x) - 4 * (1+x) * A(x^2). - _Michael Somos_, Nov 30 2016
%F A000695 a(2^k) = 4^k = A000302(k). a(n + 2^k) = a(n) + a(2^k) for 2^k > n >= 1. - _David A. Corneth_, Oct 16 2018
%F A000695 Sum_{n>=1} 1/a(n) = 1.886176434476107244547259512076353532930680508099044818673061351780360211128... (calculated using Baillie and Schmelzer's kempnerSums.nb, see Links). - _Amiram Eldar_, Feb 12 2022
%e A000695 G.f.: x + 4*x^2 + 5*x^3 + 16*x^4 + 17*x^5 + 20*x^6 + 21*x^7 + 64*x^8 + ...
%e A000695 If n=27, then b_0=1, b_1=1, b_2=0, b_3=1, b_4=1. Therefore a(27) = 4^4 + 4^3 + 4 + 1 = 325; k = b_0 + b_2*2 + b_4*2^2 = 5, l = b_1 + b_3*2 = 3, such that a(5)=17, a(3)=5 and 27 = 17 + 2*5. - _Vladimir Shevelev_, Nov 10 2008
%p A000695 a:= proc(n) local m, r, b; m, r, b:= n, 0, 1;
%p A000695       while m>0 do r:= r+b*irem(m, 2, 'm'); b:= b*4 od; r
%p A000695     end:
%p A000695 seq(a(n), n=0..100);  # _Alois P. Heinz_, Mar 16 2013
%t A000695 Table[FromDigits[Riffle[IntegerDigits[n, 2], 0], 2], {n, 0, 51}] (* _Jacob A. Siehler_, Jun 30 2010 *)
%t A000695 Table[FromDigits[IntegerDigits[n, 2], 4], {n, 0, 51}] (* _IWABUCHI Yu(u)ki_, Apr 06 2013 *)
%t A000695 Union@ Flatten@ NestList[ Join[ 4#, 4# + 1] &, {0}, 6] (* _Robert G. Wilson v_, Aug 30 2014 *)
%t A000695 Select[ Range[0, 1320], Total@ IntegerDigits[#, 2] == Total@ IntegerDigits[#, 4] &] (* _Robert G. Wilson v_, Oct 24 2014 *)
%t A000695 Union[FromDigits[#,4]&/@Flatten[Table[Tuples[{0,1},n],{n,6}],1]] (* _Harvey P. Dale_, Oct 03 2015 *)
%t A000695 a[ n_] := Which[n < 1, 0, EvenQ[n], a[n/2] 4, True, a[n - 1] + 1]; (* _Michael Somos_, Nov 30 2016 *)
%o A000695 (PARI) a(n)=n=binary(n);sum(i=1,#n,n[i]*4^(#n-i)) \\ _Charles R Greathouse IV_, Mar 04 2013
%o A000695 (PARI) {a(n) = if( n<1, 0, n%2, a(n-1) + 1, a(n/2) * 4)}; /* _Michael Somos_, Nov 30 2016 */
%o A000695 (PARI) A000695(n)=fromdigits(binary(n),4) \\ _M. F. Hasler_, Oct 16 2018
%o A000695 (Haskell)
%o A000695 a000695 n = if n == 0 then 0 else 4 * a000695 n' + b
%o A000695             where (n',b) = divMod n 2
%o A000695 -- _Reinhard Zumkeller_, Feb 21 2014, Dec 03 2011
%o A000695 (Python)
%o A000695 def a(n):
%o A000695     n = bin(n)[2:]
%o A000695     x = len(n)
%o A000695     return sum(int(n[i]) * 4**(x - 1 - i) for i in range(x))
%o A000695 [a(n) for n in range(101)] # _Indranil Ghosh_, Jun 25 2017
%o A000695 (Python)
%o A000695 def a():
%o A000695     x = 0
%o A000695     while True:
%o A000695         yield x
%o A000695         y = ~(x << 1)
%o A000695         x = (x - y) & y # _Falk Hüffner_, Dec 21 2021
%o A000695 (Python)
%o A000695 from itertools import count, islice
%o A000695 def A000695_gen(): # generator of terms
%o A000695     yield (a:=0)
%o A000695     for n in count(1):
%o A000695         yield (a := a+((1<<((~n & n-1).bit_length()<<1)+1)+1)//3)
%o A000695 A000695_list = list(islice(A000695_gen(),30)) # _Chai Wah Wu_, Feb 22 2023
%o A000695 (Python)
%o A000695 def A000695(n): return int(bin(n)[2:],4) # _Chai Wah Wu_, Aug 21 2023
%o A000695 (Magma) m:=60; R<x>:=PowerSeriesRing(Integers(), m); [0] cat Coefficients(R!( (&+[4^k*x^(2^k)/(1+x^(2^k)): k in [0..20]])/(1-x) )); // _G. C. Greubel_, Dec 06 2018
%o A000695 (Sage)  s=(sum(4^k*x^(2^k)/(1+x^(2^k)) for k in range(10))/(1-x)).series(x, 60); s.coefficients(x, sparse=False) # _G. C. Greubel_, Dec 06 2018
%o A000695 (Julia)
%o A000695 function a(n)
%o A000695     m, r, b = n, 0, 1
%o A000695     while m > 0
%o A000695         m, q = divrem(m, 2)
%o A000695         r += b * q
%o A000695         b *= 4
%o A000695     end
%o A000695 r end; [a(n) for n in 0:51] |> println # _Peter Luschny_, Jan 03 2021
%o A000695 (C) uint32_t a_next(uint32_t a_n) { return (a_n + 0xaaaaaaab) & 0x55555555; } /* _Falk Hüffner_, Jan 24 2022 */
%Y A000695 For generating functions Product_{k>=0} (1 + a*x^(b^k)) for the following values of (a,b) see: (1,2) A000012 and A000027, (1,3) A039966 and A005836, (1,4) A151666 and A000695, (1,5) A151667 and A033042, (2,2) A001316, (2,3) A151668, (2,4) A151669, (2,5) A151670, (3,2) A048883, (3,3) A117940, (3,4) A151665, (3,5) A151671, (4,2) A102376, (4,3) A151672, (4,4) A151673, (4,5) A151674.
%Y A000695 Main diagonal of A048720, second column of A048723.
%Y A000695 Cf. A000225, A000302, A001511, A007583, A059884, A059901, A059904, A059905, A059906, A007088, A033042-A033052, A126684, A145812.
%Y A000695 A062880(n) = 2*a(n); A001196(n) = 3*a(n).
%Y A000695 Row 4 of array A104257.
%K A000695 nonn,nice,easy
%O A000695 0,3
%A A000695 _N. J. A. Sloane_