Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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<N: \forall p\text{ prime, s.t. }p|x \to p \in P(n) \}$. In other words, how to approximate how many numbers $<N$ have only primes from $P(n)$ in their factorization?

share|cite|improve this question
See which is very similar. – Charles Mar 22 '12 at 12:37

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 $<N$ with all prime factors $<n$ 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.

share|cite|improve this answer

ADDED Oops! I thought you wanted all prime divisors of $N$ to be $>n$, not $<n$, 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<q$, $p$ and $q > n$ and $pq<N$. 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$.

share|cite|improve this answer
Maybe I'm misreading, but didn't the original question ask about numbers with only small prime factors (so Dickman's $\rho$-function), as opposed to only large prime factors (where Buchstab's $\omega$-function appears)? – Greg Martin Mar 22 '12 at 17:15
You are right. I misread. Would you like to write up the Dickman's function explanation? – David Speyer Mar 22 '12 at 17:17
Maybe I can convince you to edit yours instead :) Thanks! – Greg Martin Mar 22 '12 at 17:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.