|
| |
|
|
A000695
|
|
Moser-de Bruijn sequence: sums of distinct powers of 4.
(Formerly M3259 N1315)
|
|
94
|
|
|
|
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 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
Additional comments from Marc LeBrun, Mar 24 2005: 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.).
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. [From 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. - From Philippe Deléham, Oct 22 2011.
A182560(6*a(n)) = 0. [Reinhard Zumkeller, May 05 2012]
|
|
|
REFERENCES
|
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
N. G. de Bruijn, Some direct decompositions of the set of integers, Math. Comp., 18 (1964), 537-546.
L. Moser, An application of generating series, Math. Mag., 35 (1962), 37-38.
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
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
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
Joerg Arndt, Fxtbook, pp.59-60, pp.750-751
Eigen, S. J.; Ito, Y.; and Prasad, V. S., Universally bad integers and the 2-adics, J. Number Theory 107 (2004), 322-334.
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
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 [From 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. [From Vladimir Shevelev, Nov 10 2008]
If a(k)*a(l)=a(m), then k*l=m (inverse, generally speaking, is not true) [From Vladimir Shevelev, Nov 21 2008]
Let F(x) be the generating function, then F(x)*F(x^2)=1/(1-x). [From 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. [From Marc LeBrun, Sep 30 2010]
a(n)=Sum_k>=0 {A030308(n,k)*b(k)} with b(k)=4^k=A000302(k). - From Philippe Deléham, Oct 18 2011.
|
|
|
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. [From 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 *)
|
|
|
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 = a000695_list !! n
a000695_list = filter mdb [0..] where
mdb n = n < 2 || m < 2 && mdb n' where (n', m) = divMod n 4
-- Reinhard Zumkeller, 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
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
STATUS
|
approved
|
| |
|
|
