This site is supported by donations to The OEIS Foundation.

 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.