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

Author

N. J. A. Sloane, Sep 25 2014

Keywords

• nonn

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

Examples

			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
		

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

Crossrefs

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

Partial sums are in A255654.

Programs

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

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.