8
$\begingroup$

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.

2 Answers 2

7

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

  • 1
    I knew that, some day, my investment in ultra-fast electrons would pay off....2011-07-08
7

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,

  • 0
    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.2011-07-08