cp's OEIS Frontend

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

%I A078627 #24 Mar 12 2025 17:27:18
%S A078627 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,
%T A078627 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,
%U A078627 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
%N A078627 Write n in binary; repeatedly sum the "digits" until reaching 1; a(n) = 1 + number of steps required.
%C A078627 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};
%H A078627 Antti Karttunen, <a href="/A078627/b078627.txt">Table of n, a(n) for n = 1..8192</a>
%H A078627 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F A078627 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.
%F A078627 a(n) = 1 + A180094(n). - _Antti Karttunen_, Jul 09 2017
%e A078627 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.)
%p A078627 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);
%t A078627 Table[Length[NestWhileList[Total[IntegerDigits[#,2]]&,n,#>1&]],{n,110}] (* _Harvey P. Dale_, Oct 10 2011 *)
%o A078627 (PARI) A078627(n) = { my(k=1); while(n>1, n = hammingweight(n); k += 1); (k); }; \\ _Antti Karttunen_, Jul 09 2017
%o A078627 (Python)
%o A078627 def a(n):
%o A078627     c = 1 if n > 1 else 0
%o A078627     while (n:=n.bit_count()) > 1:
%o A078627         c += 1
%o A078627     return c + 1
%o A078627 print([a(n) for n in range(1, 106)]) # _Michael S. Branicky_, Mar 12 2025
%Y A078627 Cf. A000120.
%Y A078627 One more than A180094. Row lengths of A381962.
%K A078627 base,easy,nonn
%O A078627 1,2
%A A078627 Frank Schwellinger (nummer_eins(AT)web.de), Dec 12 2002
%E A078627 Description corrected by _Antti Karttunen_, Jul 09 2017