If there are $m$ primes less than $x$ then I believe that there are at most $O(\log^m N)$ numbers less than $N$ all of whose prime factors are less than $x$. This should mean that the number of numbers where both $n$ and $n+1$ have all their prime factors less than $x$ is finite if we consider the tests for $n$ and $n+1$ to be independent random events, and that is optimistic as $n$ and $n+1$ cannot share a prime factor. I'd like to know, as a function of $m$ and the primes less than $x$ how many such numbers we "expect" to find in all of the natural numbers.

This came up while playing with this question.


Have a look at the discussion of Stormer's Theorem at http://en.wikipedia.org/wiki/Stormer's_theorem and elsewhere.

  • $\begingroup$ More than I could have wished for. Thanks. $\endgroup$ – deinst Jul 7 '11 at 23:55
  • $\begingroup$ @Gerry: +1, You beat me to it! I was 6 minutes too late! $\endgroup$ – Eric Naslund Jul 7 '11 at 23:58
  • 1
    $\begingroup$ I knew that, some day, my investment in ultra-fast electrons would pay off.... $\endgroup$ – Gerry Myerson Jul 8 '11 at 1:15

Your question is answered near the bottom. However, I think you will find the first part interesting as it is related.

The function $\psi(x,y)$

We let $\psi(x,y)$ denote the number of positive integers $\leq x$ such that all of their prime factors are $\leq y$. Something important is that we can understand $\psi(x,y)$ very well when $y$ is fixed and $x$ grows very large, and also when $y$ grows like some fractional power of $x$.

Above you claim that $\psi(x,y)\ll \log^{\pi(y)}(x)=\exp\left(\pi(y)\log \log x\right)$. While this is true, for large $y$ it is not very good and we can actually do much better. Assume that $x=y^u$. Then we have $$\psi(x,y)=x\rho(u)+O\left(\frac{x\log(u+1)}{\log y}\right)$$ where the error term is uniform for $$1\leq u\leq \exp\left (\log y)^{\frac{3}{5}-\epsilon}\right).$$ Here $\rho(u)$ refers to the Dickman De-Bruijn rho function. For a complete survey of results regarding $\psi(x,y)$ see Hildebrand and Tenenbaum's 1993 paper "Integers Without Large Prime Factors." It is also worth noting that uniformety in a larger range is equivalent to improving the error term in the prime number theorem. This is proven in Hildebrand 1982.

The number of $n$ and $n+1$ which are both smooth: For $y$ fixed, this problem is very well known, and is exactly the statement of Stormers Theorem. This theorem says that given $y$ fixed, there are only finitely many pairs of integers $n,n+1$ where both have prime factors smaller then $y$. In fact, Stormer gave a method of finding all such pairs based on Pell equations.

I am not sure what happens if we allow $y$ to go to infinity with $x$. I tried to work it out without success, but I think it is an interesting question to ask.

Hope that helps,

  • $\begingroup$ Thank you. I knew that my estimate was not good, it was enough to convince myself that there were probably only finitely many consecutive pairs. I never expected an effective algorithm to find pairs. $\endgroup$ – deinst Jul 8 '11 at 0:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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