cp's OEIS Frontend

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

%I A022559 #100 Oct 04 2024 14:20:49
%S A022559 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,
%T A022559 47,49,52,55,56,59,60,65,67,69,71,75,76,78,80,84,85,88,89,92,95,97,98,
%U A022559 103,105,108,110,113,114,118,120,124,126,128,129,133,134,136,139
%N A022559 Sum of exponents in prime-power factorization of n!.
%C A022559 Partial sums of Omega(n) (A001222). - _N. J. A. Sloane_, Feb 06 2022
%H A022559 Daniel Forgues, <a href="/A022559/b022559.txt">Table of n, a(n) for n = 0..100000</a>
%H A022559 Mehdi Hassani, <a href="http://arxiv.org/abs/math/0606316">On the decomposition of n! into primes</a>, arXiv:math/0606316 [math.NT], 2006-2007.
%H A022559 Keith Matthews, <a href="http://www.numbertheory.org/php/factorial.html">Computing the prime-power factorization of n!</a>
%H A022559 Daniel Suteu, <a href="/A022559/a022559.pl.txt">Perl program</a>
%F A022559 a(n) = a(n-1) + A001222(n).
%F A022559 A027746(a(A000040(n))+1) = A000040(n). A082288(a(n)+1) = n.
%F A022559 A001221(n!) = omega(n!) = pi(n) = A000720(n).
%F A022559 a(n) = Sum_{i = 1..n} A001222(i). - _Jonathan Vos Post_, Feb 10 2010
%F A022559 a(n) = n log log n + B_2 * n + o(n), with B_2 = A083342. - _Charles R Greathouse IV_, Jan 11 2012
%F A022559 a(n) = A210241(n) - n for n > 0. - _Reinhard Zumkeller_, Mar 23 2012
%F A022559 G.f.: (1/(1 - x))*Sum_{p prime, k>=1} x^(p^k)/(1 - x^(p^k)). - _Ilya Gutkovskiy_, Mar 15 2017
%F A022559 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
%F A022559 a(n) = Sum_{prime p<=n} Sum_{k=1..floor(log_p(n))} floor(n/p^k). - _Ridouane Oudra_, Nov 04 2022
%F A022559 a(n) = Sum_{k=1..n} A069513(k)*floor(n/k). - _Ridouane Oudra_, Oct 04 2024
%e A022559 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
%p A022559 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
%p A022559 # Alternative:
%p A022559 ListTools:-PartialSums(map(numtheory:-bigomega, [$0..200])); # _Robert Israel_, Dec 21 2018
%t A022559 Array[Plus@@Last/@FactorInteger[ #! ] &, 5!, 0] (* _Vladimir Joseph Stephan Orlovsky_, Nov 10 2009 *)
%t A022559 f[n_] := If[n <= 1, 0, Total[FactorInteger[n]][[2]]]; Accumulate[Array[f, 100, 0]] (* _T. D. Noe_, Apr 11 2011 *)
%t A022559 Table[PrimeOmega[n!], {n, 0, 70}] (* _Jean-François Alcover_, Jun 08 2013 *)
%t A022559 Join[{0}, Accumulate[PrimeOmega[Range[70]]]] (* _Harvey P. Dale_, Jul 23 2013 *)
%o A022559 (PARI) a(n)=bigomega(n!)
%o A022559 (PARI) first(n)={my(k=0); vector(n, i, k+=bigomega(i))}
%o A022559 (PARI) a(n) = sum(k=1, primepi(n), (n - sumdigits(n, prime(k))) / (prime(k)-1)); \\ _Daniel Suteu_, Apr 18 2018
%o A022559 (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
%o A022559 (Haskell)
%o A022559 a022559 n = a022559_list !! n
%o A022559 a022559_list = scanl (+) 0 $ map a001222 [1..]
%o A022559 -- _Reinhard Zumkeller_, Feb 16 2012
%o A022559 (Python)
%o A022559 from sympy import factorint as pf
%o A022559 def aupton(nn):
%o A022559     alst = [0]
%o A022559     for n in range(1, nn+1): alst.append(alst[-1] + sum(pf(n).values()))
%o A022559     return alst
%o A022559 print(aupton(63)) # _Michael S. Branicky_, Aug 01 2021
%Y A022559 Cf. A001222, A013939, A046660, A144494, A115627, A238002, A069513.
%K A022559 nonn,nice
%O A022559 0,4
%A A022559 Karen E. Wandel (kw29(AT)evansville.edu)
%E A022559 Typo corrected by _Daniel Forgues_, Nov 16 2009