|
| |
|
|
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
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)
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
|
|
|
|
FORMULA
|
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
|
|
|
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:
|
|
|
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)
(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=", ")
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
easy,nonn
|
|
|
AUTHOR
|
James Kilfiger (jamesk(AT)maths.warwick.ac.uk)
|
|
|
STATUS
|
approved
|
| |
|
|
