A000695 Moser-de Bruijn sequence: sums of distinct powers of 4.
0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85, 256, 257, 260, 261, 272, 273, 276, 277, 320, 321, 324, 325, 336, 337, 340, 341, 1024, 1025, 1028, 1029, 1040, 1041, 1044, 1045, 1088, 1089, 1092, 1093, 1104, 1105, 1108, 1109, 1280, 1281, 1284, 1285
Offset: 0
Examples
G.f.: x + 4*x^2 + 5*x^3 + 16*x^4 + 17*x^5 + 20*x^6 + 21*x^7 + 64*x^8 + ... 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
References
- N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Links
- T. D. Noe, Table of n, a(n) for n = 0..1023
- Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., Vol. 98 (1992), pp. 163-197.
- Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., Vol. 98 (1992), pp. 163-197.
- David Applegate, Marc LeBrun and N. J. A. Sloane, Carryless Arithmetic (I): The Mod 10 Version.
- David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, 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.]
- David Applegate, Marc LeBrun and N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq., Vol. 14 (2011), Article 11.9.8.
- Joerg Arndt, Matters Computational (The Fxtbook), pp. 59-60, pp. 750-751.
- Robert Baillie and Thomas Schmelzer, Summing Kempner's Curious (Slowly-Convergent) Series, Mathematica Notebook kempnerSums.nb, Wolfram Library Archive, 2008.
- N. G. de Bruijn, Some direct decompositions of the set of integers, Math. Comp., Vol. 18, No. 88 (1964), pp. 537-546.
- Karl Dilcher and Larry Ericksen, Hyperbinary expansions and Stern polynomials, Elec. J. Combin, Vol. 22, No. 2 (2015), #P2.24.
- Roger B. Eggleton, Maximal Midpoint-Free Subsets of Integers, International Journal of Combinatorics Volume 2015, Article ID 216475, 14 pages.
- S. J. Eigen, Y. Ito, and V. S. Prasad, Universally bad integers and the 2-adics, J. Number Theory, Vol. 107, No. 2 (2004), pp. 322-334.
- Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 44.
- Bin Lan and James A. Sellers, Properties of a Restricted Binary Partition Function a la Andrews and Lewis, Electronic Journal of Combinatorial Number Theory, Volume 15 #A23.
- Lukasz Merta, Composition inverses of the variations of the Baum-Sweet sequence, arXiv:1803.00292 [math.NT], 2018. See m(n) p. 11.
- Leo Moser, An application of generating series, Math. Mag., Vol. 35, No. 1 (1962), pp. 37-38.
- Leo Moser, An application of generating series, Math. Mag., Vol. 35, No. 1 (1962), pp. 37-38. [Annotated scanned copy]
- John Tyler Rascoe, Illustration of terms.
- Vladimir Shevelev, Two analogs of Thue-Morse sequence, arXiv:1603.04434 [math.NT], 2016-2017.
- N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
- Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
- Ralf Stephan, Table of generating functions.
- Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
- Stephen Nicholas Swatman, Ana-Lucia Varbanescu, Andy D. Pimentel, Andreas Salzburger, and Attila Krasznahorkay, Finding Morton-Like Layouts for Multi-Dimensional Arrays Using Evolutionary Algorithms, arXiv:2309.07002 [cs.NE], 2023.
- Eric Weisstein's World of Mathematics, Moser-de Bruijn Sequence.
- Eric Weisstein's World of Mathematics, Negabinary.
- Wikipedia, Morton code. (also known as Z-order curve. Cf. Marc LeBrun's comments about binary interleaving.)
- Index entries for 2-automatic sequences.
Crossrefs
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.
Cf. A000225, A000302, A001511, A007583, A059884, A059901, A059904, A059905, A059906, A007088, A033042-A033052, A126684, A145812.
Row 4 of array A104257.
Programs
-
C
uint32_t a_next(uint32_t a_n) { return (a_n + 0xaaaaaaab) & 0x55555555; } /* Falk Hüffner, Jan 24 2022 */ -
Haskell
a000695 n = if n == 0 then 0 else 4 * a000695 n' + b where (n',b) = divMod n 2 -- Reinhard Zumkeller, Feb 21 2014, Dec 03 2011 -
Julia
function a(n) m, r, b = n, 0, 1 while m > 0 m, q = divrem(m, 2) r += b * q b *= 4 end r end; [a(n) for n in 0:51] |> println # Peter Luschny, Jan 03 2021 -
Magma
m:=60; R
:=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 -
Maple
a:= proc(n) local m, r, b; m, r, b:= n, 0, 1; while m>0 do r:= r+b*irem(m, 2, 'm'); b:= b*4 od; r end: seq(a(n), n=0..100); # Alois P. Heinz, Mar 16 2013 -
Mathematica
Table[FromDigits[Riffle[IntegerDigits[n, 2], 0], 2], {n, 0, 51}] (* Jacob A. Siehler, Jun 30 2010 *) Table[FromDigits[IntegerDigits[n, 2], 4], {n, 0, 51}] (* IWABUCHI Yu(u)ki, Apr 06 2013 *) Union@ Flatten@ NestList[ Join[ 4#, 4# + 1] &, {0}, 6] (* Robert G. Wilson v, Aug 30 2014 *) Select[ Range[0, 1320], Total@ IntegerDigits[#, 2] == Total@ IntegerDigits[#, 4] &] (* Robert G. Wilson v, Oct 24 2014 *) Union[FromDigits[#,4]&/@Flatten[Table[Tuples[{0,1},n],{n,6}],1]] (* Harvey P. Dale, Oct 03 2015 *) a[ n_] := Which[n < 1, 0, EvenQ[n], a[n/2] 4, True, a[n - 1] + 1]; (* Michael Somos, Nov 30 2016 *) -
PARI
a(n)=n=binary(n);sum(i=1,#n,n[i]*4^(#n-i)) \\ Charles R Greathouse IV, Mar 04 2013
-
PARI
{a(n) = if( n<1, 0, n%2, a(n-1) + 1, a(n/2) * 4)}; /* Michael Somos, Nov 30 2016 */ -
PARI
A000695(n)=fromdigits(binary(n),4) \\ M. F. Hasler, Oct 16 2018
-
Python
def a(n): n = bin(n)[2:] x = len(n) return sum(int(n[i]) * 4**(x - 1 - i) for i in range(x)) [a(n) for n in range(101)] # Indranil Ghosh, Jun 25 2017 -
Python
def a(): x = 0 while True: yield x y = ~(x << 1) x = (x - y) & y # Falk Hüffner, Dec 21 2021 -
Python
from itertools import count, islice def A000695_gen(): # generator of terms yield (a:=0) for n in count(1): yield (a := a+((1<<((~n & n-1).bit_length()<<1)+1)+1)//3) A000695_list = list(islice(A000695_gen(),30)) # Chai Wah Wu, Feb 22 2023
-
Python
def A000695(n): return int(bin(n)[2:],4) # Chai Wah Wu, Aug 21 2023
-
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
Formula
G.f.: 1/(1-x) * Sum_{k>=0} 4^k*x^2^k/(1+x^2^k). - Ralf Stephan, Apr 27 2003
Numbers k such that the coefficient of x^k is > 0 in Product_{n>=0} 1+x^(4^n). - Benoit Cloitre, Jul 29 2003
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
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
If a(k)*a(l)=a(m), then k*l=m (the inverse, generally speaking, is not true). - Vladimir Shevelev, Nov 21 2008
Let F(x) be the generating function, then F(x)*F(x^2) = 1/(1-x). - Joerg Arndt, May 12 2010
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
A182560(6*a(n)) = 0. - Reinhard Zumkeller, May 05 2012
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
liminf a(n)/n^2 = 1/3 and limsup a(n)/n^2 = 1. - Gheorghe Coserea, Sep 15 2015
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
G.f. A(x) satisfies x/(1 - x^2) = A(x) - 4 * (1+x) * A(x^2). - Michael Somos, Nov 30 2016
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
Sum_{n>=1} 1/a(n) = 1.886176434476107244547259512076353532930680508099044818673061351780360211128... (calculated using Baillie and Schmelzer's kempnerSums.nb, see Links). - Amiram Eldar, Feb 12 2022
Comments