login
Number of numbers m <= n that have a prime divisor greater than sqrt(n) (i.e., A006530(m)>sqrt(n)).
3

%I #26 Oct 06 2024 09:16:17

%S 0,1,2,1,2,3,4,4,2,3,4,4,5,6,7,7,8,8,9,10,11,12,13,13,9,10,10,11,12,

%T 12,13,13,14,15,16,16,17,18,19,19,20,21,22,23,23,24,25,25,19,19,20,21,

%U 22,22,23,23,24,25,26,26,27,28,28,28,29,30,31,32,33,33,34,34,35,36,36,37,38

%N Number of numbers m <= n that have a prime divisor greater than sqrt(n) (i.e., A006530(m)>sqrt(n)).

%C Values of n that are squares of primes p^2 seem to reduce the value of a(p^2) from the value a(p^2 - 1). Example, a(24) = 13, a(25) = 9; a(120) = 70, a(121) = 60.

%C a(p^2) = a(p^2-1) - p + 1 if p is prime. If n is not the square of a prime, a(n) >= a(n-1).- _Robert Israel_, Aug 11 2014

%H Michael De Vlieger, <a href="/A241419/b241419.txt">Table of n, a(n) for n = 1..5000</a>

%H E. Naslund, <a href="http://www.emis.de/journals/INTEGERS/papers/n81/n81.Abstract.html">The Average Largest Prime Factor</a>, Integers, Vol. 13 (2013), A81. See "2. The Main Theorem."

%F a(n) = Sum_{prime p > sqrt(n)} floor(n/p). - _Max Alekseyev_, Nov 14 2017

%e a(12) = 4, because there are four values of m = {5, 7, 10, 11} that have prime divisors that exceed sqrt(12) = 3.464... These prime divisors are {5, 7, 5, 11} respectively.

%p N:= 1000: # to get a(1) to a(N)

%p MF:= map(m -> max(numtheory:-factorset(m))^2,<($1..N)>): MF[1]:= 0:

%p seq(nops(select(m -> MF[m]>n, [$1..n])),n=1..N); # _Robert Israel_, Aug 11 2014

%t a241419[n_Integer] :=

%t Module[{f},

%t f = Reap[For[m = 1, m <= n, m++,

%t If[Max[First[Transpose[FactorInteger[m]]]] > Sqrt[n], Sow[m],

%t False]]];

%t If[Length[f[[2]]] == 0, Length[f[[2]]], Length[f[[2, 1]]]]]; a241419[120]

%o (PARI) isok(i, n) = {my(f = factor(i)); my(sqrn = sqrt(n)); for (k=1, #f~, if ((p=f[k, 1]) && (p>sqrn) , return (1)););}

%o a(n) = sum(i=1, n, isok(i, n)); \\ _Michel Marcus_, Aug 11 2014

%o (PARI) A241419(n) = my(r=0); forprime(p=sqrtint(n)+1,n, r+=n\p); r; \\ _Max Alekseyev_, Nov 14 2017

%o (Python)

%o from math import isqrt

%o from sympy import primerange

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

%Y Cf. A013939, A295084.

%K nonn

%O 1,3

%A _Michael De Vlieger_, Aug 08 2014