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