A048883 -id:A048883 - cp's OEIS frontend

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

N. J. A. Sloane

Although this is a list, it has offset 0 for both historical and mathematical reasons.
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
Numbers k such that the sum of the base-2 digits of k = sum of the base-4 digits of k. - 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 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
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 k such that A004117(k) 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
If n is even and present, so is n+1. - Robert G. Wilson v, Oct 24 2014
Also: interleave binary digits of n with 0's. (Equivalent to the "rebase" interpretation above.) - M. F. Hasler, Oct 16 2018
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
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

			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

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

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.

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.
Main diagonal of A048720, second column of A048723.
Cf. A000225, A000302, A001511, A007583, A059884, A059901, A059904, A059905, A059906, A007088, A033042-A033052, A126684, A145812.
A062880(n) = 2*a(n); A001196(n) = 3*a(n).
Row 4 of array A104257.

uint32_t a_next(uint32_t a_n) { return (a_n + 0xaaaaaaab) & 0x55555555; } /* Falk Hüffner, Jan 24 2022 */

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

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

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

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

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

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

{a(n) = if( n<1, 0, n%2, a(n-1) + 1, a(n/2) * 4)}; /* Michael Somos, Nov 30 2016 */

A000695(n)=fromdigits(binary(n),4) \\ M. F. Hasler, Oct 16 2018

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

def a():
    x = 0
    while True:
        yield x
        y = ~(x << 1)
        x = (x - y) & y # Falk Hüffner, Dec 21 2021

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

def A000695(n): return int(bin(n)[2:],4) # Chai Wah Wu, Aug 21 2023

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

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
a(n) = Sum_{k>=0} {A030308(n,k)*b(k)} with b(k) = 4^k = A000302(k). - Philippe Deléham, Oct 18 2011
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

A005836 Numbers whose base-3 representation contains no 2.

Original entry on oeis.org

0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, 81, 82, 84, 85, 90, 91, 93, 94, 108, 109, 111, 112, 117, 118, 120, 121, 243, 244, 246, 247, 252, 253, 255, 256, 270, 271, 273, 274, 279, 280, 282, 283, 324, 325, 327, 328, 333, 334, 336, 337, 351, 352

Offset: 1

N. J. A. Sloane, Jeffrey Shallit

3 does not divide binomial(2s, s) if and only if s is a member of this sequence, where binomial(2s, s) = A000984(s) are the central binomial coefficients.
This is the lexicographically earliest increasing sequence of nonnegative numbers that contains no arithmetic progression of length 3. - Robert Craigen (craigenr(AT)cc.umanitoba.ca), Jan 29 2001
In the notation of A185256 this is the Stanley Sequence S(0,1). - N. J. A. Sloane, Mar 19 2010
Complement of A074940. - Reinhard Zumkeller, Mar 23 2003
Sums of distinct powers of 3. - Ralf Stephan, Apr 27 2003
Numbers n such that central trinomial coefficient A002426(n) == 1 (mod 3). - Emeric Deutsch and Bruce E. Sagan, Dec 04 2003
A039966(a(n)+1) = 1; A104406(n) = number of terms <= n.
Subsequence of A125292; A125291(a(n)) = 1 for n>1. - Reinhard Zumkeller, Nov 26 2006
Also final value of n - 1 written in base 2 and then read in base 3 and with finally the result translated in base 10. - Philippe LALLOUET (philip.lallouet(AT)wanadoo.fr), Jun 23 2007
a(n) modulo 2 is the Thue-Morse sequence A010060. - Dennis Tseng, Jul 16 2009
Also numbers such that the balanced ternary representation is the same as the base 3 representation. - Alonso del Arte, Feb 25 2011
Fixed point of the morphism: 0 -> 01; 1 -> 34; 2 -> 67; ...; n -> (3n)(3n+1), starting from a(1) = 0. - Philippe Deléham, Oct 22 2011
It appears that this sequence lists the values of n which satisfy the condition sum(binomial(n, k)^(2*j), k = 0..n) mod 3 <> 0, for any j, with offset 0. See Maple code. - Gary Detlefs, Nov 28 2011
Also, it follows from the above comment by Philippe Lallouet that the sequence must be generated by the rules: a(1) = 0, and if m is in the sequence then so are 3*m and 3*m + 1. - L. Edson Jeffery, Nov 20 2015
Add 1 to each term and we get A003278. - N. J. A. Sloane, Dec 01 2019

			12 is a term because 12 = 110_3.
This sequence regarded as a triangle with rows of lengths 1, 1, 2, 4, 8, 16, ...:
   0
   1
   3,  4
   9, 10, 12, 13
  27, 28, 30, 31, 36, 37, 39, 40
  81, 82, 84, 85, 90, 91, 93, 94, 108, 109, 111, 112, 117, 118, 120, 121
... - _Philippe Deléham_, Jun 06 2015

Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section E10, pp. 317-323.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

David W. Wilson, Table of n, a(n) for n = 1..10000 (first 1024 terms from T. D. Noe)
J.-P. Allouche, G.-N. Han, and Jeffrey Shallit, On some conjectures of P. Barry, arXiv:2006.08909 [math.NT], 2020.
J.-P. Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
J.-P. Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
J.-P. Allouche, Jeffrey Shallit and G. Skordev, Self-generating sets, integers with missing blocks and substitutions, Discrete Math. 292 (2005) 1-15.
David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
Megumi Asada, Bruce Fang, Eva Fourakis, Sarah Manski, Nathan McNew, Steven J. Miller, Gwyneth Moreland, Ajmain Yamin, and Sindy Xin Zhang, Avoiding 3-Term Geometric Progressions in Hurwitz Quaternions, Williams College (2023).
Robert Baillie and Thomas Schmelzer, Summing Kempner's Curious (Slowly-Convergent) Series, Mathematica Notebook kempnerSums.nb, Wolfram Library Archive, 2008.
Noam Benson-Tilsen, Samuel Brock, Brandon Faunce, Monish Kumar, Noah Dokko Stein, and Joshua Zelinsky, Total Difference Labeling of Regular Infinite Graphs, arXiv:2107.11706 [math.CO], 2021.
Raghavendra Bhat, Cristian Cobeli, and Alexandru Zaharescu, Filtered rays over iterated absolute differences on layers of integers, arXiv:2309.03922 [math.NT], 2023. See page 16.
Matvey Borodin, Hannah Han, Kaylee Ji, Tanya Khovanova, Alexander Peng, David Sun, Isabel Tu, Jason Yang, William Yang, Kevin Zhang, and Kevin Zhao, Variants of Base 3 over 2, arXiv:1901.09818 [math.NT], 2019.
Ben Chen, Richard Chen, Joshua Guo, Tanya Khovanova, Shane Lee, Neil Malur, Nastia Polina, Poonam Sahoo, Anuj Sakarda, Nathan Sheffield, and Armaan Tipirneni, On Base 3/2 and its Sequences, arXiv:1808.04304 [math.NT], 2018.
Karl Dilcher and Larry Ericksen, Hyperbinary expansions and Stern polynomials, Elec. J. Combin, Vol. 22 (2015), Article P2.24.
P. Erdős, V. Lev, G. Rauzy, C. Sandor, and A. Sarkozy, Greedy algorithm, arithmetic progressions, subset sums and divisibility, Discrete Math., Vol. 200, No. 1-3 (1999), pp. 119-135 (see Table 1). alternate link.
Joseph L. Gerver and L. Thomas Ramsey, Sets of integers with no long arithmetic progressions generated by the greedy algorithm, Math. Comp., Vol. 33, No. 148 (1979), pp. 1353-1359.
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. 45.
Ryota Inagaki, Tanya Khovanova, and Austin Luo, Permutation-based Strategies for Labeled Chip-Firing on k-ary Trees, arXiv:2503.09577 [math.CO], 2025. See p. 18.
Kathrin Kostorz, Robert W. Hölzel and Katharina Krischer, Distributed coupling complexity in a weakly coupled oscillatory network with associative properties, New J. Phys., Vol. 15 (2013), #083010; doi:10.1088/1367-2630/15/8/083010.
Clark Kimberling, Affinely recursive sets and orderings of languages, Discrete Math., Vol. 274, Vol. 1-3 (2004), pp. 147-160.
John W. Layman, Some Properties of a Certain Nonaveraging Sequence, J. Integer Sequences, Vol. 2 (1999), Article 99.1.3.
Manfred Madritsch and Stephan Wagner, A central limit theorem for integer partitions, Monatsh. Math., Vol. 161, No. 1 (2010), pp. 85-114.
Richard A. Moy and David Rolnick, Novel structures in Stanley sequences, Discrete Math., Vol. 339, No. 2 (2016), pp. 689-698; arXiv preprint, arXiv:1502.06013 [math.CO], 2015.
A. M. Odlyzko and R. P. Stanley, Some curious sequences constructed with the greedy algorithm, 1978, remark 1 (PDF, PS, TeX).
Paul Pollack, Analytic and Combinatorial Number Theory Course Notes, p. 228. [?Broken link]
Paul Pollack, Analytic and Combinatorial Number Theory Course Notes, p. 228.
David Rolnick and Praveen S. Venkataramana, On the growth of Stanley sequences, Discrete Math., Vol. 338, No. 11 (2015), pp. 1928-1937, see p. 1930; arXiv preprint, arXiv:1408.4710 [math.CO], 2014.
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions.
Zoran Sunic, Tree morphisms, transducers and integer sequences, arXiv:math/0612080 [math.CO], 2006.
B. Vasic, K. Pedagani and M. Ivkovic, High-rate girth-eight low-density parity-check codes on rectangular integer lattices, IEEE Transactions on Communications, Vol. 52, Issue 8 (2004), pp. 1248-1252.
Eric Weisstein's World of Mathematics, Central Binomial Coefficient.
Index entries for 3-automatic sequences.

Cf. A039966 (characteristic function).
Cf. A002426, A004793, A005823, A007088, A007089, A032924, A033042-A033052, A054591, A055246, A062548, A065361, A074940, A081601, A081603, A081611, A083096, A089118, A121153, A170943, A185256.
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.
Row 3 of array A104257.
Summary of increasing sequences avoiding arithmetic progressions of specified lengths (the second of each pair is obtained by adding 1 to the first):
   3-term AP: A005836 (>=0), A003278 (>0);
   4-term AP: A005839 (>=0), A005837 (>0);
   5-term AP: A020654 (>=0), A020655 (>0);
   6-term AP: A020656 (>=0), A005838 (>0);
   7-term AP: A020657 (>=0), A020658 (>0);
   8-term AP: A020659 (>=0), A020660 (>0);
   9-term AP: A020661 (>=0), A020662 (>0);
  10-term AP: A020663 (>=0), A020664 (>0).
See also A000452.

a005836 n = a005836_list !! (n-1)
a005836_list = filter ((== 1) . a039966) [0..]
-- Reinhard Zumkeller, Jun 09 2012, Sep 29 2011

function a(n)
    m, r, b = n, 0, 1
    while m > 0
        m, q = divrem(m, 2)
        r += b * q
        b *= 3
    end
r end; [a(n) for n in 0:57] |> println # Peter Luschny, Jan 03 2021

t := (j, n) -> add(binomial(n,k)^j, k=0..n):
for i from 1 to 400 do
    if(t(4,i) mod 3 <>0) then print(i) fi
od; # Gary Detlefs, Nov 28 2011
# alternative Maple program:
a:= proc(n) option remember: local k, m:
if n=1 then 0 elif n=2 then 1 elif n>2 then k:=floor(log[2](n-1)): m:=n-2^k: procname(m)+3^k: fi: end proc:
seq(a(n), n=1.. 20); # Paul Weisenhorn, Mar 22 2020
# third Maple program:
a:= n-> `if`(n=1, 0, irem(n-1, 2, 'q')+3*a(q+1)):
seq(a(n), n=1..100);  # Alois P. Heinz, Jan 26 2022

Table[FromDigits[IntegerDigits[k, 2], 3], {k, 60}]
Select[Range[0, 400], DigitCount[#, 3, 2] == 0 &] (* Harvey P. Dale, Jan 04 2012 *)
Join[{0}, Accumulate[Table[(3^IntegerExponent[n, 2] + 1)/2, {n, 57}]]] (* IWABUCHI Yu(u)ki, Aug 01 2012 *)
FromDigits[#,3]&/@Tuples[{0,1},7] (* Harvey P. Dale, May 10 2019 *)

A=vector(100);for(n=2,#A,A[n]=if(n%2,3*A[n\2+1],A[n-1]+1));A \\ Charles R Greathouse IV, Jul 24 2012

is(n)=while(n,if(n%3>1,return(0));n\=3);1 \\ Charles R Greathouse IV, Mar 07 2013

a(n) = fromdigits(binary(n-1),3);  \\ Gheorghe Coserea, Jun 15 2018

def A005836(n):
    return int(format(n-1,'b'),3) # Chai Wah Wu, Jan 04 2015

a(n) = A005823(n)/2 = A003278(n)-1 = A033159(n)-2 = A033162(n)-3.
Numbers n such that the coefficient of x^n is > 0 in prod (k >= 0, 1 + x^(3^k)). - Benoit Cloitre, Jul 29 2003
a(n+1) = Sum_{k=0..m} b(k)* 3^k and n = Sum( b(k)* 2^k ).
a(2n+1) = 3a(n+1), a(2n+2) = a(2n+1) + 1, a(0) = 0.
a(n+1) = 3*a(floor(n/2)) + n - 2*floor(n/2). - Ralf Stephan, Apr 27 2003
G.f.: (x/(1-x)) * Sum_{k>=0} 3^k*x^2^k/(1+x^2^k). - Ralf Stephan, Apr 27 2003
a(n) = Sum_{k = 1..n-1} (1 + 3^A007814(k)) / 2. - Philippe Deléham, Jul 09 2005
From Reinhard Zumkeller, Mar 02 2008: (Start)
A081603(a(n)) = 0.
If the offset were changed to zero, then: a(0) = 0, a(n+1) = f(a(n)+1, a(n)+1) where f(x, y) = if x < 3 and x <> 2 then y else if x mod 3 = 2 then f(y+1, y+1) else f(floor(x/3), y). (End)
With offset a(0) = 0: a(n) = Sum_{k>=0} A030308(n,k)*3^k. - Philippe Deléham, Oct 15 2011
a(2^n) = A003462(n). - Philippe Deléham, Jun 06 2015
We have liminf_{n->infinity} a(n)/n^(log(3)/log(2)) = 1/2 and limsup_{n->infinity} a(n)/n^(log(3)/log(2)) = 1. - Gheorghe Coserea, Sep 13 2015
a(2^k+m) = a(m) + 3^k with 1 <= m <= 2^k and 1 <= k, a(1)=0, a(2)=1. - Paul Weisenhorn, Mar 22 2020
Sum_{n>=2} 1/a(n) = 2.682853110966175430853916904584699374821677091415714815171756609672281184705... (calculated using Baillie and Schmelzer's kempnerSums.nb, see Links). - Amiram Eldar, Feb 12 2022
A065361(a(n)) = n-1. - Rémy Sigrist, Feb 06 2023
a(n) ≍ n^k, where k = log 3/log 2 = 1.5849625007. (I believe the constant varies from 1/2 to 1.) - Charles R Greathouse IV, Mar 29 2024

Offset corrected by N. J. A. Sloane, Mar 02 2008

Edited by the Associate Editors of the OEIS, Apr 07 2009

A001316 Gould's sequence: a(n) = Sum_{k=0..n} (binomial(n,k) mod 2); number of odd entries in row n of Pascal's triangle (A007318); a(n) = 2^A000120(n).

Original entry on oeis.org

1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, 4, 8, 8, 16, 8, 16, 16, 32, 8, 16, 16, 32, 16, 32, 32, 64, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, 4, 8, 8, 16, 8, 16, 16, 32

Offset: 0

N. J. A. Sloane

Also called Dress's sequence.
This sequence might be better called Glaisher's sequence, since James Glaisher showed that odd binomial coefficients are counted by 2^A000120(n) in 1899. - Eric Rowland, Mar 17 2017 [However, the name "Gould's sequence" is deeply entrenched in the literature. - N. J. A. Sloane, Mar 17 2017] [Named after the American mathematician Henry Wadsworth Gould (b. 1928). - Amiram Eldar, Jun 19 2021]
All terms are powers of 2. The first occurrence of 2^k is at n = 2^k - 1; e.g., the first occurrence of 16 is at n = 15. - Robert G. Wilson v, Dec 06 2000
a(n) is the highest power of 2 dividing binomial(2n,n) = A000984(n). - Benoit Cloitre, Jan 23 2002
Also number of 1's in n-th row of triangle in A070886. - Hans Havermann, May 26 2002. Equivalently, number of live cells in generation n of a one-dimensional cellular automaton, Rule 90, starting with a single live cell. - Ben Branman, Feb 28 2009. Ditto for Rule 18. - N. J. A. Sloane, Aug 09 2014. This is also the odd-rule cellular automaton defined by OddRule 003 (see Ekhad-Sloane-Zeilberger "Odd-Rule Cellular Automata on the Square Grid" link). - N. J. A. Sloane, Feb 25 2015
Also number of numbers k, 0<=k<=n, such that (k OR n) = n (bitwise logical OR): a(n) = #{k : T(n,k)=n, 0<=k<=n}, where T is defined as in A080098. - Reinhard Zumkeller, Jan 28 2003
To construct the sequence, start with 1 and use the rule: If k >= 0 and a(0),a(1),...,a(2^k-1) are the first 2^k terms, then the next 2^k terms are 2*a(0),2*a(1),...,2*a(2^k-1). - Benoit Cloitre, Jan 30 2003
Also, numerator((2^k)/k!). - Mohammed Bouayoun (mohammed.bouayoun(AT)sanef.com), Mar 03 2004
The odd entries in Pascal's triangle form the Sierpiński Gasket (a fractal). - Amarnath Murthy, Nov 20 2004
Row sums of Sierpiński's Gasket A047999. - Johannes W. Meijer, Jun 05 2011
Fixed point of the morphism "1" -> "1,2", "2" -> "2,4", "4" -> "4,8", ..., "2^k" -> "2^k,2^(k+1)", ... starting with a(0) = 1; 1 -> 12 -> 1224 -> = 12242448 -> 122424482448488(16) -> ... . - Philippe Deléham, Jun 18 2005
a(n) = number of 1's of stage n of the one-dimensional cellular automaton with Rule 90. - Andras Erszegi (erszegi.andras(AT)chello.hu), Apr 01 2006
a(33)..a(63) = A117973(1)..A117973(31). - Stephen Crowley, Mar 21 2007
Or the number of solutions of the equation: A000120(x) + A000120(n-x) = A000120(n). - Vladimir Shevelev, Jul 19 2009
For positive n, a(n) equals the denominator of the permanent of the n X n matrix consisting entirely of (1/2)'s. - John M. Campbell, May 26 2011
Companions to A001316 are A048896, A105321, A117973, A151930 and A191488. They all have the same structure. We observe that for all these sequences a((2*n+1)*2^p-1) = C(p)*A001316(n), p >= 0. If C(p) = 2^p then a(n) = A001316(n), if C(p) = 1 then a(n) = A048896(n), if C(p) = 2^p+2 then a(n) = A105321(n+1), if C(p) = 2^(p+1) then a(n) = A117973(n), if C(p) = 2^p-2 then a(n) = (-1)*A151930(n) and if C(p) = 2^(p+1)+2 then a(n) = A191488(n). Furthermore for all a(2^p - 1) = C(p). - Johannes W. Meijer, Jun 05 2011
a(n) = number of zeros in n-th row of A219463 = number of ones in n-th row of A047999. - Reinhard Zumkeller, Nov 30 2012
This is the Run Length Transform of S(n) = {1,2,4,8,16,...} (cf. A000079). The Run Length Transform of a sequence {S(n), n>=0} is defined to be the sequence {T(n), n>=0} given by T(n) = Product_i S(i), where i runs through the lengths of runs of 1's in the binary expansion of n. E.g., 19 is 10011 in binary, which has two runs of 1's, of lengths 1 and 2. So T(19) = S(1)*S(2). T(0)=1 (the empty product). - N. J. A. Sloane, Sep 05 2014
A105321(n+1) = a(n+1) + a(n). - Reinhard Zumkeller, Nov 14 2014
a(n) = A261363(n,n) = number of distinct terms in row n of A261363 = number of odd terms in row n+1 of A261363. - Reinhard Zumkeller, Aug 16 2015
From Gary W. Adamson, Aug 26 2016: (Start)
A production matrix for the sequence is lim_{k->infinity} M^k, the left-shifted vector of M:
  1, 0, 0, 0, 0, ...
  2, 0, 0, 0, 0, ...
  0, 1, 0, 0, 0, ...
  0, 2, 0, 0, 0, ...
  0, 0, 1, 0, 0, ...
  0, 0, 2, 0, 0, ...
  0, 0, 0, 1, 0, ...
  ...
The result is equivalent to the g.f. of Apr 06 2003: Product_{k>=0} (1 + 2*z^(2^k)). (End)
Number of binary palindromes of length n for which the first floor(n/2) symbols are themselves a palindrome (Ji and Wilf 2008). - Jeffrey Shallit, Jun 15 2017

			Has a natural structure as a triangle:
  1,
  2,
  2,4,
  2,4,4,8,
  2,4,4,8,4,8,8,16,
  2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32,
  2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32,4,8,8,16,8,16,16,32,8,16,16,32,16,32,32,64,
  ...
The rows converge to A117973.
From _Omar E. Pol_, Jun 07 2009: (Start)
Also, triangle begins:
   1;
   2,2;
   4,2,4,4;
   8,2,4,4,8,4,8,8;
  16,2,4,4,8,4,8,8,16,4,8,8,16,8,16,16;
  32,2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32,4,8,8,16,8,16,16,32,8,16,16,32,16,32,32;
  64,2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32,4,8,8,16,8,16,16,32,8,16,16,32,16,32,...
(End)
G.f. = 1 + 2*x + 2*x^2 + 4*x^3 + 2*x^4 + 4*x^5 + 4*x^6 + 8*x^7 + 2*x^8 + ... - _Michael Somos_, Aug 26 2015

Arthur T. Benjamin and Jennifer J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A., 2003, p. 75ff.
Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 145-151.
James W. L. Glaisher, On the residue of a binomial-theorem coefficient with respect to a prime modulus, Quarterly Journal of Pure and Applied Mathematics, Vol. 30 (1899), pp. 150-156.
H. W. Gould, Exponential Binomial Coefficient Series. Tech. Rep. 4, Math. Dept., West Virginia Univ., Morgantown, WV, Sep 1961.
Olivier Martin, Andrew M. Odlyzko, and Stephen Wolfram, Algebraic properties of cellular automata, Comm. Math. Physics, Vol. 93 (1984), pp. 219-258. Reprinted in Theory and Applications of Cellular Automata, S Wolfram, Ed., World Scientific, 1986, pp. 51-90 and in Cellular Automata and Complexity: Collected Papers of Stephen Wolfram, Addison-Wesley, 1994, pp. 71-113
Manfred R. Schroeder, Fractals, Chaos, Power Laws, W. H. Freeman, NY, 1991, page 383.
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).
Andrew Wuensche, Exploring Discrete Dynamics, Luniver Press, 2011. See Fig. 2.3.

Indranil Ghosh, Table of n, a(n) for n = 0..50000 (terms 0..1000 from T. D. Noe)
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.]
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., Vol. 98 (1992), pp. 163-197.
Paul Barry, A Note on Riordan Arrays with Catalan Halves, arXiv:1912.01124 [math.CO], 2019.
George Beck and Karl Dilcher, A Matrix Related to Stern Polynomials and the Prouhet-Thue-Morse Sequence, arXiv:2106.10400 [math.CO], 2021.
Christina Talar Bekaroğlu, Analyzing Dynamics of Larger than Life: Impacts of Rule Parameters on the Evolution of a Bug's Geometry, Master's thesis, Calif. State Univ. Northridge (2023). See pp. 91-92.
Neil J. Calkin, Eunice Y. S. Chan, and Robert M. Corless, Some Facts and Conjectures about Mandelbrot Polynomials, Maple Transactions (2021) Vol. 1, No. 1, Article 1.
Neil J. Calkin, Eunice Y. S. Chan, Robert M. Corless, David J. Jeffrey, and Piers W. Lawrence, A Fractal Eigenvector, arXiv:2104.01116 [math.DS], 2021.
Emeric Deutsch and Bruce E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, arXiv:math/0407326 [math.CO], 2004.
Emeric Deutsch and Bruce E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Num. Theory, Vol. 117 (2006), pp. 191-215.
Philippe Dumas, Diviser pour régner Comportement asymptotique.
Philippe Dumas, Diviser pour régner Comportement asymptotique. (has many references)
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, A Meta-Algorithm for Creating Fast Algorithms for Counting ON Cells in Odd-Rule Cellular Automata, arXiv:1503.01796 [math.CO], 2015; see also the Accompanying Maple Package.
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, Odd-Rule Cellular Automata on the Square Grid, arXiv:1503.04249 [math.CO], 2015.
Steven R. Finch, Stolarsky-Harborth Constant. [Broken link]
Steven R. Finch, Stolarsky-Harborth Constant. [From the Wayback machine]
Ignas Gasparavičius, Andrius Grigutis, and Juozas Petkelis, Picturesque convolution-like recurrences and partial sums' generation, arXiv:2507.23619 [math.NT], 2025. See p. 28.
Michael Gilleland, Some Self-Similar Integer Sequences.
Po-Yi Huang and Wen-Fong Ke, Sequences Derived from The Symmetric Powers of {1, 2, ..., k}, arXiv:2307.07733 [math.CO], 2023.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Periodic minimum in the count of binomial coefficients not divisible by a prime, arXiv:2408.06817 [math.NT], 2024.
Kathy Q. Ji and Herbert S. Wilf, Extreme Palindromes, Amer. Math. Monthly, Vol. 115, No. 5 (2008), pp. 447-451.
Alan J. Macfarlane, Generating functions for integer sequences defined by the evolution of cellular automata....
Hans Montanus and Ron Westdijk, Cellular Automation and Binomials, Green Blue Mathematics (2022), p. 57.
Sam Northshield, Stern's Diatomic Sequence 0,1,1,2,1,3,2,3,1,4,..., Amer. Math. Month., Vol. 117, No. 7 (2010), pp. 581-598.
Tomaz Pisanski and Thomas W. Tucker, Growth in Repeated Truncations of Maps, Atti Sem. Mat. Fis. Univ. Modena, Vol. 49 (2001), suppl., pp. 167-176.
David G. Poole, The towers and triangles of Professor Claus (or, Pascal knows Hanoi), Math. Mag., Vol. 67, No. 5 (1994), pp. 323-344.
Joseph M. Shunia, A Polynomial Ring Connecting Central Binomial Coefficients and Gould's Sequence, arXiv:2312.00302 [math.GM], 2023.
N. J. A. Sloane, Illustration of first 20 generations of Rule 90.
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS.
Lukas Spiegelhofer and Michael Wallner, Divisibility of binomial coefficients by powers of two, arXiv:1710.10884 [math.NT], 2017.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Alexander Yu. Vlasov, Modelling reliability of reversible circuits with 2D second-order cellular automata, arXiv:2312.13034 [nlin.CG], 2023. See page 12.
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton.
Stephen Wolfram, Statistical mechanics of cellular automata, Rev. Mod. Phys., Vol. 55 (1983), pp. 601-644.
Stephen Wolfram, Geometry of Binomial Coefficients, Amer. Math. Monthly, Vol. 91, No. 9 (November 1984), pp. 566-571.
Chai Wah Wu, Sums of products of binomial coefficients mod 2 and run length transforms of sequences, arXiv preprint arXiv:1610.06166 [math.CO], 2016.
Zhujun Zhang, A Note on Counting Binomial Heaps, ResearchGate (2019).
Index entries for sequences related to cellular automata
Index entries for sequences that are fixed points of mappings
Index entries for sequences computed with run length transform

Equals left border of triangle A166548. - Gary W. Adamson, Oct 16 2009
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.
For partial sums see A006046. For first differences see A151930.
This is the numerator of 2^n/n!, while A049606 gives the denominator.
Cf. A051638, A048967, A007318, A094959, A048896, A117973, A008977, A139541, A048883, A102376, A038573, A159913, A000079, A166548, A006047, A089898, A105321, A061142.
Cf. A047999, A261363, A261366.
If we subtract 1 from the terms we get a pair of essentially identical sequences, A038573 and A159913.
A163000 and A163577 count binomial coefficients with 2-adic valuation 1 and 2. A275012 gives a measure of complexity of these sequences. - Eric Rowland, Mar 15 2017
Cf. A286575 (run-length transform), A368655 (binomial transform), also A037445.

import Data.List (transpose)
a001316 = sum . a047999_row  -- Reinhard Zumkeller, Nov 24 2012
a001316_list = 1 : zs where
   zs = 2 : (concat $ transpose [zs, map (* 2) zs])
-- Reinhard Zumkeller, Aug 27 2014, Sep 16 2011
(Sage, Python)
from functools import cache
@cache
def A001316(n):
    if n <= 1: return n+1
    return A001316(n//2) << n%2
print([A001316(n) for n in range(88)])  # Peter Luschny, Nov 19 2012

A001316 := proc(n) local k; add(binomial(n,k) mod 2, k=0..n); end;
S:=[1]; S:=[op(S),op(2*s)]; # repeat ad infinitum!
a := n -> 2^add(i,i=convert(n,base,2)); # Peter Luschny, Mar 11 2009

Table[ Sum[ Mod[ Binomial[n, k], 2], {k, 0, n} ], {n, 0, 100} ]
Nest[ Join[#, 2#] &, {1}, 7] (* Robert G. Wilson v, Jan 24 2006 and modified Jul 27 2014 *)
Map[Function[Apply[Plus,Flatten[ #1]]], CellularAutomaton[90,{{1},0},100]] (* Produces counts of ON cells. N. J. A. Sloane, Aug 10 2009 *)
ArrayPlot[CellularAutomaton[90, {{1}, 0}, 20]] (* Illustration of first 20 generations. - N. J. A. Sloane, Aug 14 2014 *)
Table[2^(RealDigits[n - 1, 2][[1]] // Total), {n, 1, 100}] (* Gabriel C. Benamy, Dec 08 2009 *)
CoefficientList[Series[Exp[2*x], {x, 0, 100}], x] // Numerator (* Jean-François Alcover, Oct 25 2013 *)
Count[#,?OddQ]&/@Table[Binomial[n,k],{n,0,90},{k,0,n}] (* _Harvey P. Dale, Sep 22 2015 *)
2^DigitSum[Range[0, 100], 2] (* Paolo Xausa, Jul 31 2025 *)

{a(n) = if( n<0, 0, numerator(2^n / n!))};

PARI
```
A001316(n)=1<M. F. Hasler, May 03 2009
```

a(n)=2^hammingweight(n) \\ Charles R Greathouse IV, Jan 04 2013

def A001316(n):
    return 2**bin(n)[2:].count("1") # Indranil Ghosh, Feb 06 2017

def A001316(n): return 1<Karl-Heinz Hofmann, Aug 01 2025

import numpy # (version >= 2.0.0)
n_up_to = 2**22
A000079 = 1 << numpy.arange(n_up_to.bit_length())
A001316 = A000079[numpy.bitwise_count(numpy.arange(n_up_to))]
print(A001316[0:100]) # Karl-Heinz Hofmann, Aug 01 2025

(define (A001316 n) (let loop ((n n) (z 1)) (cond ((zero? n) z) ((even? n) (loop (/ n 2) z)) (else (loop (/ (- n 1) 2) (* z 2)))))) ;; Antti Karttunen, May 29 2017

a(n) = 2^A000120(n).
a(0) = 1; for n > 0, write n = 2^i + j where 0 <= j < 2^i; then a(n) = 2*a(j).
a(n) = 2*a(n-1)/A006519(n) = A000079(n)*A049606(n)/A000142(n).
a(n) = A038573(n) + 1.
G.f.: Product_{k>=0} (1+2*z^(2^k)). - Ralf Stephan, Apr 06 2003
a(n) = Sum_{i=0..2*n} (binomial(2*n, i) mod 2)*(-1)^i. - Benoit Cloitre, Nov 16 2003
a(n) mod 3 = A001285(n). - Benoit Cloitre, May 09 2004
a(n) = 2^n - 2*Sum_{k=0..n} floor(binomial(n, k)/2). - Paul Barry, Dec 24 2004
a(n) = Product_{k=0..log_2(n)} 2^b(n, k), b(n, k) = coefficient of 2^k in binary expansion of n. - Paul D. Hanna
Sum_{k=0..n-1} a(k) = A006046(n).
a(n) = n/2 + 1/2 + (1/2)*Sum_{k=0..n} (-(-1)^binomial(n,k)). - Stephen Crowley, Mar 21 2007
G.f. for a(n)/A156769(n): (1/2)*z^(1/2)*sinh(2*z^(1/2)). - Johannes W. Meijer, Feb 20 2009
Equals infinite convolution product of [1,2,0,0,0,0,0,0,0] aerated (A000079 - 1) times, i.e., [1,2,0,0,0,0,0,0,0] * [1,0,2,0,0,0,0,0,0] * [1,0,0,0,2,0,0,0,0]. - Mats Granvik, Gary W. Adamson, Oct 02 2009
a(n) = f(n, 1) with f(x, y) = if x = 0 then y otherwise f(floor(x/2), y*(1 + x mod 2)). - Reinhard Zumkeller, Nov 21 2009
a(n) = 2^(number of 1's in binary form of (n-1)). - Gabriel C. Benamy, Dec 08 2009
a((2*n+1)*2^p-1) = (2^p)*a(n), p >= 0. - Johannes W. Meijer, Jun 05 2011
a(n) = A000120(A001317(n)). - Reinhard Zumkeller, Nov 24 2012
a(n) = A226078(n,1). - Reinhard Zumkeller, May 25 2013
a(n) = lcm(n!, 2^n) / n!. - Daniel Suteu, Apr 28 2017
a(n) = A061142(A005940(1+n)). - Antti Karttunen, May 29 2017
a(0) = 1, a(2*n) = a(n), a(2*n+1) = 2*a(n). - Daniele Parisse, Feb 15 2024
a(n*m) <= a(n)^A000120(m). - Joe Amos, Mar 27 2025

Additional comments from Henry Bottomley, Mar 12 2001

Further comments from N. J. A. Sloane, May 30 2009

A147582 First differences of A147562.

Original entry on oeis.org

1, 4, 4, 12, 4, 12, 12, 36, 4, 12, 12, 36, 12, 36, 36, 108, 4, 12, 12, 36, 12, 36, 36, 108, 12, 36, 36, 108, 36, 108, 108, 324, 4, 12, 12, 36, 12, 36, 36, 108, 12, 36, 36, 108, 36, 108, 108, 324, 12, 36, 36, 108, 36, 108, 108, 324, 36, 108, 108, 324, 108, 324, 324, 972, 4

Offset: 1

N. J. A. Sloane, Apr 29 2009

nonn

Bisection of A323651. - Omar E. Pol, Mar 04 2019

			From _Omar E. Pol_, Jun 14 2009: (Start)
When written as a triangle:
.1;
.4;
.4,12;
.4,12,12,36;
.4,12,12,36,12,36,36,108;
.4,12,12,36,12,36,36,108,12,36,36,108,36,108,108,324;
.4,12,12,36,12,36,36,108,12,36,36,108,36,108,108,324,12,36,36,108,36,108,...
The rows converge to A161411. (End)

D. Singmaster, On the cellular automaton of Ulam and Warburton, M500 Magazine of the Open University, #195 (December 2003), pp. 2-7.
S. Ulam, On some mathematical problems connected with patterns of growth of figures, pp. 215-224 of R. E. Bellman, ed., Mathematical Problems in the Biological Sciences, Proc. Sympos. Applied Math., Vol. 14, Amer. Math. Soc., 1962.

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 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, The movie version
Omar E. Pol, Illustration of initial terms (Fig. 1: one-step rook), (Fig. 2: one-step bishop), (Fig. 3: overlapping squares), (Fig. 4: overlapping X-toothpicks), 2009
Omar E. Pol, Illustration of initial terms of A139251, A160121, A147582 (Overlapping figures), 2009
D. Singmaster, On the cellular automaton of Ulam and Warburton, 2003 [Cached copy, included with permission]
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
N. J. A. Sloane, Exciting Number Sequences (video of talk), Mar 05 2021

Cf. A147562, A147610 (the sequence divided by 4), A048881, A000120.
Cf. A000079, A161411, A151779, A139250.
Cf. A048883, A139251, A160121, A162349. [Omar E. Pol, Nov 02 2009]
Cf. A323651.

A000120 := proc(n) local w,m,i; w := 0; m := n; while m > 0 do i := m mod 2; w := w+i; m := (m-i)/2; od; w; end: wt := A000120; A147582 := n-> if n <= 1 then n else 4*3^(wt(n-1)-1); fi; [seq(A147582(n),n=0..1000)]; # N. J. A. Sloane, Apr 07 2010

s = Plus @@ Flatten@ # & /@ CellularAutomaton[{686, {2, {{0, 2, 0}, {2, 1, 2}, {0, 2, 0}}}, {1, 1}}, {{{1}}, 0}, 200]; f[n_] = If[n == 0, 1, s[[n + 1]] - s[[n]]]; Array[f, 120, 0] (* Michael De Vlieger, Apr 09 2015, after Nadia Heninger and N. J. A. Sloane at A147562 *)

a(1) = 1; for n > 1, a(n) = 4*3^(wt(n-1)-1) where wt() = A000120(). - R. J. Mathar, Apr 30 2009
This formula is (essentially) given by Singmaster. - N. J. A. Sloane, Aug 06 2009
G.f.: x + 4*x*(Product_{k >= 0} (1 + 3*x^(2^k)) - 1)/3. - N. J. A. Sloane, Jun 10 2009

Extended by R. J. Mathar, Apr 30 2009

A102376 a(n) = 4^A000120(n).

Original entry on oeis.org

1, 4, 4, 16, 4, 16, 16, 64, 4, 16, 16, 64, 16, 64, 64, 256, 4, 16, 16, 64, 16, 64, 64, 256, 16, 64, 64, 256, 64, 256, 256, 1024, 4, 16, 16, 64, 16, 64, 64, 256, 16, 64, 64, 256, 64, 256, 256, 1024, 16, 64, 64, 256, 64, 256, 256, 1024, 64, 256, 256, 1024, 256, 1024, 1024

Offset: 0

Paul Barry, Jan 05 2005

Consider a simple cellular automaton, a grid of binary cells c(i,j), where the next state of the grid is calculated by applying the following rule to each cell: c(i,j) = ( c(i+1,j-1) + c(i+1,j+1) + c(i-1,j-1) + c(i-1,j+1) ) mod 2 If we start with a single cell having the value 1 and all the others 0, then the aggregate values of the subsequent states of the grid will be the terms in this sequence. - Andras Erszegi (erszegi.andras(AT)chello.hu), Mar 31 2006. See link for initial states. - N. J. A. Sloane, Feb 12 2015
This is the odd-rule cellular automaton defined by OddRule 033 (see Ekhad-Sloane-Zeilberger "Odd-Rule Cellular Automata on the Square Grid" link). - N. J. A. Sloane, Feb 25 2015
First differences of A116520. - Omar E. Pol, May 05 2010

			1 + 4*x + 4*x^2 + 16*x^3 + 4*x^4 + 16*x^5 + 16*x^6 + 64*x^7 + 4*x^8 + ...
From _Omar E. Pol_, Jun 07 2009: (Start)
Triangle begins:
  1;
  4;
  4,16;
  4,16,16,64;
  4,16,16,64,16,64,64,256;
  4,16,16,64,16,64,64,256,16,64,64,256,64,256,256,1024;
  4,16,16,64,16,64,64,256,16,64,64,256,64,256,256,1024,16,64,64,256,64,256,...
(End)

N. J. A. Sloane, Table of n, a(n) for n = 0..10000
David Applegate, Omar E. Pol, and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, A Meta-Algorithm for Creating Fast Algorithms for Counting ON Cells in Odd-Rule Cellular Automata, arXiv:1503.01796 [math.CO], 2015; see also the Accompanying Maple Package.
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, Odd-Rule Cellular Automata on the Square Grid, arXiv:1503.04249 [math.CO], 2015.
Nathan Epstein, Animation of CA generating A102376
N. J. A. Sloane, On the No. of ON Cells in Cellular Automata, Video of talk in Doron Zeilberger's Experimental Math Seminar at Rutgers University, Feb. 05 2015: Part 1, Part 2
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
N. J. A. Sloane, Illustration of generations 0-15 of the cellular automaton
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Alexander Yu. Vlasov, Modelling reliability of reversible circuits with 2D second-order cellular automata, arXiv:2312.13034 [nlin.CG], 2023. See page 13.
Index entries for sequences related to cellular automata

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.
A151783 is a very similar sequence.
Cf. A001316, A048883, A000079, A116520, A000302.
See A160239 for the analogous CA defined by Rule 204 on an 8-celled neighborhood.

a102376 = (4 ^) . a000120  -- Reinhard Zumkeller, Feb 13 2015

seq(4^convert(convert(n,base,2),`+`),n=0..100); # Robert Israel, Apr 30 2017

Table[4^DigitCount[n, 2, 1], {n, 0, 100}] (* Indranil Ghosh, Apr 30 2017 *)

{a(n) = if( n<0, 0, 4^subst( Pol( binary(n)), x, 1))} /* Michael Somos, May 29 2008 */
a(n) = 4^hammingweight(n); \\ Michel Marcus, Apr 30 2017

def a(n): return 4**bin(n)[2:].count("1") # Indranil Ghosh, Apr 30 2017

def A102376(n): return 1<<(n.bit_count()<<1) # Chai Wah Wu, Nov 15 2022

Formulas due to Paul D. Hanna: (Start)
G.f.: Product_{k>=0} 1 + 4x^(2^k).
a(n) = Product_{k=0..log_2(n)} 4^b(n, k), b(n, k)=coefficient of 2^k in binary expansion of n.
a(n) = Sum_{k=0..n} (C(n, k) mod 2)*3^A000120(n-k). (End)
a(n) = Sum_{k=0..n} (C(n, k) mod 2) * Sum_{j=0..k} (C(k, j) mod 2) * Sum_{i=0..j} (C(j, i) mod 2). - Paul Barry, Apr 01 2005
G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^4)) where f(u, v, w) = w * (u^2 - 2*u*v + 5*v^2) - 4*v^3. - Michael Somos, May 29 2008
Run length transform of A000302. - N. J. A. Sloane, Feb 23 2015

cp's OEIS Frontend

A173451 a(n) = A048883(n-1) - A160121(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A173452 a(n) = A048883(n-1) - A151710(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A151712 a(n) = A048883(n) + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A374799 Irregular table T(n, k), n >= 0, k = 1..A048883(n), read by rows; the n-th row lists the numbers m such that A003986(m) = n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A162784 a(n) = (A048883(n)+1)/2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A000695 Moser-de Bruijn sequence: sums of distinct powers of 4.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

C

Haskell

Julia

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Python

Python

Sage

Formula

A005836 Numbers whose base-3 representation contains no 2.

Views

Author

Keywords