login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000695 Moser-de Bruijn sequence: sums of distinct powers of 4.
(Formerly M3259 N1315)
114

%I M3259 N1315

%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 {0,1}. - _Ray Chandler_, Aug 03 2004

%C Numbers n such that sum of base 2 digits of n = sum of base 4 digits of n. - _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 integer n corresponds to a unique pair i,j with n=a(i)+2a(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. Yet another description is "Numbers whose base 4 representation consists of only 0's and 1's". - _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 A182560(6*a(n)) = 0. - _Reinhard Zumkeller_, May 05 2012

%C If n is even and present, so is n+1. - _Robert G. Wilson v_, Oct 24 2014

%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 J.-P. Allouche and J. Shallit, <a href="http://dx.doi.org/10.1016/0304-3975(92)90001-V">The ring of k-regular sequences</a>, Theoretical Computer Sci., 98 (1992), 163-197.

%H J.-P. Allouche and J. Shallit, <a href="http://www.cs.uwaterloo.ca/~shallit/Papers/as0.ps">The ring of k-regular sequences</a>, Theoretical Computer Sci., 98 (1992), 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="http://neilsloane.com/doc/tooth.pdf">The Toothpick Sequence and Other Sequences from Cellular Automata</a>

%H D. Applegate, M. LeBrun, N. J. A. Sloane, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Sloane/carry2.html">Dismal Arithmetic</a>, J. Int. Seq. 14 (2011) # 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 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., 18 (1964), 537-546.

%H K. Dilcher and L. Ericksen, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p24">Hyperbinary expansions and Stern polynomials</a>, Elec. J. Combin, 22, 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 107 (2004), 322-334.

%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 L. Moser, <a href="http://www.jstor.org/stable/2689100">An application of generating series</a>, Math. Mag., 35 (1962), 37-38.

%H L. Moser, <a href="/A000695/a000695.pdf">An application of generating series</a>, Math. Mag., 35 (1962), 37-38. [Annotated scanned copy]

%H V Shevelev, <a href="http://arxiv.org/abs/1603.04434">Two analogs of Thue-Morse sequence</a>, arXiv preprint arXiv:1603.04434, 2016

%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 R. Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>

%H R. Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>

%H R. Stephan, <a href="http://arXiv.org/abs/math.CO/0307027">Divide-and-conquer generating functions. I. Elementary sequences</a>, arXiv:math/0307027 [math.CO], 2003.

%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 prod (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 (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 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=-inf..inf, 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->inf, 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

%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) = subst(Pol(binary(n)), 'x, 4) \\ _Gheorghe Coserea_, Sep 15 2015

%o (PARI) {a(n) = if( n<1, 0, n%2, a(n-1) + 1, a(n/2) * 4)}; /* _Michael Somos_, Nov 30 2016 */

%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 xrange(x)])

%o print [a(n) for n in xrange(0, 101)] # _Indranil Ghosh_, Jun 25 2017

%Y For generating functions Prod_{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 Diagonal of A048720, second column of A048723.

%Y Cf. A059884, A059901, A059904, A059905, A059906, A007088, A033042-A033052, A126684.

%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_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified January 17 09:44 EST 2018. Contains 297810 sequences.