A078627 Write n in binary; repeatedly sum the "digits" until reaching 1; a(n) = 1 + number of steps required.

1, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 3, 2, 3, 3, 4, 3, 4, 4, 3, 3, 4, 4, 3, 4, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 3, 3, 4, 4, 3, 4, 3, 3, 4, 3, 4, 4, 3, 4, 3, 3, 4, 4, 3, 3, 4, 3, 4, 4, 4, 2, 3, 3, 4, 3, 4, 4, 3, 3, 4, 4, 3, 4, 3, 3, 4, 3, 4, 4, 3, 4, 3, 3, 4, 4, 3, 3, 4, 3, 4, 4, 4, 3, 4, 4, 3, 4, 3, 3, 4, 4, 3

Offset: 1

Author

Frank Schwellinger (nummer_eins(AT)web.de), Dec 12 2002

Keywords

• base
• easy
• nonn

Comments

The terms a(n) are unbounded. The smallest n with a(n) = m, n_min(m), however may be exorbitantly large, even for small m. It can be calculated by the following recurrence: n_min(1) = 1; n_min(2) = 2; n_min(m) = 2^n_min(m-1) - 1 {if m > 2};

Examples

			a(13) = 4 because 13 = (1101) -> (1+1+0+1 = 11) -> (1+1 = 10) -> (1+0 = 1) = 1. (Three iterations were required to reach 1.)
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..8192
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A000120.

One more than A180094. Row lengths of A381962.

Programs

Maple

for n from 1 to 500 do h := n:a[n] := 1:while(h>1) do a[n] := a[n]+1: b := convert(h,base,2):h := sum(b[j],j=1..nops(b)):od:od:seq(a[j],j=1..500);

Mathematica

Table[Length[NestWhileList[Total[IntegerDigits[#,2]]&,n,#>1&]],{n,110}] (* Harvey P. Dale, Oct 10 2011 *)

PARI

A078627(n) = { my(k=1); while(n>1, n = hammingweight(n); k += 1); (k); }; \\ Antti Karttunen, Jul 09 2017

Python

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

Formula

a(1) = 1; for n > 1, a(n) = 1 + a(A000120(n)), where A000120 gives the number of occurrences of digit 1 in binary representation of n.

a(n) = 1 + A180094(n). - Antti Karttunen, Jul 09 2017

Extensions

Description corrected by Antti Karttunen, Jul 09 2017