|
%I M3259 N1315 #301 Sep 28 2023 12:55:58
%S 0,1,4,5,16,17,20,21,64,65,68,69,80,81,84,85,256,257,260,261,272,273,
%T 276,277,320,321,324,325,336,337,340,341,1024,1025,1028,1029,1040,
%U 1041,1044,1045,1088,1089,1092,1093,1104,1105,1108,1109,1280,1281,1284,1285
%N Moser-de Bruijn sequence: sums of distinct powers of 4.
%C Although this is a list, it has offset 0 for both historical and mathematical reasons.
%C 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 Numbers k such that the sum of the base-2 digits of k = sum of the base-4 digits of k. - _Clark Kimberling_
%C Numbers having the same representation in both binary and negabinary (A039724). - _Eric W. Weisstein_
%C 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 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 a(n) is also equal to the product n X n formed using carryless binary multiplication (A059729, A063010). - _Henry Bottomley_, Jul 03 2001
%C Numbers k such that A004117(k) is odd. - _Pontus von Brömssen_, Nov 25 2008
%C 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 If n is even and present, so is n+1. - _Robert G. Wilson v_, Oct 24 2014
%C Also: interleave binary digits of n with 0's. (Equivalent to the "rebase" interpretation above.) - _M. F. Hasler_, Oct 16 2018
%C 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 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 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A000695/b000695.txt">Table of n, a(n) for n = 0..1023</a>
%H 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 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 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 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 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 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, pp. 59-60, pp. 750-751.
%H 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 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 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 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 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 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 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 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 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 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 John Tyler Rascoe, <a href="/A000695/a000695.jpg">Illustration of terms</a>.
%H 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 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 Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences with (relatively) simple ordinary generating functions</a>, 2004.
%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>.
%H 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 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Moser-deBruijnSequence.html">Moser-de Bruijn Sequence</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Negabinary.html">Negabinary</a>.
%H 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 <a href="/index/Ar#2-automatic">Index entries for 2-automatic sequences</a>.
%F G.f.: 1/(1-x) * Sum_{k>=0} 4^k*x^2^k/(1+x^2^k). - _Ralf Stephan_, Apr 27 2003
%F 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 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 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 If a(k)*a(l)=a(m), then k*l=m (the inverse, generally speaking, is not true). - _Vladimir Shevelev_, Nov 21 2008
%F Let F(x) be the generating function, then F(x)*F(x^2) = 1/(1-x). - _Joerg Arndt_, May 12 2010
%F 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 a(n) = Sum_{k>=0} {A030308(n,k)*b(k)} with b(k) = 4^k = A000302(k). - _Philippe Deléham_, Oct 18 2011
%F A182560(6*a(n)) = 0. - _Reinhard Zumkeller_, May 05 2012
%F 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 liminf a(n)/n^2 = 1/3 and limsup a(n)/n^2 = 1. - _Gheorghe Coserea_, Sep 15 2015
%F 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 G.f. A(x) satisfies x/(1 - x^2) = A(x) - 4 * (1+x) * A(x^2). - _Michael Somos_, Nov 30 2016
%F 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 Sum_{n>=1} 1/a(n) = 1.886176434476107244547259512076353532930680508099044818673061351780360211128... (calculated using Baillie and Schmelzer's kempnerSums.nb, see Links). - _Amiram Eldar_, Feb 12 2022
%e 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 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 a:= proc(n) local m, r, b; m, r, b:= n, 0, 1;
%p while m>0 do r:= r+b*irem(m, 2, 'm'); b:= b*4 od; r
%p end:
%p seq(a(n), n=0..100); # _Alois P. Heinz_, Mar 16 2013
%t Table[FromDigits[Riffle[IntegerDigits[n, 2], 0], 2], {n, 0, 51}] (* _Jacob A. Siehler_, Jun 30 2010 *)
%t Table[FromDigits[IntegerDigits[n, 2], 4], {n, 0, 51}] (* _IWABUCHI Yu(u)ki_, Apr 06 2013 *)
%t Union@ Flatten@ NestList[ Join[ 4#, 4# + 1] &, {0}, 6] (* _Robert G. Wilson v_, Aug 30 2014 *)
%t Select[ Range[0, 1320], Total@ IntegerDigits[#, 2] == Total@ IntegerDigits[#, 4] &] (* _Robert G. Wilson v_, Oct 24 2014 *)
%t Union[FromDigits[#,4]&/@Flatten[Table[Tuples[{0,1},n],{n,6}],1]] (* _Harvey P. Dale_, Oct 03 2015 *)
%t a[ n_] := Which[n < 1, 0, EvenQ[n], a[n/2] 4, True, a[n - 1] + 1]; (* _Michael Somos_, Nov 30 2016 *)
%o (PARI) a(n)=n=binary(n);sum(i=1,#n,n[i]*4^(#n-i)) \\ _Charles R Greathouse IV_, Mar 04 2013
%o (PARI) {a(n) = if( n<1, 0, n%2, a(n-1) + 1, a(n/2) * 4)}; /* _Michael Somos_, Nov 30 2016 */
%o (PARI) A000695(n)=fromdigits(binary(n),4) \\ _M. F. Hasler_, Oct 16 2018
%o (Haskell)
%o a000695 n = if n == 0 then 0 else 4 * a000695 n' + b
%o where (n',b) = divMod n 2
%o -- _Reinhard Zumkeller_, Feb 21 2014, Dec 03 2011
%o (Python)
%o def a(n):
%o n = bin(n)[2:]
%o x = len(n)
%o return sum(int(n[i]) * 4**(x - 1 - i) for i in range(x))
%o [a(n) for n in range(101)] # _Indranil Ghosh_, Jun 25 2017
%o (Python)
%o def a():
%o x = 0
%o while True:
%o yield x
%o y = ~(x << 1)
%o x = (x - y) & y # _Falk Hüffner_, Dec 21 2021
%o (Python)
%o from itertools import count, islice
%o def A000695_gen(): # generator of terms
%o yield (a:=0)
%o for n in count(1):
%o yield (a := a+((1<<((~n & n-1).bit_length()<<1)+1)+1)//3)
%o A000695_list = list(islice(A000695_gen(),30)) # _Chai Wah Wu_, Feb 22 2023
%o (Python)
%o def A000695(n): return int(bin(n)[2:],4) # _Chai Wah Wu_, Aug 21 2023
%o (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 (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 (Julia)
%o function a(n)
%o m, r, b = n, 0, 1
%o while m > 0
%o m, q = divrem(m, 2)
%o r += b * q
%o b *= 4
%o end
%o r end; [a(n) for n in 0:51] |> println # _Peter Luschny_, Jan 03 2021
%o (C) uint32_t a_next(uint32_t a_n) { return (a_n + 0xaaaaaaab) & 0x55555555; } /* _Falk Hüffner_, Jan 24 2022 */
%Y 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 Main diagonal of A048720, second column of A048723.
%Y Cf. A000225, A000302, A001511, A007583, A059884, A059901, A059904, A059905, A059906, A007088, A033042-A033052, A126684, A145812.
%Y A062880(n) = 2*a(n); A001196(n) = 3*a(n).
%Y Row 4 of array A104257.
%K nonn,nice,easy
%O 0,3
%A _N. J. A. Sloane_
|
