login
This site is supported by donations 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 . 8
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 [appended by] 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)

LINKS

T. D. Noe, Table of n, a(n) for n = 1..1000

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) <= 2log_2(n) - 1 - Robert FERREOL, Oct 01 2014

Let u(1)=1, u(2n)=u(n)+1, u(2n+1)=u(2n)+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, (2x^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

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;

MATHEMATICA

f[n_] := DigitCount[n, 2] /. {x_, y_} -> 2x + y - 2; Array[f, 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

CROSSREFS

Cf. A003313, A056791, A056792, A115964.

Sequence in context: A117497 A117498 A064097 * A207034 A226164 A302039

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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 18 06:21 EST 2019. Contains 320245 sequences. (Running on oeis4.)