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

%I #18 May 31 2023 09:11:43

%S 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,

%T 16,17,18,18,18,19,20,21,21,22,22,23,23,24,25,25,25,25,25,26,27,27,27,

%U 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

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

%C Lexicographically earliest monotonic left inverse of A327984.

%C 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.

%H Antti Karttunen, <a href="/A327982/b327982.txt">Table of n, a(n) for n = 0..100000</a>

%H Stephen Wolfram, <a href="https://blog.wolfram.com/2019/10/01/announcing-the-rule-30-prizes/">Announcing the Rule 30 Prizes</a>, 2019

%H <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>

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

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

%e The evolution of one-dimensional cellular automaton rule 30 proceeds as follows, when started from a single alive (1) cell:

%e ---------------------------------------------- a(n)

%e 0: (1) 1

%e 1: 1(1)1 2

%e 2: 11(0)01 2

%e 3: 110(1)111 3

%e 4: 1100(1)0001 4

%e 5: 11011(1)10111 5

%e 6: 110010(0)001001 5

%e 7: 1101111(0)0111111 5

%e 8: 11001000(1)11000001 6

%e 9: 110111101(1)001000111 7

%e 10: 1100100001(0)1111011001 7

%e 11: 11011110011(0)10000101111 7

%e 12: 110010001110(0)110011010001 7

%e 13: 1101111011001(1)1011100110111 8

%e 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, ....

%t A327982list[nmax_]:=Accumulate[CellularAutomaton[30,{{1},0},{nmax,{{0}}}]];A327982list[100] (* _Paolo Xausa_, May 30 2023 *)

%o (PARI)

%o A269160(n) = bitxor(n, bitor(2*n, 4*n)); \\ From A269160.

%o A110240(n) = if(!n,1,A269160(A110240(n-1)));

%o A051023(n) = ((A110240(n)>>n)%2);

%o A327982(n) = (A051023(n)+if(0==n,0,A327982(n-1)));

%o (PARI)

%o up_to = 105;

%o A269160(n) = bitxor(n, bitor(2*n, 4*n));

%o 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); }

%o v327982 = A327982list(up_to);

%o A327982(n) = v327982[1+n];

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

%K nonn

%O 0,2

%A _Antti Karttunen_, Oct 03 2019