I guess that the number of integers $x$ which satisfy the condition $x*p(x) \leq n$ is $O(n^{2/3})$ or $O(n^{3/4} / \ln n$), but I cannot prove it. I just write a program to count the number. The results are listed.
Note: $p(x)$ means the largest prime factor of $x$.
n the numbers
$10^5$ 1894
$10^6$ 9108
$10^7$ 44948
$10^8$ 228102
$\begingroup$
$\endgroup$
1
-
$\begingroup$ You might count the number of p-smooth numbers between n/q and n/p, where q is the smallest prime greater than the prime p. Gerhard "Or Try Integrating Dickman's Function" Paseman, 2018.02.01. $\endgroup$– Gerhard PasemanCommented Feb 2, 2018 at 5:22
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Quick observation. Choose $\alpha$ close to 1 and consider the number for which $x\leqslant n^{\alpha}=:N$, $p(x)\leqslant n^{1-\alpha}=N^{(1-\alpha)/\alpha}$. The number of such $x$ grows as $\rho(\frac\alpha{1-\alpha})N$, where $\rho$ is Dickman's function. It already implies that the number of $x$ satisfying $xp(x)\leqslant n$ grows faster than $n^{\alpha}$ for any $\alpha<1$.
answered Feb 2, 2018 at 6:23
-
$\begingroup$ Indeed, choosing $\alpha$ around $1-\sqrt{(\log\log n)/\log n}$ results (I believe) in the number of such $x\le n$ being at least something like $n\cdot \exp(-c\sqrt{\log n\log\log n})$. $\endgroup$ Commented Feb 2, 2018 at 10:08
-
$\begingroup$ @GregMartin well, it depends on Dickman's asymptotics for large (not fixed, but depending on $n$) values of $\alpha/(1-\alpha)$. Certainly this is well studied. $\endgroup$ Commented Feb 2, 2018 at 16:23