A014701 Number of multiplications to compute n-th power by the Chandah-sutra method.

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

Offset: 1

Author

James Kilfiger (jamesk(AT)maths.warwick.ac.uk)

Keywords

• easy
• nonn

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)

a(n) is the digit sum of n-1 in bijective base-2. Since the Fibonacci number F(m) can be defined as the number of ways to compose m as the sum of 1s and 2s, we get that m appears F(m) times in the sequence. - Oscar Cunningham, Apr 14 2024

Conjecture: a(n+1) is the minimal number of steps to go from 0 to n, by choosing before each step, after the first step, whether to keep the same step length or double it. The initial step length is 1. - Jean-Marc Rebert, May 15 2025

Examples

			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.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..16384 (first 1000 terms from T. D. Noe)
• Wawrzyniec Bieniawski, Piotr Masierak, Andrzej Tomski, and Szymon Łukaszyk, Assembly Theory - Formalizing Assembly Spaces and Discovering Patterns and Bounds, Preprints (2025).
• C. K. Caldwell, The Prime Glossary, binary exponentiation
• Hermann Gruber and Markus Holzer, Optimal Regular Expressions for Palindromes of Given Length, Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, Article No. 53, pp. 53:1-53:15, 2021.
• 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
• Szymon Łukaszyk and Wawrzyniec Bieniawski, Assembly Theory of Binary Messages (How to Assemble a Black Hole and Use it to Assemble New Binary Information?), Preprints (2024).
• 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

Crossrefs

Cf. A003313, A056791, A056792, A115964, A052955.

Programs

Haskell

a014701 1 = 0
a014701 n = a007953 $ a007931 (n - 1)
-- Reinhard Zumkeller, Oct 26 2012

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 *)

PARI

a(n)=hammingweight(n)+logint(n,2)-1 \\ Charles R Greathouse IV, Dec 29 2016

Python

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

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

a(n+1) = max_{1<=i<=n} (H(i) + H(n-i)) where H(n) denotes the Hamming weight of n (A000120(n)). See Lemma 8 in Gruber/Holzer 2021 article. - Hermann Gruber, Jun 26 2024