|
%I #85 Sep 08 2022 08:44:38
%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 (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
|
