A064775 Number of positive integers k <= n such that all prime divisors of k are <= sqrt(k).

1, 1, 1, 2, 2, 2, 2, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 7, 7, 7, 7, 7, 7, 8, 9, 9, 10, 10, 10, 11, 11, 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 14, 15, 15, 15, 16, 17, 18, 18, 18, 18, 19, 19, 20, 20, 20, 20, 21, 21, 21, 22, 23, 23, 23, 23, 23, 23, 24, 24, 25, 25, 25, 26, 26, 26, 26

Offset

1,4

Comments

A048098(n) is the n-th number k such that all prime divisors of k are <= sqrt(k).

References

D. P. Parent, Exercices de théorie des nombres, Les grands classiques, Gauthier-Villars, Edition Jacques Gabay, p. 17.

Links

Harry J. Smith, Table of n, a(n) for n = 1..1000

Formula

a(n) = n - (Sum_{p<=sqrt(n)} (p-1)) - Sum_{sqrt(n)<p<=n} floor(n/p). a(n) is the largest k such that A048098(k) <= n. Asymptotically: a(n) = (1-log(2))*n + O(n/log(n)).

From Ridouane Oudra, Nov 07 2019: (Start)

a(n) = n - Sum_{i=1..floor(sqrt(n))} (pi(floor(n/i)) - pi(i)).

a(n) = n - A242493(n). (End)

Example

Below 28, only k=27,25,24,18,16,12,9,8,4,1 have all their prime divisors less than or equal to sqrt(k), hence a(28)=10. To obtain from A048098(n): A048098(10) = 27 <= 28 < A048098(11)=30, hence a(28)=10.

Prog

(PARI) a(n)=n-sum(k=1, sqrtint(n), (k-1)*isprime(k)) - sum(k=sqrtint(n)+1, n, floor(n/k)*isprime(k))
(Magma) [1] cat [#[k:k in [1..n]|forall{p:p in PrimeDivisors(k)| p le Sqrt(k)}]: n in [2..80]]; // Marius A. Burtea, Nov 08 2019
(Python)
from math import isqrt
from sympy import primepi
def A064775(n): return int(n+sum(primepi(i)-primepi(n//i) for i in range(1, isqrt(n)+1))) # Chai Wah Wu, Oct 05 2024

Crossrefs

Cf. A048098, A242493.

The following are all different versions of sqrt(n)-smooth numbers: A048098, A063539, A064775, A295084, A333535, A333536.

Sequence in context: A025779 A085003 A119026 * A260731 A194239 A064475

Adjacent sequences: A064772 A064773 A064774 * A064776 A064777 A064778

Keyword

easy,nonn

Author

Benoit Cloitre, May 11 2002

Status

approved