A013939 Partial sums of sequence A001221 (number of distinct primes dividing n).

0, 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 14, 15, 17, 19, 20, 21, 23, 24, 26, 28, 30, 31, 33, 34, 36, 37, 39, 40, 43, 44, 45, 47, 49, 51, 53, 54, 56, 58, 60, 61, 64, 65, 67, 69, 71, 72, 74, 75, 77, 79, 81, 82, 84, 86, 88, 90, 92, 93, 96, 97, 99, 101, 102, 104, 107, 108, 110, 112

Offset: 1

Author

N. J. A. Sloane, Henri Lifchitz

Keywords

• nonn
• easy
• nice

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
• Eric Weisstein's World of Mathematics, Distinct Prime Factors

Crossrefs

Cf. A005187, A006218, A011371, A013936.

Cf. A093614, A048865, A006218.

Cf. A027748, A000040, A082287.

Cf. A022559.

Cf. A077761.

Cf. A346617.

Cf. A001222, A048803.

Programs

Haskell

a013939 n = a013939_list !! (n-1)
a013939_list = scanl1 (+) $ map a001221 [1..]
-- Reinhard Zumkeller, Feb 16 2012

Magma

[(&+[Floor(n/NthPrime(k)): k in [1..n]]): n in [1..70]]; // G. C. Greubel, Nov 24 2018

Maple

A013939 := proc(n) option remember;  `if`(n = 1, 0, a(n) + iquo(n+1, ithprime(n+1))) end:
seq(A013939(i), i = 1..69);  # Peter Luschny, Jul 16 2011

Mathematica

a[n_] := Sum[Floor[n/Prime[k]], {k, 1, n}]; Table[a[n], {n, 1, 69}] (* Jean-François Alcover, Jun 11 2012, from 2nd formula *)
Accumulate[PrimeNu[Range[120]]] (* Harvey P. Dale, Jun 05 2015 *)

PARI

t=0;vector(99,n,t+=omega(n)) \\ Charles R Greathouse IV, Jan 11 2012

PARI

a(n)=my(s);forprime(p=2,n,s+=n\p);s \\ Charles R Greathouse IV, Jan 11 2012

PARI

a(n) = sum(k=1, sqrtint(n), k * (primepi(n\k) - primepi(n\(k+1)))) + sum(k=1, n\(sqrtint(n)+1), if(isprime(k), n\k, 0)); \\ Daniel Suteu, Nov 24 2018

Python

from sympy.ntheory import primefactors
print([sum(len(primefactors(k)) for k in range(1,n+1)) for n in range(1, 121)]) # Indranil Ghosh, Mar 19 2017

Python

from sympy import primerange
def A013939(n): return sum(n//p for p in primerange(n+1)) # Chai Wah Wu, Oct 06 2024

Sage

[sum(floor(n/nth_prime(k)) for k in (1..n)) for n in (1..70)] # G. C. Greubel, Nov 24 2018

Formula

a(n) = Sum_{k <= n} omega(k).

a(n) = Sum_{k = 1..n} floor( n/prime(k) ).

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

a(n) = A093614(n) - A048865(n); see also A006218.

A027748(a(A000040(n))+1) = A000040(n), A082287(a(n)+1) = n.

a(n) = Sum_{k=1..n} pi(floor(n/k)). - Vladeta Jovovic, Jun 18 2006

a(n) = n log log n + O(n). - Charles R Greathouse IV, Jan 11 2012

a(n) = n*(log log n + B) + o(n), where B = 0.261497... is the Mertens constant A077761. - Arkadiusz Wesolowski, Oct 18 2013

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

a(n) = Sum_{k=1..floor(sqrt(n))} k * (pi(floor(n/k)) - pi(floor(n/(k+1)))) + Sum_{p prime <= floor(n/(1+floor(sqrt(n))))} floor(n/p). - Daniel Suteu, Nov 24 2018

a(n) = Sum_{k>=1} k * A346617(n,k). - Alois P. Heinz, Aug 19 2021

a(n) = A001222(A048803(n+1)). - Flávio V. Fernandes, Jan 14 2025

Extensions

More terms from Henry Bottomley, Jul 03 2001