login
A242493
a(n) is the number of not-sqrt-smooth numbers ("jagged" numbers) not exceeding n. This is the counting function of A064052.
3
0, 1, 2, 2, 3, 4, 5, 5, 5, 6, 7, 7, 8, 9, 10, 10, 11, 11, 12, 13, 14, 15, 16, 16, 16, 17, 17, 18, 19, 19, 20, 20, 21, 22, 23, 23, 24, 25, 26, 26, 27, 28, 29, 30, 30, 31, 32, 32, 32, 32, 33, 34, 35, 35, 36, 36, 37, 38, 39, 39, 40, 41, 41, 41, 42, 43, 44, 45
OFFSET
1,3
COMMENTS
This sequence is different from shifted A072490, after 22 terms.
REFERENCES
Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, chapter 2.21, p. 166.
Daniel H. Greene and Donald E. Knuth, Mathematics for the Analysis of Algorithms, 3rd ed., Birkhäuser, 1990, pp. 95-98.
FORMULA
From Ridouane Oudra, Nov 07 2019: (Start)
a(n) = Sum_{i=1..floor(sqrt(n))} (pi(floor(n/i)) - pi(i)).
a(n) = Sum_{p<=sqrt(n)} (p-1) + Sum_{sqrt(n)<p<=n} floor(n/p), where p is prime.
a(n) = n - A064775(n). (End)
a(n) ~ log(2)*n - A153810 * n/log(n) - A242610 * n/log(n)^2 + O(n/log(n)^3) (Greene and Knuth, 1990). - Amiram Eldar, Apr 15 2021
MATHEMATICA
jaggedQ[n_] := jaggedQ[n] = (f = FactorInteger[n][[All, 1]]; s = Sqrt[n]; Count[f, p_ /; p > s] > 0); a[n_] := ( For[ cnt = 0; j = 2, j <= n, j++, If[jaggedQ[j], cnt++]]; cnt); Table[a[n], {n, 1, 100}]
PROG
(Python)
from math import isqrt
from sympy import primepi
def A242493(n): return sum(primepi(n//i)-primepi(i) for i in range(1, isqrt(n)+1)) # Chai Wah Wu, Sep 01 2024
CROSSREFS
KEYWORD
nonn
AUTHOR
STATUS
approved