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,2

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};

Links

Antti Karttunen, Table of n, a(n) for n = 1..8192

Index entries for sequences related to binary expansion of n

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

Example

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

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

Prog

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

Crossrefs

Cf. A000120.

One more than A180094.

Sequence in context: A129759 A137467 A261461 * A106370 A128630 A273040

Adjacent sequences: A078624 A078625 A078626 * A078628 A078629 A078630

Keyword

base,easy,nonn

Author

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

Extensions

Description corrected by Antti Karttunen, Jul 09 2017

Status

approved