|
Search: id:A064194
|
|
|
| A064194 |
|
Number of ring multiplications needed to multiply two degree-n polynomials using Karatsuba's algorithm. |
|
+0
2
|
|
| 1, 3, 7, 9, 17, 21, 25, 27, 43, 51, 59, 63, 71, 75, 79, 81, 113, 129, 145, 153, 169, 177, 185, 189, 205, 213, 221, 225, 233, 237, 241, 243, 307, 339, 371, 387, 419, 435, 451, 459, 491, 507, 523, 531, 547, 555, 563, 567, 599, 615, 631, 639, 655, 663, 671, 675
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
Number of gates in the AND/OR problem (see Chang/Tsai ref).
|
|
REFERENCES
|
K.-N. Chang and S.-C. Tsai, Exact solution of a minimal recurrence, Inform. Process. Lett. 75(2000), 61-64.
A. A. Karatsuba and Y.P. Ofman, Multiplication of multiplace numbers by automata. Dokl. Akad. Nauk SSSR 145, 2, 293-294 (1962).
|
|
LINKS
|
P. J. Grabner and H.-K. Hwang, Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence
|
|
FORMULA
|
a(2n) = 3*a(n); a(2n+1)=2*a(n+1)+a(n)
Partial sums of sequence { a(1)=1, a(n)=2^(e0(n-1)+1) }, where e0(n)=A023416(n) the zeros-counting function. - Ralf Stephan (ralf(AT)ark.in-berlin.de), Jul 29 2003
a(1) = 1, a(n) = a([n/2]) + 2a(ceil(n/2)), n>1.
a(n+1)=sum_{0<=i, j<=n} {binomial(i+j, i) mod 2} - Benoit Cloitre (benoit7848c(AT)orange.fr), Mar 07 2005
|
|
CROSSREFS
|
Sequence in context: A118258 A117583 A126106 this_sequence A036978 A079464 A036976
Adjacent sequences: A064191 A064192 A064193 this_sequence A064195 A064196 A064197
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
Guillaume Hanrot and Paul Zimmermann (hanrot(AT)loria.fr), Sep 21 2001
|
|
|
Search completed in 0.002 seconds
|
