login
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).
25

%I #38 Aug 20 2024 09:13:52

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

%T 12,12,12,13,13,14,14,15,15,15,15,16,16,16,16,17,17,17,17,18,18,18,18,

%U 19,19,19,19,20,20,20,20,21,21,21,21,22,22,23,23,24,24,24,24,25,25,25,25

%N 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).

%H Antti Karttunen, <a href="/A071542/b071542.txt">Table of n, a(n) for n = 0..131072</a>

%F a(0)=0, a(n) = 1 + A071542(n - A000120(n)). - _Antti Karttunen_, Oct 24 2012

%F 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...).

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

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

%o (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, ", "); ); )

%o (PARI) a(n)=my(k);while(n,n-=hammingweight(n);k++);k \\ _Charles R Greathouse IV_, Oct 30 2012

%o (MIT/GNU Scheme)

%o ;; with memoizing definec-macro:

%o (definec (A071542 n) (if (zero? n) n (+ 1 (A071542 (- n (A000120 n)))))) ;; _Antti Karttunen_, Oct 24 2012

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

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

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

%K easy,nonn

%O 0,3

%A _Benoit Cloitre_, Jun 02 2002

%E Starting offset changed to 0 with a(0) prepended as 0 by _Antti Karttunen_, Oct 24 2012