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

 

Logo
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

Index to sequences related to the complexity of n

Index entries for sequences related to binary expansion of n

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 11 15:10 EDT 2022. Contains 356066 sequences. (Running on oeis4.)