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

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

Offset: 0

Author

Antti Karttunen, Feb 21 2016

Keywords

• nonn

Comments

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.

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

See also comments in A269165.

Links

• Antti Karttunen, Table of n, a(n) for n = 0..32767
• Eric Weisstein's World of Mathematics, Rule 30
• Index entries for sequences related to cellular automata
• Index to Elementary Cellular Automata

Crossrefs

Cf. A110240, A269160, A269162.

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

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

Cf. also A268389.

Programs

Scheme

;; This implementation is based on given recurrence and utilitizes the memoization-macro definec:
(definec (A269166 n) (let ((p (A269162 n))) (if (zero? p) 0 (+ 1 (A269166 p)))))
;; This one computes the same with tail-recursive iteration:
(define (A269166 n) (let loop ((n n) (p (A269162 n)) (s 0)) (if (zero? p) s (loop p (A269162 p) (+ 1 s)))))

Formula

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

Other identities. For all n >= 0:

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