|
Search: id:A059975
|
|
|
| A059975 |
|
n*a(n) is the number of complex multiplications needed for the fast Fourier transform of n numbers, writing n = r1 * r2 where r1 is a prime. |
|
+0
2
|
|
| 1, 2, 2, 4, 3, 6, 3, 4, 5, 10, 4, 12, 7, 6, 4, 16, 5, 18, 6, 8, 11, 22, 5, 8, 13, 6, 8, 28, 7, 30, 5, 12, 17, 10, 6, 36, 19, 14, 7, 40, 9, 42, 12, 8, 23, 46, 6, 12, 9, 18, 14, 52, 7, 14, 9, 20, 29, 58, 8, 60, 31, 10, 6, 16, 13, 66, 18, 24, 11, 70, 7, 72, 37, 10, 20, 16, 15, 78, 8, 8, 41
(list; graph; listen)
|
|
|
OFFSET
|
2,2
|
|
|
REFERENCES
|
H. S. Wilf, Algorithms and complexity, Internet Edition, Summer, 1994, p. 56.
|
|
LINKS
|
H. S. Wilf, Algorithms and complexity, Internet Edition, 1994, p. 56.
|
|
FORMULA
|
a(n) = sum ( a_i * (p_i - 1) ) where n = product ( p_i^a_i ) is the canonical factorization of n.
|
|
EXAMPLE
|
a(18) = 5 since 18 = 2*3^2, a(18) = 1*(2-1) + 2*(3-1) = 5.
|
|
CROSSREFS
|
Same as A087656 apart from offset.
Sequence in context: A058723 A076435 A156864 this_sequence A087656 A122811 A089173
Adjacent sequences: A059972 A059973 A059974 this_sequence A059976 A059977 A059978
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
YONG KONG (ykong(AT)curagen.com), Mar 05 2001
|
|
|
Search completed in 0.002 seconds
|
