Probability, that a random number has no "small" prime factors

Question

• What is the probability, that a random number $N$ with $k$ digits has no prime factor with at most $l$ digits ?

I came across the formula $\frac{e^{-\gamma}}{log(p)}$ , giving the approximate probability that a very large number (much larger than $p$) has no prime factor below $p$, if $p$ itself is "large". But neither do I know how the author came to this formula, nor do I know how accurate this formula is.

• How good is the approximation, if the probability that a $100$ digit-number has no prime factor below $10^{30}$ has to be calculated ?

A $100$-digit number starting with a $1$ has much higher probability that it is a product of two distinct $50$-digit primes than a $100$-digit number starting with a $9$.

• Is there a formula accurate enough to approve this fact ?

The problem, I am struggling with, is :

If $N$ is a random number in the range $[42^{61}-10^{12},42^{61}+10^{12}]$, which has no prime factor below $10^{30}$, is composite and no prime power, what is the probability that $N$ is the product of two distinct $50$-didit primes ?

Answer 1

This is a problem investigated by De Bruijn in 1951. Here is the reference:

N. G. de Bruijn, The asymptotic behaviour of a function occurring in the theory of primes, J. Indian Math. Soc. (N.S.) 15 (1951), 25–32. MR 0043838 (13,326f)

Note: This information was found by doing a Google search for "small prime factors". The information here was found in this paper:

D Hensley The number of positive integers ≦ x and free of prime divisors > y J. Number Theory, 21 (1985), pp. 286–298 which is at

http://ac.els-cdn.com/0022314X85900575/1-s2.0-0022314X85900575-main.pdf?_tid=efecc0ec-1227-11e5-a313-00000aab0f26&acdnat=1434240024_1e2f77b3b9cd73d1f7fae0e9801ed017

That paper was found as a reference in this paper, which was found by the search: "On the number of positive integers ≦ x and free of prime factors > y" by Adolf Hildebrand at http://www.sciencedirect.com/science/article/pii/0022314X86900132

The definition:

$\Psi(x, y)$ is the number of positive integers $\le x$ with all prime factors $\le y$.

Let $u = \frac{\log x}{\log y}$.

De Bruijn proved that, for small $u$, $\Psi(x, y) \approx x \rho(u) $ where $\rho(u) = 1$ for $0 \le \rho \le 1$ and $u \rho'(u) =-\rho(u-1) $ for $u > 1$. He showed that this is true for $u \le (\log x)^{3/8-\epsilon} $. According to this paper, this has been shown for $u \le (\log x)^{1-\epsilon} $.

De Bruijn also showed this lower bound valid for all $x$ and $y$: $\Psi(x, y) \ge \binom{\pi(y)+[u]}{[u]} $.

The rest is up to you.

Another hint: Look up "smooth number".

Here are all the references in Hensley's paper:

1. W. E. BRIGGS AND S. CHOWLA, On the number of positive integers
2. A. A. BUCHSTAB, On those numbers in an arithmetic progression all prime factors of which are small in order of magnitude, Dokl. Akad. Nuuk. SSR (N.S/ 67 (1949), 5-8.
3. E. R. CANFIELD, The asymptotic behavior of the Dickman-De Bruijn function, Proc. 13th Southeastern conference on combinatorics, graph theory, and computing (Boca Raton, Fla. 1982).
4. E. R. CANFIELD, P. ERDOS, AND C. POMERANCE. On a problem of Oppenheim concerning “Factorisatio Numerorum,” J. Number Theory 17 (1983), 1-28.
5. N. G. DE BRUIJN, I. On the number of positive integers < x and free of prime factors >J, Ned. Akad. Wetensch. Proc. Ser. A 54 (1951). 5MO. II. Ned. Akad. Wetensch. Proc. Ser. A 69 (1966), 239-247.
6. N. G. DE BRUIJN, The asymptotic behavior of a function occurring in the theory of primes, J. Indian Math. Sot. (N.S) 15 (1951), 25-32.
7. H. M. EDWARDS, “Riemann’s Zeta Function,” Chap. 5, Acadamic Press, New York, 1974.
8. A. S. FAINLEIB, On the estimation from below of the number of numbers with small prime factors, Dokl. Akad. Nauk Cl=. SSR 7 (1973), 3-5.
9. W. FELLER, “An Introduction to Probability Theory and Its Applications, Vol. II, Wiley, New York, 1960.
10. H. MAIER, On integers free of large prime divisors, unpublished manuscript.
11. K. K. NORTON, “Numbers with Small Prime Factors, and the Least kth Power Nonresidue,” Mem. Amer. Math. Sot., No. 106, Providence, RI., 1971.
12. V. RAMASWAMI, The number of positive integers less than x and free of prime divisors >x, and a problem of S. S. Pillai, Duke Mafh. J. 16 (1949). 99-109.
13. A. I. VINOGRADOV, On numbers with small prime divisors, Dokl. Akad. Nuuk. SSR (N.S.) 109 (1956), 683486.
14. A. WALFISZ, “Weyl’sche Exponentialsummen in der neuren Zahlentheorie,” EB Deutsen Verlag der Wissenchaften, Berlin, 1963.