A180094 Number of steps to reach 0 or 1, starting with n and applying the map k -> (number of 1's in binary expansion of k) repeatedly.

0, 0, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 2, 1, 2, 2, 3, 2, 3, 3, 2, 2, 3, 3, 2, 3, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 2, 2, 3, 3, 2, 3, 2, 2, 3, 2, 3, 3, 2, 3, 2, 2, 3, 3, 2, 2, 3, 2, 3, 3, 3, 1, 2, 2, 3, 2, 3, 3, 2, 2, 3, 3, 2, 3, 2, 2, 3, 2, 3, 3, 2, 3, 2, 2, 3, 3, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 2, 3

Offset

0,4

Comments

The number of 1's in binary expansion of n is called the binary weight (or Hamming weight) of n, A000120(n).

a(n)=0 for n=0 and n=1; a(n)=1 for powers of 2.

Records appear for n = 2, 3, 7, 127=2^7-1, 2^127-1, ... (terms of A007013).

It appears that the indices of the even terms for n>0 are sequence A075311.

Links

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Maple

a:= n-> `if`(n<2, 0, 1 + a(add(i, i=convert(n, base, 2)))):
seq(a(n), n=0..100);  # Alois P. Heinz, Jan 15 2011

Mathematica

Table[Length[NestWhileList[DigitCount[#, 2, 1]&, n, #>1&]]-1, {n, 0, 100}] (* Harvey P. Dale, Jul 27 2012 *)

Prog

(PARI)
bitcount(x)=
{ /* Return Hamming weight of x, i.e. A000120(x) */
    local(p);  p = 0;
    while ( x, p+=bitand(x, 1); x>>=1; );
    return( p );
}
X(n)=
{ /* Return how many iterations of bitcount() are needed to reach 0 or 1 */
    if ( n<=1, return(0) );
    return( 1+X(bitcount(n)) );
}
{ for (n=0, 100, print1(X(n), ", ") ); } /* print terms of sequence */
(Magma)
Countbits:=func< n | &+Intseq(n, 2) >;
StepsTo01:=function(n); s:=0; k:=n; while k gt 1 do k:=Countbits(k); s+:=1; end while; return s; end function;
[ StepsTo01(n): n in [0..105] ]; // Klaus Brockhaus, Jan 15 2011
(Haskell)
a180094 n = snd $ until ((< 2) . fst) (\(x, c) -> (a000120 x, c+1)) (n, 0)
-- Reinhard Zumkeller, Apr 22 2011

Crossrefs

Cf. A000120, A072086.

One less than A078627.

Sequence in context: A179868 A104232 A072086 * A333870 A354914 A366927

Adjacent sequences: A180091 A180092 A180093 * A180095 A180096 A180097

Keyword

nonn

Author

Joerg Arndt, Jan 15 2011

Status

approved