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

Author

Joerg Arndt, Jan 15 2011

Keywords

• nonn

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

Crossrefs

Cf. A000120, A072086.

One less than A078627.

Programs

Haskell

a180094 n = snd $ until ((< 2) . fst) (\(x, c) -> (a000120 x, c+1)) (n,0)
-- Reinhard Zumkeller, Apr 22 2011

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

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

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 */

Python

def a(n):
    c = 1 if n > 1 else 0
    while (n:=n.bit_count()) > 1:
        c += 1
    return c
print([a(n) for n in range(101)]) # Michael S. Branicky, Mar 12 2025