cp's OEIS Frontend

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

%I A071542 #38 Aug 20 2024 09:13:52
%S A071542 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 A071542 12,12,12,13,13,14,14,15,15,15,15,16,16,16,16,17,17,17,17,18,18,18,18,
%U A071542 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 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).
%H A071542 Antti Karttunen, <a href="/A071542/b071542.txt">Table of n, a(n) for n = 0..131072</a>
%F A071542 a(0)=0, a(n) = 1 + A071542(n - A000120(n)). - _Antti Karttunen_, Oct 24 2012
%F A071542 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 A071542 17 (= 10001 in binary) -> 15 (= 1111) -> 11 (= 1011) -> 8 (= 1000) -> 7 (= 111) -> 4 (= 100) -> 3 (= 11) -> 1 -> 0, hence a(17)=8.
%t A071542 Table[-1 + Length@ NestWhileList[# - DigitCount[#, 2, 1] &, n, # > 0 &], {n, 0, 75}] (* _Michael De Vlieger_, Jul 16 2017 *)
%o A071542 (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 A071542 (PARI) a(n)=my(k);while(n,n-=hammingweight(n);k++);k \\ _Charles R Greathouse IV_, Oct 30 2012
%o A071542 (MIT/GNU Scheme)
%o A071542 ;; with memoizing definec-macro:
%o A071542 (definec (A071542 n) (if (zero? n) n (+ 1 (A071542 (- n (A000120 n)))))) ;; _Antti Karttunen_, Oct 24 2012
%Y A071542 Cf. A000120, A011371, A071542, A213706, A213707, A213708, A218254.
%Y A071542 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 A071542 A213709(n) = a((2^(n+1))-1) - a((2^n)-1).
%K A071542 easy,nonn
%O A071542 0,3
%A A071542 _Benoit Cloitre_, Jun 02 2002
%E A071542 Starting offset changed to 0 with a(0) prepended as 0 by _Antti Karttunen_, Oct 24 2012