login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A244643 Number of cells with state 1 at n-th stage in some 2D reversible second order cellular automata (see comments for precise definition). 2
0, 1, 4, 5, 16, 9, 20, 21, 64, 25, 36, 29, 80, 41, 84, 85, 256, 89, 100, 61, 144, 65, 116, 109, 320, 121, 164, 125, 336, 169, 340, 341, 1024, 345, 356, 189, 400, 161, 244, 205, 576, 209, 260, 181, 464, 225, 436, 429, 1280, 441, 484, 285, 656, 289, 500, 461, 1344, 505, 676, 509, 1360, 681, 1364, 1365, 4096, 1369 (list; graph; refs; listen; history; text; internal format)
OFFSET

-1,3

COMMENTS

Consider cellular automata with two states defined in A244642 and second order cellular automata with four states generated from them. If we start with a single cell with state 1 and all the others 0, then number cells with state 1 in subsequent steps will be the terms in the sequence a(n). Number of cells with state 2 is a(n-1), where a(-1) = 0.

Equals row 4 in the array shown in A178568.

LINKS

Alexander Yu. Vlasov, Table of n, a(n) for n = -1..10000

Alexander Yu. Vlasov, Snakes and fractals

Alexander Yu. Vlasov, Nine initial patterns

Alexander Yu. Vlasov, On number of nonzero cells in some two-dimensional reversible second-order cellular automata, arXiv:1407.6553 [math.CO], 2014.

FORMULA

a(-1) = 0, a(0) = 1, a(2^k + j) = 4*a(j) + a(2^k - j - 2).

a(n-1)+a(n) = A244642(n).

a(2n+1) = 4a(n), a(2n+2) = a(n+1) + a(n).

EXAMPLE

For n=4, a(4) = 16 and a(n-1) = a(3) = 5.

....1

...121

..1.1.1

.1212121

..1.1.1

...121

....1

MATHEMATICA

msb[1]=1; msb[n_] := 2 msb[Quotient[n, 2]];

a[-1] = 0; a[0] = 1; a[n_] := 4 a[n-msb[n]] + a[2 msb[n]-n-2];

Table[a[n], {n, -1, 64}] (* recursion *)

Table[PolynomialMod[Fibonacci[n, f]/.f->(x+1/x+y+1/y), 2], {n, 0, 24}]/.{x->1, y->1}  (* calculation using GF(2) polynomial representation of CA *)

PROG

(AXIOM)

msb n == if n=1 then 1 else 2*msb(quo(n, 2))

a n == if n<1 then n+1 else 4*a(n-msb(n))+a(2*msb(n)-n-2)

[a(n) for n in -1..64]

CROSSREFS

Cf. A102376, A147562, A244642, A237711, A168081, A178590, A178568.

Sequence in context: A289742 A249113 A166590 * A085768 A166304 A078713

Adjacent sequences:  A244640 A244641 A244642 * A244644 A244645 A244646

KEYWORD

nonn

AUTHOR

Alexander Yu. Vlasov, Jul 03 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 15 13:27 EDT 2018. Contains 316236 sequences. (Running on oeis4.)