|
| |
|
|
A014701
|
|
Number of multiplications to compute n-th power by method of Chandra-sutra.
|
|
4
| |
|
|
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, 10, 8, 9, 9, 10, 9, 10, 10, 11, 7, 8, 8
(list; graph; refs; listen; history; 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). [From Lekraj Beedassy (blekraj(AT)yahoo.com), May 28 2010]
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=1..1000
C. K. Caldwell, The Prime Glossary, binary exponentiation. [From Lekraj Beedassy (blekraj(AT)yahoo.com), May 28 2010]
|
|
|
FORMULA
| a(n)=floor(log_2(n)) + number of 1's in binary representation of n.
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 (benoit7848c(AT)orange.fr), 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 (ralf(AT)ark.in-berlin.de), Aug 15 2003
|
|
|
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;
|
|
|
CROSSREFS
| Cf. A003313, A056791, A056792, A115964.
a(n) = A056792(n) - 1 = A056791(n) - 2.
Sequence in context: A117497 A117498 A064097 * A056239 A161511 A100197
Adjacent sequences: A014698 A014699 A014700 * A014702 A014703 A014704
|
|
|
KEYWORD
| easy,nonn
|
|
|
AUTHOR
| James Kilfiger (jamesk(AT)maths.warwick.ac.uk)
|
| |
|
|
