OFFSET

0,2

COMMENTS

This is the odd-rule cellular automaton defined by OddRule 757 (see Ekhad-Sloane-Zeilberger "Odd-Rule Cellular Automata on the Square Grid" link). - N. J. A. Sloane, Feb 25 2015

The partial sums are in A245542, in which the structure also looks like an irregular stepped pyramid. - Omar E. Pol, Jan 29 2015

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..10000

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.

Charles R Greathouse IV, Compact illustration of generations 0..17

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

N. J. A. Sloane, Enlarged illustration of first 16 generations (pdf).

N. J. A. Sloane, Illustration for a(15) = 416 (png).

N. J. A. Sloane, Illustration for a(15) = 416 (pdf).

N. J. A. Sloane, Illustration for a(31) = 1728.

N. J. A. Sloane, Illustration for a(63) = 6784.

N. J. A. Sloane, Illustration for a(127) = 27392 (tiff).

N. J. A. Sloane, Illustration for a(127) = 27392 (png).

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.

FORMULA

a(0) = 1; a(2t)=a(t), a(4t+1)=8*a(t), a(4t+3)=2*a(2t+1)+8*a(t) for t >= 0. (Conjectured by Hrothgar, Jul 11 2014; proved by N. J. A. Sloane, Oct 04 2014.)

For n >= 2, a(n) = 8^r * Product_{lengths i of runs of 1 in binary expansion of n} R(i), where r is the number of runs of 1 in the binary expansion of n and R(i) = A083424(i-1) = (5*4^(i-1)+(-2)^(i-1))/6. Note that row i of the table in A245562 lists the lengths of runs of 1 in binary expansion of i. Example: n=7 = 111 in binary, so r=1, i=3, R(3) = A083424(2) = 14, and so a(7) = 8^1*14 = 112. That is, this sequence is the Run Length Transform of A246030. - N. J. A. Sloane, Oct 04 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

EXAMPLE

From Omar E. Pol, Jul 22 2014 (Start):

Written as an irregular triangle in which row lengths is A011782 the sequence begins:

1;

8;

8, 24;

8, 64, 24, 112;

8, 64, 64, 192, 24, 192, 112, 416;

8, 64, 64, 192, 64, 512, 192, 896, 24, 192, 192, 576, 112, 896, 416, 1728;

8, 64, 64, 192, 64, 512, 192, 896, 64, 512, 512, 1536, 192, 1536, 896, 3328, 24, 192, 192, 576, 192, 1536, 576, 2688, 112, 896, 896, 2688, 416, 3328, 1728, 6784;

(End)

Right border gives A246030. - Omar E. Pol, Jan 29 2015 [This is simply a restatement of the theorem that this sequence is the Run Length Transform of A246030. - N. J. A. Sloane, Jan 29 2015]

.

From Omar E. Pol, Mar 18 2015 (Start):

Also, the sequence can be written as an irregular tetrahedron as shown below:

1;

..

8;

..

8;

24;

.........

8, 64;

24;

112;

...................

8, 64, 64, 192;

24, 192;

112;

416;

.....................................

8, 64, 64, 192, 64, 512,192, 896;

24, 192, 192, 576;

112, 896;

416;

1728;

.......................................................................

8, 64, 64, 192, 64, 512,192, 896,64,512,512,1536,192,1536,896,3328;

24, 192, 192, 576,192,1536,576,2688;

112, 896, 896,2688;

416,3328;

1728;

6784;

...

Apart from the initial 1, we have that T(s,r,k) = T(s+1,r,k). On the other hand, it appears that the configuration of ON cells of T(s,r,k) is also the central part of the configuration of ON cells of T(s+1,r+1,k).

(End)

MAPLE

# From N. J. A. Sloane, Jan 19 2015:

f:=proc(n) option remember;

if n=0 then RETURN(1);

elif n mod 2 = 0 then RETURN(f(n/2))

elif n mod 4 = 1 then RETURN(8*f((n-1)/4))

else RETURN(f(n-2)+2*f((n-1)/2)); fi;

end;

[seq(f(n), n=0..255)];

MATHEMATICA

A160239[n_] :=

CellularAutomaton[{52428, {2, {{2, 2, 2}, {2, 1, 2}, {2, 2, 2}}}, {1, 1}}, {{{1}}, 0}, {{n}}][[1]] // Total@*Total (* Charles R Greathouse IV, Aug 21 2014 *)

ArrayPlot /@ CellularAutomaton[{52428, {2, {{2, 2, 2}, {2, 1, 2}, {2, 2, 2}}}, {1, 1}}, {{{1}}, 0}, 30] (* Charles R Greathouse IV, Aug 21 2014 *)

PROG

(Haskell)

import Data.List (transpose)

a160239 n = a160239_list !! n

a160239_list = 1 : (concat $

transpose [a8, hs, zipWith (+) (map (* 2) hs) a8, tail a160239_list])

where a8 = map (* 8) a160239_list;

hs = h a160239_list; h (_:x:xs) = x : h xs

-- Reinhard Zumkeller, Feb 13 2015

CROSSREFS

KEYWORD

nonn,nice

AUTHOR

John W. Layman, May 05 2009

EXTENSIONS

Offset changed to 1 by Hrothgar, Jul 11 2014

Offset reverted to 0 by N. J. A. Sloane, Jan 19 2015

STATUS

approved