login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A059975 a(n) is the least number of prime factors (counted with multiplicity) of any integer with n divisors. 3
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; refs; listen; history; text; internal format)
OFFSET

2,2

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.

REFERENCES

H. S. Wilf, Algorithms and complexity, Internet Edition, Summer, 1994, p. 56.

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 2..1000

K. V. Lever, Problem 89-11: The complexity of the standard form of an integer, SIAM Rev. 31 (3) (1989) 493-498

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.

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

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

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, 2, 100}] (* Danny Marmer, Nov 13 2014 - adapted to the offset by Vincenzo Librandi, Nov 13 2014 *)

CROSSREFS

Cf. A001222, A000005.

Same as A087656 apart from offset.

Sequence in context: A076435 A257010 A156864 * A087656 A122811 A089173

Adjacent sequences:  A059972 A059973 A059974 * A059976 A059977 A059978

KEYWORD

nonn

AUTHOR

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

EXTENSIONS

Definition revised by Hugo van der Sanden, May 21 2010

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 21 05:01 EST 2017. Contains 294988 sequences.