|
|
A071053
|
|
Number of ON cells at n-th generation of 1-D CA defined by Rule 150, starting with a single ON cell at generation 0.
|
|
44
|
|
|
1, 3, 3, 5, 3, 9, 5, 11, 3, 9, 9, 15, 5, 15, 11, 21, 3, 9, 9, 15, 9, 27, 15, 33, 5, 15, 15, 25, 11, 33, 21, 43, 3, 9, 9, 15, 9, 27, 15, 33, 9, 27, 27, 45, 15, 45, 33, 63, 5, 15, 15, 25, 15, 45, 25, 55, 11, 33, 33, 55, 21, 63, 43, 85, 3, 9, 9, 15, 9, 27, 15, 33, 9, 27, 27
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Number of 1's in n-th row of triangle in A071036.
Number of odd coefficients in (x^2+x+1)^n. - Benoit Cloitre, Sep 05 2003. This result was given in Wolfram (1983). - N. J. A. Sloane, Feb 17 2015
This is also the odd-rule cellular automaton defined by OddRule 007 (see Ekhad-Sloane-Zeilberger "Odd-Rule Cellular Automata on the Square Grid" link). - N. J. A. Sloane, Feb 25 2015
This is the Run Length Transform of S(n) = Jacobsthal(n+2) (cf. A001045). 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, Sep 05 2014
|
|
REFERENCES
|
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; Chapter 3.
|
|
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(2*n) = a(n); a(2*n+1) = a(n) + 2*a(floor(n/2)). - Peter J. Taylor, Mar 26 2020
|
|
EXAMPLE
|
May be arranged into blocks of sizes 1,1,2,4,8,16,...:
1,
3,
3, 5,
3, 9, 5, 11,
3, 9, 9, 15, 5, 15, 11, 21,
3, 9, 9, 15, 9, 27, 15, 33, 5, 15, 15, 25, 11, 33, 21, 43,
3, 9, 9, 15, 9, 27, 15, 33, 9, 27, 27, 45, 15, 45, 33, 63, 5, 15, 15, 25, 15, 45, 25, 55, 11, 33, 33, 55, 21, 63, 43, 85,
3, 9, 9, 15, 9, 27, 15, 33, 9, 27, 27, ...
.
Apart from the initial 1, the sequence can be written also as an irregular tetrahedron T(s,r,k) = A001045(r+2) * a(k), s>=1, 1<=r<=s, 0<=k<=(A011782(s-r)-1) as shown below (see also Joerg Arndt's equivalent program):
3;
..
3;
5;
.......
3, 9;
5;
11;
...............
3, 9, 9, 15;
5, 15;
11;
21;
...............................
3, 9, 9, 15, 9, 27, 15, 33;
5, 15, 15, 25;
11, 33;
21;
43;
..............................................................
3, 9, 9, 15, 9, 27, 15, 33, 9, 27, 27, 45, 15, 45, 33, 63;
5, 15, 15, 25, 15, 45, 25, 55;
11, 33, 33, 55;
21, 63;
43;
85;
...
Note that every row r is equal to A001045(r+2) times the beginning of the sequence itself, thus in 3D every column contains the same number.
(End)
|
|
MATHEMATICA
|
a[n_] := Total[CoefficientList[(x^2 + x + 1)^n, x, Modulus -> 2]];
|
|
PROG
|
(PARI)
b(n) = { (2^n - (-1)^n) / 3; } \\ A001045
a(n)=
{
if ( n==0, return(1) );
\\ Use a( 2^k * t ) = a(t)
n \= 2^valuation(n, 2);
if ( n==1, return(3) ); \\ Use a(2^k) == 3
\\ now n is odd
my ( v1 = valuation(n+1, 2) );
\\ Use a( 2^k - 1 ) = A001045( 2 + k ):
if ( n == 2^v1 - 1 , return( b( v1 + 2 ) ) );
my( k2 = 1, k = 0 );
while ( k2 < n, k2 <<= 1; k+=1 );
if ( k2 > n, k2 >>= 1; k-=1 );
my( t = n - k2 );
\\ here n == 2^k + 1 where k maximal
\\ Use the following:
\\ a( 2^k + t ) = 3 * a(t) if t <= 2^(k-1)
\\ a( 2^k + 2^(k-1) + t ) = 5 * a(t) if t <= 2^(k-2)
\\ a( 2^k + 2^(k-1) + 2^(k-2) + t ) = 11* a(t) if t <= 2^(k-3)
\\ ... etc. ...
\\ a( 2^k + ... + 2^(k-s) + t ) = A001045(s+2) * a(t) if t <= 2^((k-1)-s)
my ( s=1 );
while ( 1 ,
k2 >>= 1;
if ( t <= k2 , return( b(s+2) * a(t) ) );
t -= k2;
s += 1;
);
}
\\ Joerg Arndt, Mar 15 2015, from SeqFan Mailing List, Mar 09 2015
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|