A086876 Run lengths in A071542.

1, 1, 2, 2, 2, 2, 2, 4, 2, 2, 4, 4, 4, 2, 2, 4, 4, 4, 4, 4, 4, 4, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 6, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 6, 2, 4, 4, 4, 4, 4, 4, 6, 4, 6, 6, 6, 6, 6, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 6, 2, 4, 4, 4, 4, 4, 4, 6, 4, 6, 6, 6

Offset: 0

Author

Ralf Stephan, Aug 21 2003

Keywords

• nonn
• easy

Comments

All a(n) are even for n>1.

Although this can be viewed as a list, the indexing still starts from zero, because a(n) tells from how many starting values one can end to 0 in n steps, with the iterative process described in A071542 (if going around in 0->0 loop is disallowed). I.e., a(n) gives the number of all nodes (whether internal or leaves) in "beanstalk" (see A179016) from which the distance to the root (zero) is n.

Records occur at positions { 1,2,7,37,122,... } which correspond to run start positions { 2,4,16,126,512,... } in A071542.

Examples

			There is only one way to reach 0 in 0 steps from anywhere, and that is from 0 itself.
There is only one way to reach 0 in 1 steps from anywhere (with no 0->0 transition allowed), and that is from 1, as 1-A000120(1)=0.
There are two ways to reach 0 in 2 steps, from 2, as 2-A000120(2)=1, and 1-A000120(1)=0, and from 3, as 3-A000120(3)=1, and 1-A000120(1)=0.
Thus a(0)=a(1)=1 and a(2)=2.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 0..8728

Crossrefs

Essentially the first differences of both A173601 and A213708.

Programs

PARI

e1(n)=sum(k=0, floor(log(n)/log(2)), bittest(n, k))
f(n)=local(c); c=0; while(n, n=n-e1(n); c=c+1); c
p=1; r=1; for(n=1, 150, c=0; while(f(r) == p, r=r+1; c=c+1); p=f(r); print1(c", "))

Extensions

Changed the starting offset by prepending a(0)=1 (with the indexing of the rest of terms thus not changed), as A071542 now contains an initial zero. - Antti Karttunen, Nov 02 2012