A169708 -id:A169708 - cp's OEIS frontend

A160552 a(0)=0, a(1)=1; a(2^i+j) = 2*a(j) + a(j+1) for 0 <= j < 2^i.

0, 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 5, 11, 17, 15, 1, 3, 5, 7, 5, 11, 17, 15, 5, 11, 17, 19, 21, 39, 49, 31, 1, 3, 5, 7, 5, 11, 17, 15, 5, 11, 17, 19, 21, 39, 49, 31, 5, 11, 17, 19, 21, 39, 49, 35, 21, 39, 53, 59, 81, 127, 129, 63, 1, 3, 5, 7, 5, 11, 17, 15, 5, 11, 17, 19, 21, 39, 49, 31

Offset: 0

David Applegate, May 18 2009

nonn

This recurrence is patterned after the one for A152980, but without the special cases.
Sequence viewed as triangle:
  0,
  1,
  1, 3,
  1, 3, 5, 7,
  1, 3, 5, 7, 5, 11, 17, 15,
  1, 3, 5, 7, 5, 11, 17, 15, 5, 11, 17, 19, 21, 39, 49, 31.
The rows converge to A151548.
Also the sum of the terms in the k-th row (k >= 1) is 4^(k-1). Proof by induction. - N. J. A. Sloane, Jan 21 2010
If this sequence [1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 5, 11, 17, 15, ...] is convolved with [1, 2, 2, 2, 2, 2, 2, ...] we obtain A139250, the toothpick sequence. Example: A139250(5) = 15 = (1, 2, 2, 2, 2) * (3, 1, 3, 1, 1). - Gary W. Adamson, May 19 2009
Starting with 1 and convolved with [1, 2, 0, 0, 0, ...] = A151548. - Gary W. Adamson, Jun 04 2009
Refer to A162956 for the analogous triangle using N=3. - Gary W. Adamson, Jul 20 2009
It appears that the sums of two successive terms give the positive terms of A139251. - Omar E. Pol, Feb 18 2015

			a(2) = a(2^1+0) = 2*a(0) + a(1) = 1, a(3) = a(2^1+1) = 2*a(1) + a(2) = 3*a(2^i) = 2*a(0) + a(1) = 1.

N. J. A. Sloane, Table of n, a(n) for n = 0..16384
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 the recurrence a(2^i+j) = C*a(j) + D*a(j+1), a(0) = A, a(1) = B for following values of (A B C D) see: (0 1 1 1) A118977, (1 0 1 1) A151702, (1 1 1 1) A151570, (1 2 1 1) A151571, (0 1 1 2) A151572, (1 0 1 2) A151703, (1 1 1 2) A151573, (1 2 1 2) A151574, (0 1 2 1) A160552, (1 0 2 1) A151704, (1 1 2 1) A151568, (1 2 2 1) A151569, (0 1 2 2) A151705, (1 0 2 2) A151706, (1 1 2 2) A151707, (1 2 2 2) A151708.
Cf. A152980, A139250, A139251, A151548, A160570, A151568.
Cf. A162956, A170903.

S:=proc(n) option remember; local i,j; if n <= 1 then RETURN(n); fi; i:=floor(log(n)/log(2)); j:=n-2^i; 2*S(j)+S(j+1); end; # N. J. A. Sloane, May 18 2009
H := x*(1+2*x)/(1+x) + (4*x^2/(1+2*x))*(mul(1+x^(2^k-1)+2*x^(2^k),k=1..20)-1); series(H,x,120); # N. J. A. Sloane, May 23 2009

Nest[Join[#, 2 # + Append[Rest@#, 1]] &, {0}, 7] (* Ivan Neretin, Feb 09 2017 *)

G.f.: x*(1+2*x)/(1+x) + (4*x^2/(1+2*x))*(-1 + Product_{k>=1} (1 + x^(2^k-1) + 2*x^(2^k))). - N. J. A. Sloane, May 23 2009, based on Gary W. Adamson's comment above and the known g.f. for A139250.
It appears that a(n) = A169708(n)/4, n >= 1. - Omar E. Pol, Feb 15 2015
It appears that a(n) = A139251(n) - a(n-1), n >= 1. - Omar E. Pol, Feb 18 2015

A169707 Total number of ON cells at stage n of two-dimensional cellular automaton defined by "Rule 750" using the von Neumann neighborhood.

Original entry on oeis.org

1, 5, 9, 21, 25, 37, 57, 85, 89, 101, 121, 149, 169, 213, 281, 341, 345, 357, 377, 405, 425, 469, 537, 597, 617, 661, 729, 805, 889, 1045, 1241, 1365, 1369, 1381, 1401, 1429, 1449, 1493, 1561, 1621, 1641, 1685, 1753, 1829, 1913, 2069, 2265, 2389, 2409, 2453, 2521

Offset: 1

N. J. A. Sloane, Apr 17 2010

Square grid, 4 neighbors per cell (N, E, S, W cells), turn ON iff exactly 1 or 3 neighbors are ON; once ON, cells stay ON.
The terms agree with those of A246335 for n <= 11, although the configurations are different starting at n = 7. - N. J. A. Sloane, Sep 21 2014
Offset 1 is best for giving a formula for a(n), although the Maple and Mathematica programs index the states starting at state 0.
It appears that this shares infinitely many terms with both A162795 and A147562, see Formula section and Example section. - Omar E. Pol, Feb 19 2015

			Divides naturally into blocks of sizes 1,2,4,8,16,...:
1,
5, 9,
21, 25, 37, 57,
85, 89, 101, 121, 149, 169, 213, 281, <- terms 8 through 15
341, 345, 357, 377, 405, 425, 469, 537, 597, 617, 661, 729, 805, 889, 1045, 1241,
1365, 1369, 1381, 1401, 1429, 1449, 1493, 1561, 1621, 1641, 1685, 1753, 1829, 1913, 2069, 2265, 2389, 2409, 2453, 2521, ...
From _Omar E. Pol_, Feb 18 2015: (Start)
Also, written as an irregular triangle T(j,k), k>=1, in which the row lengths are the terms of A011782:
1;
5;
9,   21;
25,  37,   57,  85;
89,  101, 121, 149, 169, 213, 281, 341;
345, 357, 377, 405, 425, 469, 537, 597, 617, 661, 729, 805, 889, 1045, 1241, 1365;
The right border gives the positive terms of A002450.
It appears that T(j,k) = A162795(j,k) = A147562(j,k), if k is a power of 2, for example: it appears that the three mentioned triangles only share the elements from the columns 1, 2, 4, 8, 16, ...
(End)

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 928.

N. J. A. Sloane and Vincenzo Librandi, Table of n, a(n) for n = 1..513, computed from the definition, not using the conjectured formula. [The first 200 terms were found by _Vincenzo Librandi_]
David Applegate, The movie 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), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.], arXiv:1004.3036 [math.CO].
N. J. A. Sloane, Table of n, a(n) for n=1..8192 assuming the recurrence is correct. Note that these terms are merely conjectures.
N. J. A. Sloane, Illustration of first 24 generations
N. J. A. Sloane, Illustration of first 24 generations of the NW-NE-SE-SW version of this CA
N. J. A. Sloane, Illustration of generation 7 of the NW-NE-SE-SW version of this CA (containing a(7) = 57 ON cells)
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
Index entries for sequences related to cellular automata

Cf. A169708 (first differences), A147562, A147582, A169648, A169649, A169709, A169710, A246333, A246334, A246335, A246336, A253098 (partial sums).
Cf. also A162795, A150552, A160104, A170903, A048645, A187200.
See A253088 for the analogous CA using Rule 750 and a 9-celled neighborhood.

(Maple program that uses the actual definition of the automaton, rather than the (conjectured) formula, from N. J. A. Sloane, Feb 15 2015):
# Count terms in a polynomial:
C := f->`if`(type(f, `+`), nops(f), 1);
# Replace all nonzero coeffts by 1:
bool := proc(f) local ix, iy, f2, i, t1, t2, A;
f2:=expand(f);
if whattype(f) = `+` then
t1:=nops(f2); A:=0;
for i from 1 to t1 do t2:=op(i, f2); ix:=degree(t2, x); iy:=degree(t2, y);
A:=A+x^ix*y^iy; od: A;
else ix:=degree(f2, x); iy:=degree(f2, y); x^ix*y^iy;
fi;
end;
# a loop that produces M steps of A169707 and A169708:
M:=20;
F:=x*y+x/y+1/x*y+1/x/y mod 2;
GG[0]:=1;
for n from 1 to M do dd[n]:=expand(F*GG[n-1]) mod 2;
GG[n]:=bool(GG[n-1]+dd[n]);
lprint(n,C(GG[n]), C(GG[n]-GG[n-1])); od:

Map[Function[Apply[Plus,Flatten[ #1]]], CellularAutomaton[{ 750, {2,{{0,2,0},{2,1,2},{0,2,0}}},{1,1}},{{{1}},0},100]]
ArrayPlot /@ CellularAutomaton[{750, {2, {{0, 2, 0}, {2, 1, 2}, {0, 2, 0}}}, {1, 1}}, {{{1}}, 0}, 23]
(* The next two lines deal with the equivalent CA based on neighbors NW, NE, SE, SW. This is to facilitate the comparison with A246333 and A246335 *)
Map[Function[Apply[Plus, Flatten[ #1]]], CellularAutomaton[{ 750, {2, {{2, 0, 2}, {0, 1, 0}, {2, 0, 2}}}, {1, 1}}, {{{1}}, 0}, 100]]
ArrayPlot /@ CellularAutomaton[{750, {2, {{2, 0, 2}, {0, 1, 0}, {2, 0, 2}}}, {1, 1}}, {{{1}}, 0}, 23]

a(2^k + i) = (4^(k+1)-1)/3 + 4*A246336(i), for k >= 0, 0 <= i < 2^k. For example, if n = 15 = 2^3 + 7, so k=3, i=7, we have a(15) = (4^4-1)/3 + 4*A246336(7) = 85 + 4*49 = 281.
a(n) = 1 + 2*(A139250(n) - A160552(n)) = A160164(n) - A170903(n) = A187220(n) + 2*(A160552(n-1)). - Omar E. Pol, Feb 18 2015
It appears that a(n) = A162795(n) = A147562(n), if n is a member of A048645, otherwise a(n) > A162795(n) > A147562(n). - Omar E. Pol, Feb 19 2015
It appears that a(n) = 1 + 4*A255747(n-1). - Omar E. Pol, Mar 05 2015
It appears that a(n) = 1 + 4*(A139250(n-1) - (a(n-1) - 1)/4), n > 1. - Omar E. Pol, Jul 24 2015
It appears that a(2n) = 1 + 4*A162795(n). - Omar E. Pol, Jul 04 2017

Edited (added formula, illustration, etc.) by N. J. A. Sloane, Aug 30 2014

Offset changed to 1 by N. J. A. Sloane, Feb 09 2015

A162793 Number of toothpicks added to the toothpick structure A139250 at the n-th odd round.

Original entry on oeis.org

1, 4, 4, 12, 4, 12, 16, 32, 4, 12, 16, 32, 16, 36, 60, 80, 4, 12, 16, 32, 16, 36, 60, 80, 16, 36, 60, 84, 60, 112, 208, 192, 4, 12, 16, 32, 16, 36, 60, 80, 16, 36, 60, 84, 60, 112, 208, 192, 16, 36, 60, 84, 60, 112, 208, 196, 60, 112, 208, 224, 212, 364, 672, 448, 4, 12, 16, 32, 16

Offset: 1

Omar E. Pol, Jul 14 2009

Bisection of A139251.
Note that these toothpicks are parallel to the initial toothpick in the structure.
First differences of A162795. - Omar E. Pol, Feb 23 2015

			From _Omar E. Pol_, Feb 23 2015: (Start)
Written as an irregular triangle in which the row lengths are the terms of A011782, the sequence begins:
1;
4;
4,12;
4,12,16,32;
4,12,16,32,16,36,60,80;
4,12,16,32,16,36,60,80,16,36,60,84,60,112,208,192;
4,12,16,32,16,36,60,80,16,36,60,84,60,112,208,192,16,36,60,84,60,112,208,196,60,112,208,224,212,364,672,448;
...
It appears that right border gives the positive terms of A001787.
It appears that row sums give A000302.
(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
Index entries for sequences related to cellular automata

Cf. A000302, A001787, A139250, A139251, A147582, A159791, A159792, A162794, A162795, A162796, A162797, A169708.

More terms from N. J. A. Sloane, Dec 28 2009

A169709 Total number of ON cells at stage n of two-dimensional cellular automaton defined by "Rule 1006".

Original entry on oeis.org

1, 5, 9, 21, 29, 41, 61, 89, 101, 113, 133, 161, 189, 233, 309, 377, 397, 409, 429, 457, 485, 529, 605, 673, 709, 753, 821, 905, 1005, 1169, 1413, 1569, 1605, 1617, 1637, 1665, 1693, 1737, 1813, 1881, 1917, 1961, 2029, 2113, 2213, 2377, 2621, 2777, 2829, 2873, 2941

Offset: 0

N. J. A. Sloane, Apr 17 2010

nonn

Square grid, 4 neighbors per cell, turn ON iff exactly 1, 3 or 4 neighbors are ON; once ON, cells stay ON.

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 928.

David Applegate, The movie version
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Index entries for sequences related to cellular automata

Cf. A139250, A151725, A147562, A147582, A169648, A169649, A169707, A169708, A169710.

Map[Function[Apply[Plus,Flatten[ #1]]], CellularAutomaton[{ 1006, {2,{{0,2,0},{2,1,2},{0,2,0}}},{1,1}},{{{1}},0},100]]

A256261 First differences of A256260.

Original entry on oeis.org

1, 4, 4, 12, 4, 12, 20, 28, 4, 12, 20, 28, 20, 44, 68, 60, 4, 12, 20, 28, 20, 44, 68, 60, 20, 44, 68, 92, 116, 140, 164, 124, 4, 12, 20, 28, 20, 44, 68, 60, 20, 44, 68, 92, 116, 140, 164, 124, 20, 44, 68, 92, 116, 140, 164, 188, 212, 236, 260, 284, 308, 332, 356, 252, 4, 12, 20, 28, 20, 44, 68, 60, 20, 44, 68, 92, 116, 140

Offset: 0

Omar E. Pol, Mar 30 2015

First 27 terms agree with A169708. Both sequences share infinitely many terms.

			Written as an irregular triangle in which the row lengths are the terms of A011782, the sequence begins:
1;
4;
4,12;
4,12,20,28;
4,12,20,28,20,44,68,60;
4,12,20,28,20,44,68,60,20,44,68,92,116,140,164,124;
4,12,20,28,20,44,68,60,20,44,68,92,116,140,164,124,20,44,68,92,116,140,164,188,212,236,260,284,308,332,356,252;
...
It appears that the row sums give A000302.
It appears that the right border gives A173033.

Cf. A000302, A011782, A139251, A147582, A169708, A173033, A256258, A256251, A256260, A256263, A256264, A256265.

a(n) = 4*A256263(n), n >= 1.

A256251 First differences of A256250.

Original entry on oeis.org

1, 4, 4, 12, 4, 12, 20, 28, 4, 12, 20, 28, 36, 44, 52, 60, 4, 12, 20, 28, 36, 44, 52, 60, 68, 76, 84, 92, 100, 108, 116, 124, 4, 12, 20, 28, 36, 44, 52, 60, 68, 76, 84, 92, 100, 108, 116, 124, 132, 140, 148, 156, 164, 172, 180, 188, 196, 204, 212, 220, 228, 236, 244, 252, 4, 12, 20, 28, 36, 44, 52, 60, 68, 76, 84, 92, 100

Offset: 0

Omar E. Pol, Mar 20 2015

Number of cells turned ON at n-th stage in the structure of A256250.

Apart from the initial 1, four times A006257 (Josephus problem).

			Written as an irregular triangle in which the row lengths are the terms of A011782, the sequence begins:
1;
4;
4,12;
4,12,20,28;
4,12,20,28,36,44,52,60;
4,12,20,28,36,44,52,60,68,76,84,92,100,108,116,124;
4,12,20,28,36,44,52,60,68,76,84,92,100,108,116,124,132,140,148,156,164,172,180,188,196,204,212,220,228,236,244,252;
...
Row sums give A000302.
Right border gives A173033.

Danny Rorabaugh, Table of n, a(n) for n = 0..10000
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Index entries for sequences related to cellular automata
Index entries for sequences related to the Josephus Problem

Cf. A000302, A006257, A011782, A028399, A139251, A147582, A162793, A169708, A256239.

a(n) = if(n, 8*(n - 2^logint(n,2)) + 4, 1)

[1] + [8*(n - 2^floor(log(n,base=2))) + 4 for n in range(1,77)] # Danny Rorabaugh, Apr 20 2015

a(0) = 1. For n >= 1; a(n) = 4*A006257(n).

For n>0, a(n) = 8*(n - 2^floor(log_2(n))) + 4 (by the formula of Gregory Pat Scandalis in A006257). - Danny Rorabaugh, Apr 20 2015

A255045 a(n) = (1 + A160552(n))/2.

Original entry on oeis.org

1, 1, 2, 1, 2, 3, 4, 1, 2, 3, 4, 3, 6, 9, 8, 1, 2, 3, 4, 3, 6, 9, 8, 3, 6, 9, 10, 11, 20, 25, 16, 1, 2, 3, 4, 3, 6, 9, 8, 3, 6, 9, 10, 11, 20, 25, 16, 3, 6, 9, 10, 11, 20, 25, 18, 11, 20, 27, 30, 41, 64, 65, 32, 1, 2, 3, 4, 3, 6, 9, 8, 3, 6, 9, 10, 11, 20, 25, 16, 3, 6, 9, 10, 11, 20, 25, 18, 11, 20, 27, 30, 41, 64, 65, 32, 3, 6, 9, 10, 11, 20, 25, 18

Offset: 1

Omar E. Pol, Feb 13 2015

Triangle of numbers related to cellular automata.

It appears that this is also a triangle read by rows in which row n lists the first 2^(n-1) terms of A255046, with n >= 1.

			Written as an irregular triangle in which the length of row j is 2^j, j >= 0, the sequence begins:
1;
1,2;
1,2,3,4;
1,2,3,4,3,6,9,8;
1,2,3,4,3,6,9,8,3,6,9,10,11,20,25,16;
1,2,3,4,3,6,9,8,3,6,9,10,11,20,25,16,3,6,9,10,11,20,25,18,11,20,27,30,41,64,65,32;
...
It appears that the right border gives A000079.
It appears that the row sums give A007582.
It appears that rows converge to A255046.

Index entries for sequences related to cellular automata

Cf. A000079, A007582, A139251, A151548, A160552, A169708, A255046, A255049.

A255049 a(n) = 2*A160552(n).

Original entry on oeis.org

0, 2, 2, 6, 2, 6, 10, 14, 2, 6, 10, 14, 10, 22, 34, 30, 2, 6, 10, 14, 10, 22, 34, 30, 10, 22, 34, 38, 42, 78, 98, 62, 2, 6, 10, 14, 10, 22, 34, 30, 10, 22, 34, 38, 42, 78, 98, 62, 10, 22, 34, 38, 42, 78, 98, 70, 42, 78, 106, 118, 162, 254, 258, 126, 2, 6, 10, 14, 10

Offset: 0

Omar E. Pol, Feb 13 2015

			Written as an irregular triangle in which row lengths are the terms of A011782 the sequence begins:
0;
2;
2,6;
2,6,10,14;
2,6,10,14,10,22,34,30;
2,6,10,14,10,22,34,30,10,22,34,38,42,78,98,62;
2,6,10,14,10,22,34,30,10,22,34,38,42,78,98,62,10,22,34,38,42,78,98,70,42,78,106,118,162,254,258,126;
It appears that row sums give 0 together with A004171, (see also A081294).
It appears that right border gives the nonnegative terms of A000918, (see also A095121).

Cf. A000918, A004171, A081294, A095121, A139250, A160164, A160552, A169707, A169708, A187220.

It appears that a(n) = A169708(n)/2, n >= 1.

Edited by Omar E. Pol, Feb 18 2015

A256139 First differences of A256138.

Original entry on oeis.org

1, 4, 4, 12, 4, 12, 20, 28, 4, 12, 20, 36, 36, 28, 52, 60, 4, 12, 20, 36, 36, 36, 68, 100, 68, 28, 52, 92, 108, 76, 124, 124, 4, 12, 20, 36, 36, 36, 68, 100, 68, 36, 68, 116, 148, 132, 164, 228, 132, 28, 52, 92, 108, 108, 172, 268, 236, 108, 124, 220, 276, 196, 276, 252

Offset: 0

Omar E. Pol, Mar 20 2015

Number of cells turned ON at n-th stage in the structure of A256138.

First differs from A169708 at a(11).

			Written as an irregular triangle in which the row lengths are the terms of A011782 the sequence begins:
1;
4;
4,12;
4,12,20,28;
4,12,20,36,36,28,52,60;
4,12,20,36,36,36,68,100,68,28,52,92,108,76,124,124;
4,12,20,36,36,36,68,100,68,36,68,116,148,132,164,228,132,28,52,92,108,108,172,268,236,108,124,220,276,196,276,252;
...
It appears that the right border gives A173033.

Cf. A028399, A011782, A151723, A151724, A160721, A169708, A170898, A170905, A173033, A256138.

a(n) = 2*A151724(n+1)/3, n >= 1.

cp's OEIS Frontend

A160552 a(0)=0, a(1)=1; a(2^i+j) = 2*a(j) + a(j+1) for 0 <= j < 2^i.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A169707 Total number of ON cells at stage n of two-dimensional cellular automaton defined by "Rule 750" using the von Neumann neighborhood.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A162793 Number of toothpicks added to the toothpick structure A139250 at the n-th odd round.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A169709 Total number of ON cells at stage n of two-dimensional cellular automaton defined by "Rule 1006".

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

A256261 First differences of A256260.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A256251 First differences of A256250.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Sage

Formula

A255045 a(n) = (1 + A160552(n))/2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A255049 a(n) = 2*A160552(n).

Views

Author

Keywords

Examples