OFFSET
1,3
COMMENTS
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.
This sequence with offset 1 and a(1) = 0 is completely additive with a(p^e) = e*(p-1) for prime p and e >= 0. - Werner Schulte, Feb 23 2019
REFERENCES
Herbert S. Wilf, Algorithms and complexity, Internet Edition, Summer, 1994, p. 56.
LINKS
Antti Karttunen, Table of n, a(n) for n = 1..16384 (terms 2..1000 from Vincenzo Librandi, terms 1001..10000 from Amiram Eldar)
K. V. Lever, Problem 89-11: The complexity of the standard form of an integer, SIAM Rev. 31 (3) (1989) 493-498.
Herbert S. Wilf, Algorithms and complexity, Internet Edition, 1994, p. 56.
FORMULA
a(n) = Sum ( e_i * (p_i - 1) ) where n = Product ( p_i^e_i ) is the canonical factorization of n.
a(n) = n - A341865(n). - Antti Karttunen, Jun 05 2024
EXAMPLE
a(18) = 5 since 18 = 2*3^2, a(18) = 1*(2-1) + 2*(3-1) = 5.
MAPLE
A059975 := proc(n)
local a, pf, p, e ;
a := 0 ;
for pf in ifactors(n)[2] do
p := op(1, pf) ;
e := op(2, pf) ;
a := a+e*(p-1) ;
end do:
a ;
end proc: # R. J. Mathar, Oct 17 2011
MATHEMATICA
Table[Total[(First /@ FactorInteger[n] - 1) Last /@ FactorInteger[n]], {n, 1, 100}] (* Danny Marmer, Nov 13 2014 *)
f[p_, e_] := e*(p - 1); a[n_] := Plus @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Mar 27 2023 *)
PROG
(PARI) a(n) = {my(f = factor(n)); sum(i = 1, #f~, f[i, 2]*(f[i, 1] - 1)); } \\ Amiram Eldar, Mar 27 2023
CROSSREFS
Essentially same as A087656 apart from offset.
Cf. A000005, A138618, A309155, A309239, A327250, A341865, A373368 [= gcd(n, a(n))], A373369 [= gcd(A001414(n), a(n))].
Cf. A003159 (positions of even terms), A096268 (with offset 1, parity of terms), A373385 (positions of multiples of 3).
Leftmost column of irregular table A355029.
KEYWORD
nonn
AUTHOR
Yong Kong (ykong(AT)curagen.com), Mar 05 2001
EXTENSIONS
Definition revised by Hugo van der Sanden, May 21 2010
Term a(1)=0 prepended and Werner Schulte's comment adopted as an alternative definition - Antti Karttunen, Jun 05 2024
STATUS
approved