A327982 Partial sums of A051023, the middle column of rule-30 1-D cellular automaton, when started from a lone 1 cell.

1, 2, 2, 3, 4, 5, 5, 5, 6, 7, 7, 7, 7, 8, 8, 9, 10, 10, 10, 11, 11, 11, 12, 13, 14, 14, 15, 15, 16, 17, 18, 18, 18, 19, 20, 21, 21, 22, 22, 23, 23, 24, 25, 25, 25, 25, 25, 26, 27, 27, 27, 28, 28, 29, 29, 30, 31, 31, 32, 32, 33, 33, 34, 35, 36, 37, 38, 39, 39, 39, 39, 39, 40, 41, 42, 43, 43, 43, 43, 44, 44, 45, 45, 46

Offset: 0

Author

Antti Karttunen, Oct 03 2019

Keywords

• nonn

Comments

Lexicographically earliest monotonic left inverse of A327984.

Proving (or disproving) that Lim_{n->inf} a(n)/n = 1/2 would solve the Problem 2: "Does each color of cell occur on average equally often in the center column?" of Stephen Wolfram's 2019 prize announcement.

Examples

			The evolution of one-dimensional cellular automaton rule 30 proceeds as follows, when started from a single alive (1) cell:
---------------------------------------------- a(n)
   0:              (1)                          1
   1:             1(1)1                         2
   2:            11(0)01                        2
   3:           110(1)111                       3
   4:          1100(1)0001                      4
   5:         11011(1)10111                     5
   6:        110010(0)001001                    5
   7:       1101111(0)0111111                   5
   8:      11001000(1)11000001                  6
   9:     110111101(1)001000111                 7
  10:    1100100001(0)1111011001                7
  11:   11011110011(0)10000101111               7
  12:  110010001110(0)110011010001              7
  13: 1101111011001(1)1011100110111             8
We count how many 1's have occurred so far in the central column (indicated with parentheses), giving us the terms: 1, 2, 2, 3, 4, 5, 5, 5, 6, 7, 7, 7, 7, 8, ....
		

Links

• Antti Karttunen, Table of n, a(n) for n = 0..100000
• Stephen Wolfram, Announcing the Rule 30 Prizes, 2019
• Index entries for sequences related to cellular automata

Crossrefs

Cf. A051023, A110240, A269160, A327973, A327980, A327981, A327983, A327984.

Programs

Mathematica

A327982list[nmax_]:=Accumulate[CellularAutomaton[30,{{1},0},{nmax,{{0}}}]];A327982list[100] (* Paolo Xausa, May 30 2023 *)

PARI

A269160(n) = bitxor(n, bitor(2*n, 4*n)); \\ From A269160.
A110240(n) = if(!n,1,A269160(A110240(n-1)));
A051023(n) = ((A110240(n)>>n)%2);
A327982(n) = (A051023(n)+if(0==n,0,A327982(n-1)));

PARI

up_to = 105;
A269160(n) = bitxor(n, bitor(2*n, 4*n));
A327982list(up_to) = { my(v=vector(1+up_to), s=1, n=0, c=0); while(n<=up_to, c += (s>>n)%2; n++; v[n] = c; s = A269160(s)); (v); }
v327982 = A327982list(up_to);
A327982(n) = v327982[1+n];

Formula

a(0) = A051023(0) = 1, for n > 0, a(n) = A051023(n) + a(n-1).

For all n >= 0, a(A327984(n)) = n.