The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A014701 Number of multiplications to compute n-th power by the Chandah-sutra method. 10
 0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 5, 6, 6, 7, 6, 7, 7, 8, 6, 7, 7, 8, 7, 8, 8, 9, 6, 7, 7, 8, 7, 8, 8, 9, 7, 8, 8, 9, 8, 9, 9, 10, 6, 7, 7, 8, 7, 8, 8, 9, 7, 8, 8, 9, 8, 9, 9, 10, 7, 8, 8, 9, 8, 9, 9 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,3 COMMENTS In other words, number of steps to reach 1 starting from n and using the process: x -> x-1 if n is odd and x -> x/2 otherwise. a(n) = number of 0's + twice number of 1's (disregarding the leading digit 1) in the binary expansion of n, i.e., A007088(n). - Lekraj Beedassy, May 28 2010 From Daniel Forgues, Jul 31 2012: (Start) For the binary Fibonacci rabbits sequence (A036299) (cf. OEIS Wiki link below) we have the substitution/concatenation rule: a(n), n >= 3, may be obtained by the concatenation of a(n-1) and a(n-2), with a(1) = 0, a(2) = 1. Thus, using . (dot) as the concatenation operator, we have the recursive substitution/concatenation     a(n) = a(n-0)     a(n) = a(n-1).a(n-2)     a(n) = a(n-2).a(n-3).a(n-3).a(n-4)     a(n) = a(n-3).a(n-4).a(n-4).a(n-5).a(n-4).a(n-5).a(n-5).a(n-6)   which suggests the sequence     {0}     {1, 2}     {2, 3, 3, 4}     {3, 4, 4, 5, 4, 5, 5, 6}   whose concatenation gives A014701 (this sequence). Number of multiplications to compute n-th power by the Chandah-sutra method, also called left-to-right binary exponentiation:   x^1 = x^(   1_2) =                                 (x)   (0 prod)   x^2 = x^(  10_2) =                         (x^2)         (1 prod)   x^3 = x^(  11_2) =                         (x^2) * (x)   (2 prod)   x^4 = x^( 100_2) =               (x^2)^2                 (2 prod)   x^5 = x^( 101_2) =               (x^2)^2         * (x)   (3 prod)   x^6 = x^( 110_2) =               (x^2)^2 * (x^2)         (3 prod)   x^7 = x^( 111_2) =               (x^2)^2 * (x^2) * (x)   (4 prod)   x^8 = x^(1000_2) = ((x^2)^2)^2                           (3 prod) (End) From Ya-Ping Lu, Mar 03 2021: (Start) Index at which record m occurs is A052955(m). First appearance of m in the sequence (or the record value m) is at n = 2^(m/2 + 1) - 1 for even m, and at n = 3*2^((m - 1)/2) - 1 for odd m. The last appearance of m in the sequence is at n = 2^m. (End) LINKS Alois P. Heinz, Table of n, a(n) for n = 1..16384 (first 1000 terms from T. D. Noe) C. K. Caldwell, The Prime Glossary, binary exponentiation J. Jordan and R. Southwell, Further Properties of Reproducing Graphs, Applied Mathematics, Vol. 1 No. 5, 2010, pp. 344-350. - From N. J. A. Sloane, Feb 03 2013 OEIS Wiki, Binary Fibonacci rabbits sequence FORMULA a(n) = A056792(n) - 1 = A056791(n) - 2. a(n) = floor(log_2(n)) + (number of 1's in binary representation of n) - 1. - Corrected (- 1 at end) by Daniel Forgues, Aug 01 2012 a(2^n) = n, a(2^n-1) = 2*(n-1), and for n >= 2, log_2(n) <= a(n) <= 2*log_2(n) - 1. - Robert FERREOL, Oct 01 2014 Let u(1) = 1, u(2*n) = u(n)+1, u(2*n+1) = u(2*n)+1; then a(1) = 0 and a(n) = u(n-1). - Benoit Cloitre, Dec 19 2002 G.f.: -2/(1-x) + (1/(1-x)) * Sum_{k>=0} (2*x^2^k + x^2^(k+1))/(1+x^2^k). - Ralf Stephan, Aug 15 2003 From {0}, apply the substitution rule (n -> n+1, n+2) repeatedly, giving {{0}, {1, 2}, {2, 3, 3, 4}, {3, 4, 4, 5, 4, 5, 5, 6}, ...} and concatenate. - Daniel Forgues, Jul 31 2012 For n > 1: a(n) = A007953(A007931(n-1)). - Reinhard Zumkeller, Oct 26 2012 a(n) >= A003313(n). - Charles R Greathouse IV, Jan 03 2018 a(n) = a(floor(n/2)) + 1 + (n mod 2) for n > 1. - Pablo Hueso Merino, Oct 28 2020 EXAMPLE 5 -> 4 -> 2 -> 1 so 3 steps are needed to reach 1 hence a(5)=3; 9 -> 8 -> 4 -> 2 -> 1 hence a(9)=4. MAPLE A014701 := proc(n) local j, k; j := n; k := 0; while(j>1) do if j mod 2=1 then j := j-1 else j := j/2 fi; k := k+1 od end; # second Maple program: a:= n-> add(i+1, i=Bits[Split](n))-2: seq(a(n), n=1..128);  # Alois P. Heinz, Aug 30 2021 MATHEMATICA a[n_] := DigitCount[n, 2] /. {x_, y_} -> 2x + y - 2; Array[a, 100] (* Robert G. Wilson v, Jul 31 2012 *) PROG (Haskell) a014701 1 = 0 a014701 n = a007953 \$ a007931 (n - 1) -- Reinhard Zumkeller, Oct 26 2012 (PARI) a(n)=hammingweight(n)+logint(n, 2)-1 \\ Charles R Greathouse IV, Dec 29 2016 (Python3) def a(n):     if n==1:         return 0     return a(n//2)+1+n%2 for i in range(1, 60):     print(a(i), end=", ") # Pablo Hueso Merino, Oct 28 2020 CROSSREFS Cf. A003313, A056791, A056792, A115964, A052955. Sequence in context: A117497 A117498 A064097 * A207034 A226164 A308220 Adjacent sequences:  A014698 A014699 A014700 * A014702 A014703 A014704 KEYWORD easy,nonn AUTHOR James Kilfiger (jamesk(AT)maths.warwick.ac.uk) 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 August 11 15:10 EDT 2022. Contains 356066 sequences. (Running on oeis4.)