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

 

Logo

110 people attended OEIS-50 (videos, suggestions); annual fundraising drive to start soon (donate); editors, please edit! (stack is over 300), your editing is more valuable than any donation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000695 Moser-de Bruijn sequence: sums of distinct powers of 4.
(Formerly M3259 N1315)
98
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Numbers whose set of base 4 digits is {0,1}. - Ray Chandler, Aug 03 2004

Numbers n such that sum of base 2 digits of n = sum of base 4 digits of n. - Clark Kimberling

Numbers having the same representation in both binary and negabinary (A039724). - Eric W. Weisstein

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

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

a(n) is also equal to the product n X n formed using carryless binary multiplication (A059729, A063010). - Henry Bottomley, Jul 03 2001

Numbers n such that A004117(n) is odd. - Pontus von Brömssen, Nov 25 2008

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

A182560(6*a(n)) = 0. - Reinhard Zumkeller, May 05 2012

If n is even and present, so is n+1. - Robert G. Wilson v, Oct 24 2014

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

J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.

J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 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

Joerg Arndt, Matters Computational (The Fxtbook), pp.59-60, pp.750-751

N. G. de Bruijn, Some direct decompositions of the set of integers, Math. Comp., 18 (1964), 537-546.

Eigen, S. J.; Ito, Y.; and Prasad, V. S., Universally bad integers and the 2-adics, J. Number Theory 107 (2004), 322-334.

L. Moser, An application of generating series, Math. Mag., 35 (1962), 37-38.

N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

R. Stephan, Some divide-and-conquer sequences ...

R. Stephan, Table of generating functions

R. Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.

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.)

FORMULA

G.f. 1/(1-x) * Sum(k>=0, 4^k*x^2^k/(1+x^2^k)). - Ralf Stephan, Apr 27 2003

n such that the coefficient of x^n is > 0 in prod (k>=0, 1+x^(4^k)). - 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 (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

a(n)=Sum_k>=0 {A030308(n,k)*b(k)} with b(k)=4^k=A000302(k). - Philippe Deléham, Oct 18 2011

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

EXAMPLE

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

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 *)

PROG

(PARI) d(n, k)=if(n<=0, [ ], concat(d(n\k, k), n%k)); /* vector of digits of n in base k */ sd(n, k)=Set(d(n, k)) /* set of digits of n in base k */

(PARI) Vec(1/(1-x)*+O(x^99)) \\ Charles R Greathouse IV, Oct 12 2012

(PARI) for(n=0, 100, l=if(!n, 0, floor(log(n)/log(2))):print1(sum(k=0, l, binary(n)[k+1]*4^(l-k))", "))

(PARI) a(n)=n=binary(n); sum(i=1, #n, n[i]*4^(#n-i)) \\ Charles R Greathouse IV, Mar 04 2013

(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

CROSSREFS

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.

Diagonal of A048720, second column of A048723.

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

A062880[n] = 2*a[n]; A001196[n] = 3*a[n].

Row 4 of array A104257.

Sequence in context: A166304 A078713 A175263 * A081345 A137527 A024854

Adjacent sequences:  A000692 A000693 A000694 * A000696 A000697 A000698

KEYWORD

nonn,nice,easy,changed

AUTHOR

N. J. A. Sloane

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified October 30 23:35 EDT 2014. Contains 248844 sequences.