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

%I #89 Oct 06 2024 09:15:56

%S 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,

%T 37,39,40,43,44,45,47,49,51,53,54,56,58,60,61,64,65,67,69,71,72,74,75,

%U 77,79,81,82,84,86,88,90,92,93,96,97,99,101,102,104,107,108,110,112

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

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

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

%H Charles R Greathouse IV, <a href="/A013939/b013939.txt">Table of n, a(n) for n = 1..10000</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DistinctPrimeFactors.html">Distinct Prime Factors</a>

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

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

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

%F a(n) = Sum_{k=1..n} pi(floor(n/k)). - _Vladeta Jovovic_, Jun 18 2006

%F a(n) = n log log n + O(n). - _Charles R Greathouse IV_, Jan 11 2012

%F a(n) = n*(log log n + B) + o(n), where B = 0.261497... is the Mertens constant A077761. - _Arkadiusz Wesolowski_, Oct 18 2013

%F G.f.: (1/(1 - x))*Sum_{k>=1} x^prime(k)/(1 - x^prime(k)). - _Ilya Gutkovskiy_, Jan 02 2017

%F 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

%F a(n) = Sum_{k>=1} k * A346617(n,k). - _Alois P. Heinz_, Aug 19 2021

%p A013939 := proc(n) option remember; `if`(n = 1, 0, a(n) + iquo(n+1, ithprime(n+1))) end:

%p seq(A013939(i), i = 1..69); # _Peter Luschny_, Jul 16 2011

%t 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 *)

%t Accumulate[PrimeNu[Range[120]] (* _Harvey P. Dale_, Jun 05 2015 *)

%o (PARI) t=0;vector(99,n,t+=omega(n)) \\ _Charles R Greathouse IV_, Jan 11 2012

%o (PARI) a(n)=my(s);forprime(p=2,n,s+=n\p);s \\ _Charles R Greathouse IV_, Jan 11 2012

%o (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

%o (Haskell)

%o a013939 n = a013939_list !! (n-1)

%o a013939_list = scanl1 (+) $ map a001221 [1..]

%o -- _Reinhard Zumkeller_, Feb 16 2012

%o (Python)

%o from sympy.ntheory import primefactors

%o print([sum(len(primefactors(k)) for k in range(1,n+1)) for n in range(1, 121)]) # _Indranil Ghosh_, Mar 19 2017

%o (Python)

%o from sympy import primerange

%o def A013939(n): return sum(n//p for p in primerange(n+1)) # _Chai Wah Wu_, Oct 06 2024

%o (Magma) [(&+[Floor(n/NthPrime(k)): k in [1..n]]): n in [1..70]]; // _G. C. Greubel_, Nov 24 2018

%o (Sage) [sum(floor(n/nth_prime(k)) for k in (1..n)) for n in (1..70)] # _G. C. Greubel_, Nov 24 2018

%Y Cf. A005187, A006218, A011371, A013936.

%Y Cf. A022559.

%Y Cf. A077761.

%Y Cf. A346617.

%K nonn,easy,nice

%O 1,3

%A _N. J. A. Sloane_, _Henri Lifchitz_

%E More terms from _Henry Bottomley_, Jul 03 2001