# A problem about a sequence and prime factorization

A long time ago I solved the following theorem

Let $p_1,p_2,\ldots,p_k$ be distinct primes. Let $\{a_i\}^\infty_{i=1}$ be the increasing sequence of positive integers whose prime factorization contains only these primes (not necesarily all). Show that $\forall c>0\exists n\in \mathbb{N}:a_{n+1}-a_n>c$

Solution. Let $m$ be an integer such that $p^m_i>c$ for all $i=1,2,\ldots,k$. Let $a_n=(a_1a_2\ldots a_k)^m$. As $a_{n+1}>a_n$, there exist a prime $p_j$ such that $p_j^m|a_{n+1}$. Then $p^m|a_{n+1}-a_n$ from which $a_{n+1}-a_n>c$.

Then a friend told me that this stronger version is also true.

Let $p_1,p_2,\ldots,p_k$ be distinct primes. Let $\{a_i\}^\infty_{i=1}$ be the increasing sequence of positive integers whose prime factorization contains only these primes (not necesarily all). Show that $\forall c>0\exists n_c\in \mathbb{N}:n>n_c\implies a_{n+1}- a_n>c$

I've tried to solve it but I couldn't. I'm 90% sure that the stronger version is also true. I'm interested in elementary solutions but a complex one is also welcome.

-
add comment

## 2 Answers

This is a result of Thue. For much stronger information, see the 1973 paper "On integers with many small prime factors" (Tijdeman, Compositio Mathematica).

-
add comment

This is not quite an answer but possibly a push in the right direction. I remembered the following beautiful idea to show that the reciprocal sum of $a_i$ must be finite:

Recall by Euler's product formula that $\prod_{i=1}^\infty \left(1-\frac{1}{q_i}\right)^{-1}=1+1/2+1/3+\ldots=\infty$ where $q_i$ is the $i'th$ prime. Notice that for your problem you have just $p_1,\ldots,p_k$. Then,

$S:=\prod_{i=1}^k\left(1-\frac{1}{p_i}\right)^{-1}$ is the sum of the reciprocals of all numbers whose factors are $p_1,\ldots,p_k$. Notice that unlike the full Euler product, $S<\infty$. Then

$\sum_{i=1}^\infty \frac{1}{a_i}\leq \prod_{i=1}^k\left(1-\frac{1}{p_i}\right)^{-1} <\infty$

Hence the sum of reciprocals of $a_i$ converges. So by the ratio test, we must have that $\lim_{n\rightarrow\infty} \frac{a_{n}}{a_{n+1}}\leq 1$. In fact this result is inherently obvious since $a_n\leq a_{n+1}$ in the first place but, the point is thinking about it in terms of a sum may be useful.

Now, suppose there exists $c\geq 1$ with $a_{n+1}-a_n>c$ for all $n$. Then, rearranging this and using the fact that $a_n$ is strictly increasing gives

$1>\frac{a_n}{a_{n+1}}>1-\frac{c}{a_{n+1}}$

The problem is that we would like to conclude with a contradiction that $\lim_{n\rightarrow\infty} \frac{a_n}{a_{n+1}}>1$ but, we actually get $\lim_{n\rightarrow\infty} \frac{a_n}{a_{n+1}}=1$ and the equality at 1 gives us an indeterminate result from the ratio test. Perhaps someone more clever than me can show that $\lim_{n\rightarrow\infty} a_{n}/a_{n+1}<1$ which would imply the stronger result by taking the limit along a subsequence $n_i$ for which $a_{n_{i+1}}-a_{n_i}> c$. My initial hope was to try and show the sum must diverge if the limit is 1.

-
add comment