A071542 Number of steps to reach 0 starting with n and using the iterated process : x -> x - (number of 1's in binary representation of x).

0, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 7, 7, 8, 8, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25

Offset: 0

Author

Benoit Cloitre, Jun 02 2002

Keywords

• easy
• nonn

Examples

			17 (= 10001 in binary) -> 15 (= 1111) -> 11 (= 1011) -> 8 (= 1000) -> 7 (= 111) -> 4 (= 100) -> 3 (= 11) -> 1 -> 0, hence a(17)=8.
		

Links

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

Crossrefs

Cf. A000120, A011371, A071542, A213706, A213707, A213708, A218254.

A179016 gives the unique infinite sequence whose successive terms are related by this iterated process (in reverse order). Also, it seems that for n>=0, a(A213708(n)) = a(A179016(n+1)) = n.

A213709(n) = a((2^(n+1))-1) - a((2^n)-1).

Programs

Mathematica

Table[-1 + Length@ NestWhileList[# - DigitCount[#, 2, 1] &, n, # > 0 &], {n, 0, 75}] (* Michael De Vlieger, Jul 16 2017 *)

PARI

for(n=1, 150, s=n; t=0; while(s!=0, t++; s=s-sum(i=1, length(binary(s)), component(binary(s), i))); if(s==0, print1(t, ", "); ); )

PARI

a(n)=my(k);while(n,n-=hammingweight(n);k++);k \\ Charles R Greathouse IV, Oct 30 2012
(MIT/GNU Scheme)
;; with memoizing definec-macro:
(definec (A071542 n) (if (zero? n) n (+ 1 (A071542 (- n (A000120 n)))))) ;; Antti Karttunen, Oct 24 2012

Formula

a(0)=0, a(n) = 1 + A071542(n - A000120(n)). - Antti Karttunen, Oct 24 2012

It seems that a(n) ~ C n/log(n) asymptotically with C = 1.4... (n = 10^6 gives C = 1.469..., n = 10^7 gives C = 1.4614...).

Extensions

Starting offset changed to 0 with a(0) prepended as 0 by Antti Karttunen, Oct 24 2012