A247649 Number of terms in expansion of f^n mod 2, where f = 1/x^2 + 1/x + 1 + x + x^2 mod 2.

1, 5, 5, 7, 5, 17, 7, 19, 5, 25, 17, 19, 7, 31, 19, 25, 5, 25, 25, 35, 17, 61, 19, 71, 7, 35, 31, 41, 19, 71, 25, 77, 5, 25, 25, 35, 25, 85, 35, 95, 17, 85, 61, 71, 19, 91, 71, 77, 7, 35, 35, 49, 31, 107, 41, 121, 19, 95, 71, 85, 25, 113, 77, 103

Offset

0,2

Comments

This is the number of cells that are ON after n generations in a one-dimensional cellular automaton defined by the odd-neighbor rule where the neighborhood consists of 5 contiguous cells.

a(n) is also the number of odd entries in row n of A035343. - Leon Rische, Feb 02 2023

Links

Chai Wah Wu, Table of n, a(n) for n = 0..10000

N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.

Index entries for sequences related to cellular automata

Formula

The values of a(n) for n in A247647 (or A247648) determine all the values, as follows. Parse the binary expansion of n into terms from A247647 separated by at least two zeros: m_1 0...0 m_2 0...0 m_3 ... m_r 0...0. Ignore any number (one or more) of trailing zeros. Then a(n) = a(m_1)*a(m_2)*...*a(m_r). For example, n = 37_10 = 100101_2 is parsed into 1.00.101, and so a(37) = a(1)*a(5) = 5*17 = 85. This is a generalization of the Run Length Transform.

Example

The first few generations are:
..........X..........
........XXXXX........
......X.X.X.X.X......
....XX..X.X.X..XX.... (f^3)
..X...X...X...X...X..
XXXX.XXX.XXX.XXX.XXXX
...
f^3 mod 2 = x^6 + x^5 + x^2 + 1/x^2 + 1/x^5 + 1/x^6 + 1 has 7 terms, so a(3) = 7.
From Omar E. Pol, Mar 02 2015: (Start)
Also, written as an irregular triangle in which the row lengths are the terms of A011782, the sequence begins:
  1;
  5;
  5, 7;
  5,17, 7,19;
  5,25,17,19, 7,31,19,25;
  5,25,25,35,17,61,19,71, 7,35,31,41,19,71,25,77;
  5,25,25,35,25,85,35,95,17,85,61,71,19,91,71,77,7,35,35,49,31,107,41,121,19, ...
(End)
It follows from the Generalized Run Length Transform result mentioned in the comments that in each row the first quarter of the terms (and no more) are equal to 5 times the beginning of the sequence itself. It cannot be said that the rows converge (in any meaningful sense) to five times the sequence. - N. J. A. Sloane, Mar 03 2015

Prog

(Python)
import sympy
from functools import reduce
from operator import mul
x = sympy.symbols('x')
f = 1/x**2+1/x+1+x+x**2
A247649_list, g = [1], 1
for n in range(1, 1001):
    s = [int(d, 2) for d in bin(n)[2:].split('00') if d != '']
    g = (g*f).expand(modulus=2)
    if len(s) == 1:
        A247649_list.append(g.subs(x, 1))
    else:
        A247649_list.append(reduce(mul, (A247649_list[d] for d in s)))
# Chai Wah Wu, Sep 25 2014

Crossrefs

Cf. A071053, A247647, A247648, A253085, A255490.

Partial sums are in A255654.

Sequence in context: A195380 A139261 A352442 * A252655 A021646 A231589

Adjacent sequences: A247646 A247647 A247648 * A247650 A247651 A247652

Keyword

nonn

Author

N. J. A. Sloane, Sep 25 2014

Status

approved