This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A014701 #163 May 20 2025 17:13:39
%S A014701 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 A014701 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 A014701 8,8,9,7,8,8,9,8,9,9,10,7,8,8,9,8,9,9
%N A014701 Number of multiplications to compute n-th power by the Chandah-sutra method.
%C A014701 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 A014701 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 A014701 From _Daniel Forgues_, Jul 31 2012: (Start)
%C A014701 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 A014701 a(n) = a(n-0)
%C A014701 a(n) = a(n-1).a(n-2)
%C A014701 a(n) = a(n-2).a(n-3).a(n-3).a(n-4)
%C A014701 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 A014701 which suggests the sequence
%C A014701 {0}
%C A014701 {1, 2}
%C A014701 {2, 3, 3, 4}
%C A014701 {3, 4, 4, 5, 4, 5, 5, 6}
%C A014701 whose concatenation gives A014701 (this sequence).
%C A014701 Number of multiplications to compute n-th power by the Chandah-sutra method, also called left-to-right binary exponentiation:
%C A014701 x^1 = x^( 1_2) = (x) (0 prod)
%C A014701 x^2 = x^( 10_2) = (x^2) (1 prod)
%C A014701 x^3 = x^( 11_2) = (x^2) * (x) (2 prod)
%C A014701 x^4 = x^( 100_2) = (x^2)^2 (2 prod)
%C A014701 x^5 = x^( 101_2) = (x^2)^2 * (x) (3 prod)
%C A014701 x^6 = x^( 110_2) = (x^2)^2 * (x^2) (3 prod)
%C A014701 x^7 = x^( 111_2) = (x^2)^2 * (x^2) * (x) (4 prod)
%C A014701 x^8 = x^(1000_2) = ((x^2)^2)^2 (3 prod) (End)
%C A014701 From _Ya-Ping Lu_, Mar 03 2021: (Start)
%C A014701 Index at which record m occurs is A052955(m).
%C A014701 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 A014701 The last appearance of m in the sequence is at n = 2^m. (End)
%C A014701 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
%C A014701 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
%H A014701 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 A014701 Wawrzyniec Bieniawski, Piotr Masierak, Andrzej Tomski, and Szymon Łukaszyk, <a href="https://www.preprints.org/manuscript/202409.1581">Assembly Theory - Formalizing Assembly Spaces and Discovering Patterns and Bounds</a>, Preprints (2025).
%H A014701 C. K. Caldwell, The Prime Glossary, <a href="https://t5k.org/glossary/page.php?sort=BinaryExponentiation">binary exponentiation</a>
%H A014701 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 A014701 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 A014701 Szymon Łukaszyk and Wawrzyniec Bieniawski, <a href="https://www.preprints.org/manuscript/202401.1113">Assembly Theory of Binary Messages (How to Assemble a Black Hole and Use it to Assemble New Binary Information?)</a>, Preprints (2024).
%H A014701 OEIS Wiki, <a href="/wiki/Fibonacci_rabbits#Properties">Binary Fibonacci rabbits sequence</a>
%H A014701 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%H A014701 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F A014701 a(n) = A056792(n) - 1 = A056791(n) - 2.
%F A014701 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 A014701 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 A014701 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 A014701 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 A014701 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 A014701 For n > 1: a(n) = A007953(A007931(n-1)). - _Reinhard Zumkeller_, Oct 26 2012
%F A014701 a(n) >= A003313(n). - _Charles R Greathouse IV_, Jan 03 2018
%F A014701 a(n) = a(floor(n/2)) + 1 + (n mod 2) for n > 1. - _Pablo Hueso Merino_, Oct 28 2020
%F A014701 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 A014701 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 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 A014701 # second Maple program:
%p A014701 a:= n-> add(i+1, i=Bits[Split](n))-2:
%p A014701 seq(a(n), n=1..128); # _Alois P. Heinz_, Aug 30 2021
%t A014701 a[n_] := DigitCount[n, 2] /. {x_, y_} -> 2x + y - 2; Array[a, 100] (* _Robert G. Wilson v_, Jul 31 2012 *)
%o A014701 (Haskell)
%o A014701 a014701 1 = 0
%o A014701 a014701 n = a007953 $ a007931 (n - 1)
%o A014701 -- _Reinhard Zumkeller_, Oct 26 2012
%o A014701 (PARI) a(n)=hammingweight(n)+logint(n,2)-1 \\ _Charles R Greathouse IV_, Dec 29 2016
%o A014701 (Python)
%o A014701 def a(n):
%o A014701 if n==1:
%o A014701 return 0
%o A014701 return a(n//2)+1+n%2
%o A014701 for i in range(1,60):
%o A014701 print(a(i), end=", ")
%o A014701 # _Pablo Hueso Merino_, Oct 28 2020
%Y A014701 Cf. A003313, A056791, A056792, A115964, A052955.
%K A014701 easy,nonn
%O A014701 1,3
%A A014701 James Kilfiger (jamesk(AT)maths.warwick.ac.uk)