A269166 - OEIS

%I #11 Feb 21 2016 19:20:56

%S 0,0,0,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,2,1,1,1,0,0,0,0,0,

%T 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,2,1,1,1,0,1,0,0,0,0,0,0,1,0,0,0,0,

%U 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,2,2,2,0,1,1,1,1,1,0,0,3,1,0,0,0,0,0,0,1,0

%N If A269162(n) = 0, then a(n) = 0, otherwise a(n) = 1 + a(A269162(n)).

%C a(n) gives the generational distance to the earliest finite ancestor when the binary expansion of n is interpreted as a pattern in Wolfram's Rule-30 cellular automaton or 0 if that pattern has no finite predecessors.

%C A110240 gives the record positions (after zero) and particularly, for n > 0, A110240(n) gives the first occurrence of n in this sequence.

%C See also comments in A269165.

%H Antti Karttunen, <a href="/A269166/b269166.txt">Table of n, a(n) for n = 0..32767</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Rule30.html">Rule 30</a>

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

%H <a href="https://oeis.org/wiki/Index_to_Elementary_Cellular_Automata">Index to Elementary Cellular Automata</a>

%F If A269162(n) = 0, then a(n) = 0, otherwise a(n) = 1 + a(A269162(n)).

%F Other identities. For all n >= 0:

%F a(A110240(n)) = n. [Works as a left inverse of sequence A110240.]

%o (Scheme)

%o ;; This implementation is based on given recurrence and utilitizes the memoization-macro definec:

%o (definec (A269166 n) (let ((p (A269162 n))) (if (zero? p) 0 (+ 1 (A269166 p)))))

%o ;; This one computes the same with tail-recursive iteration:

%o (define (A269166 n) (let loop ((n n) (p (A269162 n)) (s 0)) (if (zero? p) s (loop p (A269162 p) (+ 1 s)))))

%Y Cf. A110240, A269160, A269162.

%Y Cf. A269164 (the indices of zeros after the initial zero).

%Y Cf. A269165 (the earliest finite ancestor for n).

%Y Cf. also A268389.

%K nonn

%O 0,26

%A _Antti Karttunen_, Feb 21 2016