4
$\begingroup$

Let $P(n)=\{p \leq n: p\text{ is prime} \}$. For given $N$ and $n$, what's a good approximation for $|S(N,n)|$, where $S(N,n)=\{x. In other words, how to approximate how many numbers $ have only primes from $P(n)$ in their factorization?

  • 0
    See http://math.stackexchange.com/q/1$2$2692/1778 which is very similar.2012-03-22

2 Answers 2

2

My previous answer was to a misreading of the question. Here is a similar aswer to the correct question. Once again, let $N=n^u$. The number of integers $ with all prime factors $ is approximately $\rho(u) N$, where $\rho(u)$ is Dickman's function.

For $0 \leq u \leq 1$, we clearly have $\rho(u)=1$.

For $1 \leq u \leq 2$, the number of integers which do NOT have the desired property is $\sum_{n \leq p \leq N} \lfloor N/p \rfloor$, where the variable $p$ runs over primes in the indicated range. One can justify turning the sum into an integral and discarding the greatest integer function: $\int_{p=n}^N \frac{N}{p} \frac{dp}{\log p} = \int_{x=1/u}^1 \frac{N}{N^x} \frac{(\log N) N^x dx}{x \log N} = N \int_{x=1/u}^1 \frac{dx}{x} = N \log u.$ In the first equality, we set $p =N^x$.

So the number of integers which do have the desired property is roughly $N - N \log u$, and $\rho(u) = 1-\log u$.

For $u$ in higher ranges, one has to worry about double counting, plus the integrals very quickly become undoable. The Wikipedia page is pretty good, so I'll stop here.

1

ADDED Oops! I thought you wanted all prime divisors of $N$ to be $>n$, not $, and that is what the answer below addresses. For your question, there is a similar answer involving Dickman's function, which I have now added as a separate answer.

Fix a constant $u >1 $ and let $N = n^u$. As $n \to \infty$, we have $|S(N,n)| \sim \omega(u) \frac{N}{\log n}.$ where $\omega$ is Buchstab's function. Buchstab's function is piecewise smooth, with singularities at the integers. I'll work out some special values of $u$ below:


If $1< u < 2$, then $|S(N,n)|$ is the number of primes between $N$ and $n$, so $\pi(N) - \pi(n)$. The first term is much larger than the second, so $|S(N,n)| \sim \pi(N) \sim \frac{N}{\log N} = \frac{1}{u} \frac{N}{\log n}.$ So $\omega(u)=1/u$ for $1 < u <2$.

If $2 < u < 3$, then $S(N,n)$ has two kinds of elements in it: Primes between $N$ and $n$, and products $pq$ of two primes with $p, $p$ and $q > n$ and $pq. Note that $p$ is necessarily $\leq N^{1/2}$. So $|S(N,n)| =\pi(N)- \pi(n) + \sum_{p \ \mathrm{prime}, n < p < N^{1/2}} \left( \pi(N/p) - \pi(p) \right).$ Again, the second $\pi$ term in each expression is negligible. Using the prime number theorem and being non-rigorous, we expect $|S(N,n)| \approx \frac{N}{\log N} + \int_{p=n}^{N^{1/2}} \frac{N/p}{\log (N/p)} \frac{dp}{\log p}.$ Put $p = N^x$, the integral is $\int_{1/u}^{1/2} \frac{N^{1-x}}{(1-x) \log N} \frac{\log N \cdot N^x dx}{x \log N} = \int_{1/u}^{1/2} \frac{N dx}{x (1-x) \log N}$ $=\frac{N}{\log N} \log(u-1) = \frac{\log(u-1)}{u} \frac{N}{\log n}.$ So $\omega(u) = 1/u + \log(u-1)/u$ for $2 < u <3$ (if I didn't screw up the integral).

For $3< u < 4$, a similar analysis gives an integral which can't be done in closed form, and for $u>4$, you wind up with integrals of those integrals which can't be done in closed form. But this should give you the idea.

When $u$ is very large, we have $|S(N,n)| \approx N \prod_{p < n} (1-1/p) \sim N \cdot e^{- \gamma}/\log n$ by Merten's theorem. So $\omega(u) \to e^{- \gamma}$ as $u \to \infty$.

  • 0
    Maybe I can convince you to edit yours instead :) Thanks!2012-03-22