The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A061313 Minimal number of steps to get from 1 to n by (a) subtracting 1 or (b) multiplying by 2. 7
 0, 1, 3, 2, 5, 4, 4, 3, 7, 6, 6, 5, 6, 5, 5, 4, 9, 8, 8, 7, 8, 7, 7, 6, 8, 7, 7, 6, 7, 6, 6, 5, 11, 10, 10, 9, 10, 9, 9, 8, 10, 9, 9, 8, 9, 8, 8, 7, 10, 9, 9, 8, 9, 8, 8, 7, 9, 8, 8, 7, 8, 7, 7, 6, 13, 12, 12, 11, 12, 11, 11, 10, 12, 11, 11, 10, 11, 10, 10, 9, 12, 11, 11, 10, 11, 10, 10, 9, 11, 10 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,3 COMMENTS Also number of steps to get from n to 1 by process of adding 1 if odd, or dividing by 2 if even. It is straightforward to prove that the number n appears F(n) times in this sequence, where F(n) is the n-th Fibonacci number (A000045). - Gary Gordon, May 31 2019 Conjecture: a(n)+2 is the sum of the terms of the Hirzebruch (negative) continued fraction for the Stern-Brocot tree fraction A007305(n)/A007306(n). - Andrey Zabolotskiy, Apr 17 2020 LINKS Reinhard Zumkeller, Table of n, a(n) for n = 1..10000 Ralf Stephan, Some divide-and-conquer sequences ... Ralf Stephan, Table of generating functions Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003. FORMULA a(2n) = a(n)+1; a(2n+1) = a(n+1)+2; a(1) = 0. Is Sum_{k=1..n} a(k) asymptotic to C*n*log(n) where 3 > C > 2? - Benoit Cloitre, Aug 31 2002 G.f.: x/(1-x) * Sum_{k>=0} (x^2^k + x^2^(k+1)/(1+x^2^k)). - Ralf Stephan, Jun 14 2003 a(n) = A080791(n-1) + A029837(n). - Ralf Stephan, Jun 14 2003 a(n) = 2*A023416(n-1) + A000120(n-1) = A023416(A062880(n)) = A023416(A000695(n)) + 1. - Ralf Stephan, Jul 16 2003 a(n) = A119477(n) - 1. - Philippe Deléham, Nov 03 2008 EXAMPLE a(2) = 1 since 2 = 1*2, a(3) = 3 since 3 = 1*2*2-1, a(11) = 6 since 11 = (1*2*2-1)*2*2-1. MATHEMATICA f[n_] := Block[{c = 0, m = n}, While[m != 1, If[ EvenQ[m], While[ EvenQ[m], m = m/2; c++ ], m++; c++ ]]; Return[c]]; Table[f[n], {n, 1, 100}] PROG (PARI) a(n)=if(n<2, 0, s=n; c=1; while((s+s%2)/(2-s%2)>1, s=(s+s%2)/(2-s%2); c++); c) (PARI) xpcount(n) = { p = 1; for(x=1, n, p1 = x; ct=0; while(p1>1, if(p1%2==0, p1/=2; ct++, p1 = p1*p+1; ct++) ); print1(ct, ", ") ) } (PARI) a(n) = if(n--, 2*(logint(n, 2)+1)) - hammingweight(n); \\ Kevin Ryde, Oct 21 2021 (Haskell) a061313 n = fst \$ until ((== 1) . snd) (\(u, v) -> (u + 1, f v)) (0, n)    where f n = if r == 0 then n' else n + 1  where (n', r) = divMod n 2 -- Reinhard Zumkeller, Sep 05 2015 CROSSREFS Cf. A056792, A006577, A029837, A000045. Cf. A007305, A007306, A008687. Sequence in context: A076243 A140061 A292776 * A259846 A087669 A053087 Adjacent sequences:  A061310 A061311 A061312 * A061314 A061315 A061316 KEYWORD easy,nonn AUTHOR Henry Bottomley, Jun 06 2001 STATUS approved

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

Last modified September 26 18:11 EDT 2022. Contains 357002 sequences. (Running on oeis4.)