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

%I #141 Jun 28 2024 23:15:58

%S 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,

%T 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,

%U 8,8,9,7,8,8,9,8,9,9,10,7,8,8,9,8,9,9

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

%C 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.

%C 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

%C From _Daniel Forgues_, Jul 31 2012: (Start)

%C 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

%C a(n) = a(n-0)

%C a(n) = a(n-1).a(n-2)

%C a(n) = a(n-2).a(n-3).a(n-3).a(n-4)

%C 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)

%C which suggests the sequence

%C {0}

%C {1, 2}

%C {2, 3, 3, 4}

%C {3, 4, 4, 5, 4, 5, 5, 6}

%C whose concatenation gives A014701 (this sequence).

%C Number of multiplications to compute n-th power by the Chandah-sutra method, also called left-to-right binary exponentiation:

%C x^1 = x^( 1_2) = (x) (0 prod)

%C x^2 = x^( 10_2) = (x^2) (1 prod)

%C x^3 = x^( 11_2) = (x^2) * (x) (2 prod)

%C x^4 = x^( 100_2) = (x^2)^2 (2 prod)

%C x^5 = x^( 101_2) = (x^2)^2 * (x) (3 prod)

%C x^6 = x^( 110_2) = (x^2)^2 * (x^2) (3 prod)

%C x^7 = x^( 111_2) = (x^2)^2 * (x^2) * (x) (4 prod)

%C x^8 = x^(1000_2) = ((x^2)^2)^2 (3 prod) (End)

%C From _Ya-Ping Lu_, Mar 03 2021: (Start)

%C Index at which record m occurs is A052955(m).

%C 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.

%C The last appearance of m in the sequence is at n = 2^m. (End)

%C 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

%H Alois P. Heinz, <a href="/A014701/b014701.txt">Table of n, a(n) for n = 1..16384</a> (first 1000 terms from T. D. Noe)

%H C. K. Caldwell, The Prime Glossary, <a href="https://t5k.org/glossary/page.php?sort=BinaryExponentiation">binary exponentiation</a>

%H Hermann Gruber and Markus Holzer, <a href="https://doi.org/10.4230/LIPIcs.MFCS.2021.52">Optimal Regular Expressions for Palindromes of Given Length</a>, Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, Article No. 53, pp. 53:1-53:15, 2021.

%H J. Jordan and R. Southwell, <a href="http://dx.doi.org/10.4236/am.2010.15045">Further Properties of Reproducing Graphs</a>, Applied Mathematics, Vol. 1 No. 5, 2010, pp. 344-350. - From _N. J. A. Sloane_, Feb 03 2013

%H Szymon Ɓukaszyk and Wawrzyniec Bieniawski, <a href="https://doi.org/10.20944/preprints202401.1113.v1">Assembly Theory of Binary Messages (How to Assemble a Black Hole and Use it to Assemble New Binary Information?)</a>, Preprints (2024).

%H OEIS Wiki, <a href="/wiki/Fibonacci_rabbits#Properties">Binary Fibonacci rabbits sequence</a>

%H <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%F a(n) = A056792(n) - 1 = A056791(n) - 2.

%F 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

%F 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

%F 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

%F 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

%F 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

%F For n > 1: a(n) = A007953(A007931(n-1)). - _Reinhard Zumkeller_, Oct 26 2012

%F a(n) >= A003313(n). - _Charles R Greathouse IV_, Jan 03 2018

%F a(n) = a(floor(n/2)) + 1 + (n mod 2) for n > 1. - _Pablo Hueso Merino_, Oct 28 2020

%F 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

%e 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.

%p 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;

%p # second Maple program:

%p a:= n-> add(i+1, i=Bits[Split](n))-2:

%p seq(a(n), n=1..128); # _Alois P. Heinz_, Aug 30 2021

%t a[n_] := DigitCount[n, 2] /. {x_, y_} -> 2x + y - 2; Array[a, 100] (* _Robert G. Wilson v_, Jul 31 2012 *)

%o (Haskell)

%o a014701 1 = 0

%o a014701 n = a007953 $ a007931 (n - 1)

%o -- _Reinhard Zumkeller_, Oct 26 2012

%o (PARI) a(n)=hammingweight(n)+logint(n,2)-1 \\ _Charles R Greathouse IV_, Dec 29 2016

%o (Python)

%o def a(n):

%o if n==1:

%o return 0

%o return a(n//2)+1+n%2

%o for i in range(1,60):

%o print(a(i), end=", ")

%o # _Pablo Hueso Merino_, Oct 28 2020

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

%K easy,nonn

%O 1,3

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