login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 25
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
LINKS
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...).
EXAMPLE
17 (= 10001 in binary) -> 15 (= 1111) -> 11 (= 1011) -> 8 (= 1000) -> 7 (= 111) -> 4 (= 100) -> 3 (= 11) -> 1 -> 0, hence a(17)=8.
MATHEMATICA
Table[-1 + Length@ NestWhileList[# - DigitCount[#, 2, 1] &, n, # > 0 &], {n, 0, 75}] (* Michael De Vlieger, Jul 16 2017 *)
PROG
(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
CROSSREFS
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).
Sequence in context: A274618 A176843 A238263 * A264810 A176841 A176814
KEYWORD
easy,nonn
AUTHOR
Benoit Cloitre, Jun 02 2002
EXTENSIONS
Starting offset changed to 0 with a(0) prepended as 0 by Antti Karttunen, Oct 24 2012
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 25 10:22 EDT 2024. Contains 371967 sequences. (Running on oeis4.)