login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A078627 Write n in binary; repeatedly sum the "digits" until reaching 1; a(n) = 1 + number of steps required. 3

%I

%S 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 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 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 Write n in binary; repeatedly sum the "digits" until reaching 1; a(n) = 1 + number of steps required.

%C 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 Antti Karttunen, <a href="/A078627/b078627.txt">Table of n, a(n) for n = 1..8192</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%F 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 a(n) = 1 + A180094(n). - _Antti Karttunen_, Jul 09 2017

%e 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 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 Table[Length[NestWhileList[Total[IntegerDigits[#,2]]&,n,#>1&]],{n,110}] (* _Harvey P. Dale_, Oct 10 2011 *)

%o (PARI) A078627(n) = { my(k=1); while(n>1, n = hammingweight(n); k += 1); (k); }; \\ _Antti Karttunen_, Jul 09 2017

%Y Cf. A000120.

%Y One more than A180094.

%K base,easy,nonn

%O 1,2

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

%E Description corrected by _Antti Karttunen_, Jul 09 2017

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 18 10:31 EDT 2020. Contains 337166 sequences. (Running on oeis4.)