A022559 Sum of exponents in prime-power factorization of n!.

0, 0, 1, 2, 4, 5, 7, 8, 11, 13, 15, 16, 19, 20, 22, 24, 28, 29, 32, 33, 36, 38, 40, 41, 45, 47, 49, 52, 55, 56, 59, 60, 65, 67, 69, 71, 75, 76, 78, 80, 84, 85, 88, 89, 92, 95, 97, 98, 103, 105, 108, 110, 113, 114, 118, 120, 124, 126, 128, 129, 133, 134, 136, 139

Offset: 0

Author

Karen E. Wandel (kw29(AT)evansville.edu)

Keywords

• nonn
• nice

Comments

Partial sums of Omega(n) (A001222). - N. J. A. Sloane, Feb 06 2022

Examples

			For n=5, 5! = 120 = 2^3*3^1*5^1 so a(5) = 3+1+1 = 5. - _N. J. A. Sloane_, May 26 2018
		

Links

• Daniel Forgues, Table of n, a(n) for n = 0..100000
• Mehdi Hassani, On the decomposition of n! into primes, arXiv:math/0606316 [math.NT], 2006-2007.
• Keith Matthews, Computing the prime-power factorization of n!
• Daniel Suteu, Perl program

Crossrefs

Cf. A001222, A013939, A046660, A144494, A115627, A238002, A069513.

Programs

Haskell

a022559 n = a022559_list !! n
a022559_list = scanl (+) 0 $ map a001222 [1..]
-- Reinhard Zumkeller, Feb 16 2012

Maple

with(numtheory):with(combinat):a:=proc(n) if n=0 then 0 else bigomega(numbperm(n)) fi end: seq(a(n), n=0..63); # Zerinvary Lajos, Apr 11 2008
# Alternative:
ListTools:-PartialSums(map(numtheory:-bigomega, [$0..200])); # Robert Israel, Dec 21 2018

Mathematica

Array[Plus@@Last/@FactorInteger[ #! ] &, 5!, 0] (* Vladimir Joseph Stephan Orlovsky, Nov 10 2009 *)
f[n_] := If[n <= 1, 0, Total[FactorInteger[n]][[2]]]; Accumulate[Array[f, 100, 0]] (* T. D. Noe, Apr 11 2011 *)
Table[PrimeOmega[n!], {n, 0, 70}] (* Jean-François Alcover, Jun 08 2013 *)
Join[{0}, Accumulate[PrimeOmega[Range[70]]]] (* Harvey P. Dale, Jul 23 2013 *)

PARI

a(n)=bigomega(n!)

PARI

first(n)={my(k=0); vector(n, i, k+=bigomega(i))}

PARI

a(n) = sum(k=1, primepi(n), (n - sumdigits(n, prime(k))) / (prime(k)-1)); \\ Daniel Suteu, Apr 18 2018

PARI

a(n) = my(res = 0); forprime(p = 2, n, cn = n; while(cn > 0, res += (cn \= p))); res \\ David A. Corneth, Apr 27 2018

Python

from sympy import factorint as pf
def aupton(nn):
    alst = [0]
    for n in range(1, nn+1): alst.append(alst[-1] + sum(pf(n).values()))
    return alst
print(aupton(63)) # Michael S. Branicky, Aug 01 2021

Formula

a(n) = a(n-1) + A001222(n).

A027746(a(A000040(n))+1) = A000040(n). A082288(a(n)+1) = n.

A001221(n!) = omega(n!) = pi(n) = A000720(n).

a(n) = Sum_{i = 1..n} A001222(i). - Jonathan Vos Post, Feb 10 2010

a(n) = n log log n + B_2 * n + o(n), with B_2 = A083342. - Charles R Greathouse IV, Jan 11 2012

a(n) = A210241(n) - n for n > 0. - Reinhard Zumkeller, Mar 23 2012

G.f.: (1/(1 - x))*Sum_{p prime, k>=1} x^(p^k)/(1 - x^(p^k)). - Ilya Gutkovskiy, Mar 15 2017

a(n) = Sum_{k=1..floor(sqrt(n))} k * (A025528(floor(n/k)) - A025528(floor(n/(k+1)))) + Sum_{k=1..floor(n/(floor(sqrt(n))+1))} floor(n/k) * A069513(k). - Daniel Suteu, Dec 21 2018

a(n) = Sum_{prime p<=n} Sum_{k=1..floor(log_p(n))} floor(n/p^k). - Ridouane Oudra, Nov 04 2022

a(n) = Sum_{k=1..n} A069513(k)*floor(n/k). - Ridouane Oudra, Oct 04 2024

Extensions

Typo corrected by Daniel Forgues, Nov 16 2009