A059975 For n > 1, a(n) is the least number of prime factors (counted with multiplicity) of any integer with n divisors; fully additive with a(p) = p-1.

0, 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

Offset: 1

Author

Yong Kong (ykong(AT)curagen.com), Mar 05 2001

Keywords

• nonn

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

Examples

			a(18) = 5 since 18 = 2*3^2, a(18) = 1*(2-1) + 2*(3-1) = 5.
		

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.

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.

Other completely additive sequences with primes p mapped to a function of p include: A001222 (with a(p)=1), A001414 (with a(p)=p), A276085 (with a(p)=p#/p), A341885 (with a(p)=p*(p+1)/2), A373149 (with a(p)=prevprime(p)), A373158 (with a(p)=p#).

Programs

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 *)

PARI

a(n) = {my(f = factor(n)); sum(i = 1, #f~, f[i, 2]*(f[i, 1] - 1));} \\ Amiram Eldar, Mar 27 2023

Formula

a(n) = Sum ( e_i * (p_i - 1) ) where n = Product ( p_i^e_i ) is the canonical factorization of n.

a(n) = min(A001222(x) : A000005(x)=n).

a(n) = row sums of A138618 - row products of A138618. - Mats Granvik, May 23 2013

a(n) = A001414(n) - A001222(n). - David James Sycamore, Jul 17 2019

a(n) = n - A341865(n). - Antti Karttunen, Jun 05 2024

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