login
Card{ k<=n, k such that all prime divisors of k are <= sqrt(k) }.
7

%I #39 Oct 06 2024 09:16:13

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

%T 12,12,12,12,13,13,13,13,14,14,14,14,14,15,15,15,16,17,18,18,18,18,19,

%U 19,20,20,20,20,21,21,21,22,23,23,23,23,23,23,24,24,25,25,25,26,26,26,26

%N Card{ k<=n, k such that all prime divisors of k are <= sqrt(k) }.

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

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

%H Harry J. Smith, <a href="/A064775/b064775.txt">Table of n, a(n) for n = 1..1000</a>

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

%F From _Ridouane Oudra_, Nov 07 2019: (Start)

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

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

%e 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.

%o (PARI) a(n)=n-sum(k=1,floor(sqrt(n)+10^-20),(k-1)*isprime(k))-sum(k=ceil(sqrt(n)+10^-20),n,floor(n/k)*isprime(k))

%o (PARI) { for (n=1, 1000, a=n - sum(k=1, floor(sqrt(n) + 10^-20), (k-1)*isprime(k)) - sum(k=ceil(sqrt(n) + 10^-20), n, floor(n/k)*isprime(k)); write("b064775.txt", n, " ", a) ) } \\ _Harry J. Smith_, Sep 24 2009

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

%o (Python)

%o from math import isqrt

%o from sympy import primepi

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

%Y Cf. A048098, A242493.

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

%K easy,nonn

%O 1,4

%A _Benoit Cloitre_, May 11 2002