|
| |
|
|
A160239
|
|
Number of "ON" cells in a 2-dimensional cellular automaton ("Fredkin's Replicator") evolving according to the rule that a cell is ON in a given generation if and only if there was an odd number of ON cells among the eight nearest neighbors in the preceding generation, starting with one ON cell.
|
|
33
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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, 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
|
|
|
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
|
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)
.
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
|
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
|
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
(PARI) A160239=[]; a(n)={if(n>#A160239, A160239=concat(A160239, vector(n-#A160239)), n||return(1); A160239[n]&&return(A160239[n])); A160239[n]=if(bittest(n, 0), if(bittest(n, 1), a(n-2)+2*a(n\2), a(n\4)*8), a(n\2))} \\ M. F. Hasler, May 10 2016
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Offset changed to 1 by Hrothgar, Jul 11 2014
|
|
|
STATUS
|
approved
|
| |
|
|
