A048883 -id:A048883 - cp's OEIS frontend

A033042 Sums of distinct powers of 5.

0, 1, 5, 6, 25, 26, 30, 31, 125, 126, 130, 131, 150, 151, 155, 156, 625, 626, 630, 631, 650, 651, 655, 656, 750, 751, 755, 756, 775, 776, 780, 781, 3125, 3126, 3130, 3131, 3150, 3151, 3155, 3156, 3250, 3251, 3255, 3256, 3275, 3276, 3280, 3281, 3750, 3751

Offset: 0

Clark Kimberling

Numbers without any base-5 digits larger than 1.
a(n) modulo 2 is the Prouhet-Thue-Morse sequence A010060. - Philippe Deléham, Oct 17 2011
Values of k where A008977(k) does not end with 0. - Henry Bottomley, Nov 09 2022

T. D. Noe, Table of n, a(n) for n = 0..1023
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.]
K. Dilcher and L. Ericksen, Hyperbinary expansions and Stern polynomials, Elec. J. Combin, 22, 2015, #P2.24.
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.
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

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.
Cf. A000695, A005836, A008977, A010060, A033043-A033052.
Row 5 of array A104257.

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

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*5 od; r
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Mar 16 2013

t = Table[FromDigits[RealDigits[n, 2], 5], {n, 1, 100}]
(* Clark Kimberling, Aug 02 2012 *)
FromDigits[#,5]&/@Tuples[{0,1},7] (* Harvey P. Dale, May 22 2018 *)

a(n) = subst(Pol(binary(n)), 'x, 5);
vector(50, i, a(i-1))  \\ Gheorghe Coserea, Sep 15 2015

a(n)=fromdigits(binary(n),5) \\ Charles R Greathouse IV, Jan 11 2017

def A033042(n): return int(bin(n)[2:],5) # Chai Wah Wu, Oct 30 2024

a(n) = Sum_{i=0..m} d(i)*5^i, where Sum_{i=0..m} d(i)*2^i is the base-2 representation of n.
Numbers j such that the coefficient of x^j is > 0 in Product_{k>=0} (1 + x^(5^k)). - Benoit Cloitre, Jul 29 2003
a(n) = A097251(n)/4.
a(2n) = 5*a(n), a(2n+1) = a(2n)+1.
a(n) = Sum_{k>=0} A030308(n,k)*5^k. - Philippe Deléham, Oct 17 2011
liminf a(n)/n^(log(5)/log(2)) = 1/4 and limsup a(n)/n^(log(5)/log(2)) = 1. - Gheorghe Coserea, Sep 15 2015
G.f.: (1/(1 - x))*Sum_{k>=0} 5^k*x^(2^k)/(1 + x^(2^k)). - Ilya Gutkovskiy, Jun 04 2017

Extended by Ray Chandler, Aug 03 2004

A039966 a(0) = 1; thereafter a(3n+2) = 0, a(3n) = a(3n+1) = a(n).

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

N. J. A. Sloane, Dec 11 1999

nonn

Number of partitions of n into distinct powers of 3.
Trajectory of 1 under the morphism: 1 -> 110, 0 -> 000. Thus 1 -> 110 ->110110000 -> 110110000110110000000000000 -> ... - Philippe Deléham, Jul 09 2005
Also, an example of a d-perfect sequence.
This is a composite of two earlier sequences contributed at different times by N. J. A. Sloane and by Reinhard Zumkeller, Mar 05 2005. Christian G. Bower extended them and found that they agreed for at least 512 terms. The proof that they were identical was found by Ralf Stephan, Jun 13 2005, based on the fact that they were both 3-regular sequences.

			The triples of elements (a(3k), a(3k+1), a(3k+2)) are (1,1,0) if a(k) = 1 and (0,0,0) if a(k) = 0.  So since a(2) = 0, a(6) = a(7) = a(8) = 0, and since a(3) = 1, a(9) = a(10) = 1 and a(11) = 0. - _Michael B. Porter_, Jul 11 2016

Reinhard Zumkeller, 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.]
D. Kohel, S. Ling and C. Xing, Explicit Sequence Expansions, in Sequences and their Applications, C. Ding, T. Helleseth, and H. Niederreiter, eds., Proceedings of SETA'98 (Singapore, 1998), 308-317, 1999.
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Index entries for sequences that are fixed points of mappings
Index entries for characteristic functions

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.
Cf. A062051, A000009, A000244, A004642.
Characteristic function of A005836 (and apart from offset of A003278).

a039966 n = fromEnum (n < 2 || m < 2 && a039966 n' == 1)
   where (n',m) = divMod n 3
-- Reinhard Zumkeller, Sep 29 2011

a := proc(n) option remember; if n <= 1 then RETURN(1) end if; if n = 2 then RETURN(0) end if; if n mod 3 = 2 then RETURN(0) end if; if n mod 3 = 0 then RETURN(a(1/3*n)) end if; if n mod 3 = 1 then RETURN(a(1/3*n - 1/3)) end if end proc; # Ralf Stephan, Jun 13 2005

(* first do *) Needs["DiscreteMath`Combinatorica`"] (* then *) s = Rest[ Sort[ Plus @@@ Table[UnrankSubset[n, Table[3^i, {i, 0, 4}]], {n, 32}]]]; Table[ If[ Position[s, n] == {}, 0, 1], {n, 105}] (* Robert G. Wilson v, Jun 14 2005 *)
CoefficientList[Series[Product[(1 + x^(3^k)), {k, 0, 5}], {x, 0, 111}], x] (* or *)
Nest[ Flatten[ # /. {0 -> {0, 0, 0}, 1 -> {1, 1, 0}}] &, {1}, 5] (* Robert G. Wilson v, Mar 29 2006 *)
Nest[ Join[#, #, 0 #] &, {1}, 5] (* Robert G. Wilson v, Jul 27 2014 *)

{a(n)=local(A,m); if(n<0, 0, m=1; A=1+O(x); while(m<=n, m*=3; A=(1+x)*subst(A,x,x^3)); polcoeff(A,n))} /* Michael Somos, Jul 15 2005 */

A039966(n)=vecmax(digits(n+!n,3))<2;
apply(A039966, [0..99]) \\ M. F. Hasler, Feb 15 2023

def A039966(n):
    while n > 2:
        n,r = divmod(n,3)
        if r==2: return 0
    return int(n!=2) # M. F. Hasler, Feb 15 2023

a(0) = 1, a(1) = 0, a(n) = b(n-2), where b is the sequence defined by b(0) = 1, b(3n+2) = 0, b(3n) = b(3n+1) = b(n). - Ralf Stephan
a(n) = A005043(n-1) mod 3. - Christian G. Bower, Jun 12 2005
a(n) = A002426(n) mod 3. - John M. Campbell, Aug 24 2011
a(n) = A000275(n) mod 3. - John M. Campbell, Jul 08 2016
Properties: 0 <= a(n) <= 1, a(A074940(n)) = 0, a(A005836(n)) = 1; A104406(n) = Sum(a(k), 1 <= k <= n). - Reinhard Zumkeller, Mar 05 2005
Euler transform of sequence b(n) where b(3^k) = 1, b(2*3^k) = -1 and zero otherwise. - Michael Somos, Jul 15 2005
G.f. A(x) satisfies A(x) = (1+x)*A(x^3). - Michael Somos, Jul 15 2005
G.f.: Product{k>=0} 1+x^(3^k). Exponents give A005836.

Entry revised Jun 30 2005

Offset corrected by John M. Campbell, Aug 24 2011

A130665 a(n) = Sum_{k=0..n} 3^wt(k), where wt() = A000120().

Original entry on oeis.org

1, 4, 7, 16, 19, 28, 37, 64, 67, 76, 85, 112, 121, 148, 175, 256, 259, 268, 277, 304, 313, 340, 367, 448, 457, 484, 511, 592, 619, 700, 781, 1024, 1027, 1036, 1045, 1072, 1081, 1108, 1135, 1216, 1225, 1252, 1279, 1360, 1387, 1468, 1549, 1792, 1801, 1828, 1855

Offset: 0

N. J. A. Sloane, based on a message from Don Knuth, Jun 23 2007

Partial sums of A048883. - David Applegate, Jun 11 2009
From Gary W. Adamson, Aug 26 2016: (Start)
The formula of Mar 26 2010 is equivalent to the left-shifted vector of matrix powers (lim_{k->infinity} M^k), of the production matrix M:
  1, 0, 0, 0, 0, 0, ...
  4, 0, 0, 0, 0, 0, ...
  3, 1, 0, 0, 0, 0, ...
  0, 4, 0, 0, 0, 0, ...
  0, 3, 1, 0, 0, 0, ...
  0, 0, 4, 0, 0, 0, ...
  0, 0, 3, 1, 0, 0, ...
  ...
The sequence divided by its aerated variant is (1, 4, 3, 0, 0, 0, ...). (End)

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
David Applegate, The movie version
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, pp. 27, 31-32.
Tanya Khovanova and Joshua Xiong, Nim Fractals, arXiv:1405.594291 [math.CO], 2014 and J. Int. Seq. 17 (2014) # 14.7.8.
D. E. Knuth, Problem 11320 Amer. Math. Monthly, Vol. 114 No. 9 (Nov 2007) p. 835.
Omar E. Pol, Illustration of initial terms: Fig. 1. Neighbors of the vertices, Fig. 2. Overlapping squares, Fig. 3. One-step bishop, (Nov 08 2009)
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Mike Warburton, Ulam-Warburton Automaton - Counting Cells with Quadratics, arXiv:1901.10565 [math.CO], 2019.

Cf. A000120, A006046 (Sum 2^wt(n)), A116520, A130667, A147562, A151920, A151922, A160410, A160412, A360189.

a130665 = sum . map (3 ^) . (`take` a000120_list) . (+ 1)
-- Reinhard Zumkeller, Apr 18 2012

u:=3; a[1]:=1; M:=30; for n from 1 to M do a[2*n] := (u+1)*a[n]; a[2*n+1] := u*a[n] + a[n+1]; od; t1:=[seq( a[n], n=1..2*M )]; # Gives sequence with a different offset

f[n_] := Sum[3^Count[ IntegerDigits[k, 2], 1], {k, 0, n}]; Array[f, 51, 0] (* Robert G. Wilson v, Jun 28 2010 *)

def a(n):  # formula version, n=10^10000 takes ~1 second
    if n == 0:
        return 1
    msb = 1 << (n.bit_length() - 1)
    return msb**2 + 3 * a(n-msb) # Stefan Pochmann, Mar 15 2023

def a(n):  # optimized, n=10^50000 takes ~1 second
    n += 1
    total = 0
    power3 = 1
    while n:
        log = n.bit_length() - 1
        total += power3 << (2*log)
        n -= 1 << log
        power3 *= 3
    return total # Stefan Pochmann, Mar 15 2023

With a different offset: a(1) = 1; a(n) = max { 3*a(k)+a(n-k) | 1 <= k <= n/2 }, for n>1.
a(2n+1) = 4*a(n) and a(2n) = 3*a(n-1) + a(n).
a(n) = (A147562(n+1) - 1)*3/4 + 1. - Omar E. Pol, Nov 08 2009
a(n) = A160410(n+1)/4. - Omar E. Pol, Nov 12 2009
Let r(x) = (1 + 4x + 3x^2), then (1 + 4x + 7x^2 + 16x^3 + ...) =
r(x)* r(x^2) * r(x^4) * r(x^8) * ... - Gary W. Adamson, Mar 26 2010
For asymptotics see the discussion in the comments in A006046. - N. J. A. Sloane, Mar 11 2021
a(n) = Sum_{k=0..floor(log_2(n+1))} 3^k * A360189(n,k). - Alois P. Heinz, Mar 06 2023
a(n) = msb^2 + 3*a(n-msb), where msb = A053644(n). - Stefan Pochmann, Mar 15 2023

Simpler definition (and new offset) from David Applegate, Jun 11 2009

Lower limit of sum in definition changed from 1 to 0 by Robert G. Wilson v, Jun 28 2010

A072272 Number of active cells in n-th stage of growth of two-dimensional cellular automaton defined by "Rule 614", based on the 5-celled von Neumann neighborhood.

Original entry on oeis.org

1, 5, 5, 17, 5, 25, 17, 61, 5, 25, 25, 85, 17, 85, 61, 217, 5, 25, 25, 85, 25, 125, 85, 305, 17, 85, 85, 289, 61, 305, 217, 773, 5, 25, 25, 85, 25, 125, 85, 305, 25, 125, 125, 425, 85, 425, 305, 1085, 17, 85, 85, 289, 85, 425, 289, 1037, 61, 305, 305, 1037, 217, 1085, 773, 2753

Offset: 0

Miklos Kristof, Jul 09 2002

Consider only the four nearest (N,S,E,W) neighbors of a cell together with the cell itself. In the next state, the state of a cell will change if an odd number of these five cells is ON. [Comment corrected by N. J. A. Sloane, Aug 25 2014]
Equivalently, a(n) is the number of ON cells at generation n of 2-D CA defined as follows: the neighborhood of a cell consists of the cell itself and the four adjacent E, W, N, S cells. A cell is ON iff an odd number of these cells was ON at the previous generation. - N. J. A. Sloane, Aug 20 2014. This is the odd-rule cellular automaton defined by OddRule 057 (see Ekhad-Sloane-Zeilberger "Odd-Rule Cellular Automata on the Square Grid" link).
This is the Run Length Transform of A007483. - N. J. A. Sloane, Aug 25 2014
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, Aug 25 2014
The partial sums are in A253908, in which the structure looks like an irregular stepped pyramid. - Omar E. Pol, Jan 29 2015
Rules 518, 550 and 582 also generate this sequence. - Robert Price, Mar 01 2016

			To illustrate a(0) = 1, a(1) = 5, a(2) = 5, a(3) = 17:
  ......................0
  .............0.......000
  .......0............0...0
  .0....000..0.0.0...00.0.00
  .......0............0...0
  .............0.......000
  ......................0
From _Omar E. Pol_, Jan 29 2015: (Start)
May be arranged into blocks of sizes A011782:
  1;
  5;
  5,17;
  5,25,17,61;
  5,25,25,85,17,85,61,217;
  5,25,25,85,25,125,85,305,17,85,85,289,61,305,217,773;
  5,25,25,85,25,125,85,305,25,125,125,425,85,425,305,1085,17,85,85,289,85,425,289,1037,
    61,305,305,1037,217,1085,773,2753;
So the right border gives A007483.
(End)
From _Omar E. Pol_, Mar 19 2015: (Start)
Also, the sequence can be written as an irregular tetrahedron T(s,r,k) as shown below:
     1;
  .....
     5;
  .....
     5;
    17;
  ...........
     5,   25;
    17;
    61;
  ......................
     5,   25,  25,   85;
    17,   85;
    61;
   217;
  ...........................................
     5,   25,  25,   85,  25, 125,  85,  305;
    17,   85,  85,  289;
    61,  305;
   217;
   773;
  ..................................................................................
     5,   25,  25,   85,  25, 125,  85,  305, 25, 125, 125, 425, 85, 425, 305, 1085;
    17,   85,  85,  289,  85, 425, 289, 1037;
    61,  305, 305, 1037;
   217, 1085;
   773;
  2753;
  ...
Apart from the initial 1, we have that T(s,r,k) = T(s+1,r,k).
It appears that the configuration of ON cells of T(s,r,k) is of the same kind as the configuration of ON cells of T(s+1,r,k).
(End)

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; pp. 170-179.

Alois P. Heinz, Table of n, a(n) for n = 0..8192
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 A072272.
N. H. Packard and S. Wolfram, Two-Dimensional Cellular Automata, Journal of Statistical Physics, 38 (1985), 901-946.
N. J. A. Sloane, Illustration of first 15 generations.
N. J. A. Sloane, Illustration of first 28 generations.
N. J. A. Sloane, Illustration for a(15)=217.
N. J. A. Sloane, Illustration for a(31)=773.
N. J. A. Sloane, Illustration for a(63)=2753.
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS.
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
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.
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton.
S. Wolfram, A New Kind of Science.
Index to 2D 5-Neighbor Cellular Automata
Index to Elementary Cellular Automata
Index entries for sequences related to cellular automata

Cf. A048883, A170878 (first differences), A253908 (partial sums).

See A253090 for 9-celled neighborhood version.

C:=f->subs({x=1,y=1},f);
# Find number of ON cells in CA for generations 0 thru M defined by rule
# that cell is ON iff number of ON cells in nbd at time n-1 was odd
# where nbd is defined by a polynomial or Laurent series f(x,y).
OddCA:=proc(f,M) global C; local n,a,i,f2,g,p;
f2:=simplify(expand(f)) mod 2;
a:=[]; p:=1; g:=f2;
for n from 0 to M do a:=[op(a),C(p)]; p:=expand(p*f2) mod 2; od:
lprint([seq(a[i],i=1..nops(a))]);
end;
f:=1+1/x+x+1/y+y;
OddCA(f,100);
# N. J. A. Sloane, Aug 20 2014

Map[Function[Apply[Plus,Flatten[ #1]]], CellularAutomaton[{ 614, {2,{{0,2,0},{2,1,2},{0,2,0}}},{1,1}},{{{1}},0},100]] (* N. J. A. Sloane, Apr 17 2010 *)
ArrayPlot /@ CellularAutomaton[{ 614, {2,{{0,2,0},{2,1,2},{0,2,0}}},{1,1}},{{{1}},0},6] (* N. J. A. Sloane, Aug 25 2014 *)

a(0)=1; thereafter a(2t)=a(t), a(4t+1)=5*a(t), a(4t+3)=3*a(2t+1)+2*a(t). - N. J. A. Sloane, Jan 26 2015

Extended and edited by John W. Layman, Jul 17 2002
Minor edits by N. J. A. Sloane, Jan 07 2010
More terms from N. J. A. Sloane, Apr 17 2010

A160410 Number of "ON" cells at n-th stage in simple 2-dimensional cellular automaton (see Comments for precise definition).

Original entry on oeis.org

0, 4, 16, 28, 64, 76, 112, 148, 256, 268, 304, 340, 448, 484, 592, 700, 1024, 1036, 1072, 1108, 1216, 1252, 1360, 1468, 1792, 1828, 1936, 2044, 2368, 2476, 2800, 3124, 4096, 4108, 4144, 4180, 4288, 4324, 4432, 4540, 4864, 4900, 5008, 5116, 5440, 5548, 5872, 6196

Offset: 0

Omar E. Pol, May 20 2009

On the infinite square grid, we consider cells to be the squares, and we start at round 0 with all cells in the OFF state, so a(0) = 0.
At round 1, we turn ON four cells, forming a square.
The rule for n > 1: A cell in turned ON iff exactly one of its four vertices is a corner vertex of the set of ON cells. So in each generation every exposed vertex turns on three new cells.
Therefore:
At Round 2, we turn ON twelve cells around the square.
At round 3, we turn ON twelve other cells. Three cells around of every corner of the square.
And so on.
For the first differences see the entry A161411.
Shows a fractal behavior similar to the toothpick sequence A139250.
A very similar sequence is A160414, which uses the same rule but with a(1) = 1, not 4.
When n=2^k then the polygon formed by ON cells is a square with side length 2^(k+1).
a(n) is also the area of the figure of A147562 after n generations if A147562 is drawn as overlapping squares. - Omar E. Pol, Nov 08 2009
From Omar E. Pol, Mar 28 2011: (Start)
Also, toothpick sequence starting with four toothpicks centered at (0,0) as a cross.
Rule: Each exposed endpoint of the toothpicks of the old generation must be touched by the endpoints of three toothpicks of new generation. (Note that these three toothpicks looks like a T-toothpick, see A160172.)
The sequence gives the number of toothpicks after n stages. A161411 gives the number of toothpicks added at the n-th stage.
(End)

			From _Omar E. Pol_, Sep 24 2015: (Start)
With the positive terms written as an irregular triangle in which the row lengths are the terms of A011782 the sequence begins:
    4;
   16;
   28,  64;
   76, 112, 148, 256;
  268, 304, 340, 448, 484, 592, 700, 1024;
  ...
Right border gives the elements of A000302 greater than 1.
This triangle T(n,k) shares with the triangle A256534 the terms of the column k, if k is a power of 2, for example, both triangles share the following terms: 4, 16, 28, 64, 76, 112, 256, 268, 304, 448, 1024, etc.
.
Illustration of initial terms, for n = 1..10:
.       _ _ _ _                         _ _ _ _
.      |  _ _  |                       |  _ _  |
.      | |  _|_|_ _ _ _ _ _ _ _ _ _ _ _|_|_  | |
.      | |_|  _ _     _ _     _ _     _ _  |_| |
.      |_ _| |  _|_ _|_  |   |  _|_ _|_  | |_ _|
.          | |_|  _ _  |_|   |_|  _ _  |_| |
.          |   | |  _|_|_ _ _ _|_|_  | |   |
.          |  _| |_|  _ _     _ _  |_| |_  |
.          | | |_ _| |  _|_ _|_  | |_ _| | |
.          | |_ _| | |_|  _ _  |_| | |_ _| |
.          |       |   | |   | |   |       |
.          |  _ _  |  _| |_ _| |_  |  _ _  |
.          | |  _|_| | |_ _ _ _| | |_|_  | |
.          | |_|  _| |_ _|   |_ _| |_  |_| |
.          |   | | |_ _ _ _ _ _ _ _| | |   |
.          |  _| |_ _| |_     _| |_ _| |_  |
.       _ _| | |_ _ _ _| |   | |_ _ _ _| | |_ _
.      |  _| |_ _|   |_ _|   |_ _|   |_ _| |_  |
.      | | |_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _| | |
.      | |_ _| |                       | |_ _| |
.      |_ _ _ _|                       |_ _ _ _|
.
After 10 generations there are 304 ON cells, so a(10) = 304.
(End)

Michael De Vlieger, Table of n, a(n) for n = 0..1000
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.],
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. 31.
Omar E. Pol, Illustration of initial terms (2009)
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Index entries for sequences related to cellular automata

Cf. A000079, A000302, A048883, A139250, A147562, A160118, A160412, A160414, A161411, A160717, A160720, A160727, A256530, A256534.

RasterGraphics[state_?MatrixQ,colors_Integer:2,opts___]:=
Graphics[Raster[Reverse[1-state/(colors -1)]],
AspectRatio ->(AspectRatio/.{opts}/.AspectRatio ->Automatic),
Frame ->True, FrameTicks ->None, GridLines ->None];
rule=1340761804646523638425234105559798690663900360577570370705802859623\
705267234688669629039040624964794287326910250673678735142700520276191850\
5902735959769690
Show[GraphicsArray[Map[RasterGraphics,CellularAutomaton[{rule, {2,
{{4,2,1}, {32,16,8}, {256,128,64}}}, {1,1}}, {{{1,1}, {1,1}}, 0}, 9,-10]]]];
ca=CellularAutomaton[{rule,{2,{{4,2,1},{32,16,8},{256,128,64}}},{1,
1}},{{{1,1},{1,1}},0},99,-100];
Table[Total[ca[[i]],2],{i,1,Length[ca]}]
(* John W. Layman, Sep 01 2009; Sep 02 2009 *)
a[n_] := 4*Sum[3^DigitCount[k, 2, 1], {k, 0, n-1}];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Nov 17 2017, after N. J. A. Sloane *)

A160410(n)=sum(i=0,n-1,3^norml2(binary(i)))<<2 \\ M. F. Hasler, Dec 04 2012

Equals 4*A130665. This provides an explicit formula for a(n). - N. J. A. Sloane, Jul 13 2009

a(2^k) = (2*(2^k))^2 for k>=0.

Edited by David Applegate and N. J. A. Sloane, Jul 13 2009

A117940 a(0)=1, thereafter a(3n) = a(3n+1)/3 = a(n), a(3n+2)=0.

Original entry on oeis.org

1, 3, 0, 3, 9, 0, 0, 0, 0, 3, 9, 0, 9, 27, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 9, 0, 9, 27, 0, 0, 0, 0, 9, 27, 0, 27, 81, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 9, 0, 9, 27, 0, 0, 0, 0, 9, 27, 0, 27, 81, 0, 0, 0, 0, 0, 0

Offset: 0

Paul Barry, Apr 05 2006

a(n) = a(3n)/a(0) = a(3n+1)/a(1). a(n) mod 2 = A039966(n). Row sums of A117939.

Observation: if this is written as a triangle (see example) then at least the first five row sums coincide with A002001. - Omar E. Pol, Nov 28 2011

			Contribution from Omar E. Pol, Nov 26 2011 (Start):
When written as a triangle this begins:
1,
3,0,
3,9,0,0,0,0,
3,9,0,9,27,0,0,0,0,0,0,0,0,0,0,0,0,0,
3,9,0,9,27,0,0,0,0,9,27,0,27,81,0,0,0,0,0,0,0,0,0,0,0,...
(End)

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.]
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

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.

G.f.: Product{k>=0, 1+3x^(3^k)}; a(n)=sum{k=0..n, sum{j=0..n, L(C(n,j)/3)*L(C(n-j,k)/3)}} where L(j/p) is the Legendre symbol of j and p.

A151666 Number of partitions of n into distinct powers of 4.

Original entry on oeis.org

1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

N. J. A. Sloane, May 30 2009

nonn

Reinhard Zumkeller, 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.]
Lukasz Merta, Composition inverses of the variations of the Baum-Sweet sequence, arXiv:1803.00292 [math.NT], 2018. See q(n) (with different offset) p. 9.
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

Cf. A039966, A151667, A000695, A269707.

a151666 n = fromEnum (n < 2 || m < 2 && a151666 n' == 1)
   where (n', m) = divMod n 4
-- Reinhard Zumkeller, Dec 03 2011

terms = 105;
kmax = Log[4, terms] // Ceiling;
CoefficientList[Product[1+x^(4^k), {k, 0, kmax}] + O[x]^(kmax terms), x][[1 ;; terms]] (* Jean-François Alcover, Jul 31 2018 *)

G.f.: Prod_{k >= 0 } (1+x^(4^k)). Exponents give A000695.

G.f. A(x) satisfies: A(x) = (1 + x) * A(x^4). - Ilya Gutkovskiy, Aug 12 2019

A160414 Number of "ON" cells at n-th stage in simple 2-dimensional cellular automaton (same as A160410, but a(1) = 1, not 4).

Original entry on oeis.org

0, 1, 9, 21, 49, 61, 97, 133, 225, 237, 273, 309, 417, 453, 561, 669, 961, 973, 1009, 1045, 1153, 1189, 1297, 1405, 1729, 1765, 1873, 1981, 2305, 2413, 2737, 3061, 3969, 3981, 4017, 4053, 4161, 4197, 4305, 4413, 4737, 4773, 4881, 4989, 5313, 5421, 5745

Offset: 0

Omar E. Pol, May 20 2009

The structure has a fractal behavior similar to the toothpick sequence A139250.
First differences: A161415, where there is an explicit formula for the n-th term.
For the illustration of a(24) = 1729 (the Hardy-Ramanujan number) see the Links section.

			From _Omar E. Pol_, Sep 24 2015: (Start)
With the positive terms written as an irregular triangle in which the row lengths are the terms of A011782 the sequence begins:
1;
9;
21,    49;
61,    97,  133,  225;
237,  273,  309,  417,  453, 561,  669,  961;
...
Right border gives A060867.
This triangle T(n,k) shares with the triangle A256530 the terms of the column k, if k is a power of 2, for example both triangles share the following terms: 1, 9, 21, 49, 61, 97, 225, 237, 273, 417, 961, etc.
.
Illustration of initial terms, for n = 1..10:
.       _ _ _ _                       _ _ _ _
.      |  _ _  |                     |  _ _  |
.      | |  _|_|_ _ _ _ _ _ _ _ _ _ _|_|_  | |
.      | |_|  _ _     _ _   _ _     _ _  |_| |
.      |_ _| |  _|_ _|_  | |  _|_ _|_  | |_ _|
.          | |_|  _ _  |_| |_|  _ _  |_| |
.          |   | |  _|_|_ _ _|_|_  | |   |
.          |  _| |_|  _ _   _ _  |_| |_  |
.          | | |_ _| |  _|_|_  | |_ _| | |
.          | |_ _| | |_|  _  |_| | |_ _| |
.          |  _ _  |  _| |_| |_  |  _ _  |
.          | |  _|_| | |_ _ _| | |_|_  | |
.          | |_|  _| |_ _| |_ _| |_  |_| |
.          |   | | |_ _ _ _ _ _ _| | |   |
.          |  _| |_ _| |_   _| |_ _| |_  |
.       _ _| | |_ _ _ _| | | |_ _ _ _| | |_ _
.      |  _| |_ _|   |_ _| |_ _|   |_ _| |_  |
.      | | |_ _ _ _ _ _ _ _ _ _ _ _ _ _ _| | |
.      | |_ _| |                     | |_ _| |
.      |_ _ _ _|                     |_ _ _ _|
.
After 10 generations there are 273 ON cells, so a(10) = 273.
(End)

Paolo Xausa, 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.]
Omar E. Pol, Illustration of initial terms
Omar E. Pol, Illustration of the structure after 24th stage (contains 1729 ON cells)
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Index entries for sequences related to cellular automata

Cf. A001235, A011541, A011782, A000225, A060867, A139250, A147562, A160117, A160118, A160410, A160412, A161415, A160720, A160727, A151725, A256530, A256534.

read("transforms") ; isA000079 := proc(n) if type(n,'even') then nops(numtheory[factorset](n)) = 1 ; else false ; fi ; end proc:
A048883 := proc(n) 3^wt(n) ; end proc:
A161415 := proc(n) if n = 1 then 1; elif isA000079(n) then 4*A048883(n-1)-2*n ; else 4*A048883(n-1) ; end if; end proc:
A160414 := proc(n) add( A161415(k),k=1..n) ; end proc: seq(A160414(n),n=0..90) ; # R. J. Mathar, Oct 16 2010

A160414list[nmax_]:=Accumulate[Table[If[n<2,n,4*3^DigitCount[n-1,2,1]-If[IntegerQ[Log2[n]],2n,0]],{n,0,nmax}]];A160414list[100] (* Paolo Xausa, Sep 01 2023, after R. J. Mathar *)

my(s=-1, t(n)=3^norml2(binary(n-1))-if(n==(1<Altug Alkan, Sep 25 2015

a(n) = 1 + 4*A219954(n), n >= 1. - M. F. Hasler, Dec 02 2012

a(2^k) = (2^(k+1) - 1)^2. - Omar E. Pol, Jan 05 2013

Edited by N. J. A. Sloane, Jun 15 2009 and Jul 13 2009

More terms from R. J. Mathar, Oct 16 2010

A151665 G.f.: Product_{k>=0} (1 + 3*x^(4^k)).

Original entry on oeis.org

1, 3, 0, 0, 3, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 9, 0, 0, 9, 27, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 9, 0, 0, 9, 27, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 27, 0, 0, 27, 81, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

N. J. A. Sloane, May 30 2009

nonn

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.]
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

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.

A151667 Number of partitions of n into distinct powers of 5.

Original entry on oeis.org

1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

N. J. A. Sloane, May 30 2009

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..15625
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.]
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

Cf. A039966, A151666, A033042.

m = 130; A[_] = 1;
Do[A[x_] = (1+x) A[x^5] + O[x]^m // Normal, {m}];
CoefficientList[A[x], x] (* Jean-François Alcover, Oct 19 2019 *)

G.f.: Prod_{k >= 0 } (1+x^(5^k)). Exponents give A033042.

G.f. A(x) satisfies: A(x) = (1 + x) * A(x^5). - Ilya Gutkovskiy, Aug 12 2019

cp's OEIS Frontend

A033042 Sums of distinct powers of 5.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Julia

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A039966 a(0) = 1; thereafter a(3n+2) = 0, a(3n) = a(3n+1) = a(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A130665 a(n) = Sum_{k=0..n} 3^wt(k), where wt() = A000120().

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Python

Python

Formula

Extensions

A072272 Number of active cells in n-th stage of growth of two-dimensional cellular automaton defined by "Rule 614", based on the 5-celled von Neumann neighborhood.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A160410 Number of "ON" cells at n-th stage in simple 2-dimensional cellular automaton (see Comments for precise definition).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A117940 a(0)=1, thereafter a(3n) = a(3n+1)/3 = a(n), a(3n+2)=0.

Views

Author

Keywords