# Question about the number of primes greater than $3$ in a sequence of consecutive integers.

I recently noticed that for any $x > 16$, it follows that there are at least $2$ integers in the any sequence of 3 consecutive integers that are divisible by a prime greater than $3$.

For example, for $10,11,12$, we have $5|10$ and $11$. For $18,19,20$, we have $5|20$ and $19$. (Note: For the details on my reasoning, see below the line).

For any $n$, does it follow that there is a $y$ such that for any $x \ge y$, there are at least $n-1$ integers divisible by a prime greater than $3$ in the sequence $x, x+1, \cdots x+n-1$?

Here's my reasoning for any sequence of 3 consecutive integers greater than $9$ contain $2$ integers divisible by a prime greater than $3$:

Case 1: $6 | x$

$x+1$ is clearly divisible by a prime greater than $3$. Assume that no prime greater than $3$ divides $x$. We can assume that $x=3^u2$ and $3^u2+2 = 2^v$ where $v > 4$ and $u > 1$. Then, $2^{v-1} - 3^u = 1$ which is impossible by the proof of Catalan's Conjecture.

Case 2: $6 | (x+1)$

$x$ and $x+2$ are clearly divisible by a prime greater than $3$.

Case 3: $6 | (x+2)$

$x+1$ is clearly divisible by a prime greater than $3$. Assume that no prime greater than $3$ divides $x+2$. We can assume that $x+2=3^u2$ and $3^u-2 = 2^v$ where $v > 4$ and $u > 1$. Then, $3^u - 2^{v-1}=1$ which is impossible by the proof of Catalan's Conjecture.

Case 4: $3 | x$ and $2 | x+1$

$x+2$ is clearly divisible by a prime greater than $3$. Assume both $x$ and $x+1$ are not divisible by a prime greater than $3$. Then, $2^v - 3^u = 1$ where $v > 3$ and $u > 2$ but this is impossible by the proof of Catalan's Conjecture.

Case 5: $2 | x$ and $3 | x+1$

$x$ and $x+2$ cannot both be powers of $2$ so one must be divisible by a prime greater than $3$. Further, it is not possible that $x$ is a power of $2$ and $x+1$ is a power of $3$ since by the proof of Catalan's conjecture: $3^u - 2^v \ne 1$ where $u > 2$ and $v > 3$ It is also not possible that $x+2$ is a power of $2$ and $x+1$ is a power of $3$ since $2^m - 3^n \ne 1$ where $m > 3$ and $n > 2$.

Case 6: $2 | x+1$ and $3 | x+2$

$x$ is clearly divisible by a prime greater than $3$. It is not possible for both $x+1$ to be a power of $2$ and $x+2$ to be a power of $3$ since by the proof of Catalan's Conjecture $3^v - 2^u \ne 1$ where $v > 2$ and $u > 3$.

Edit: $x > 9$ is not correct since $18-16=2$ doesn't violate Catalan's conjecture. So, I've corrected it to $x > 16$. Thanks very much to J.B. King for pointing this out.

• For 16,17,18 what is the prime other than 17 as $16=2^4$ and $18=2*3^2$? Your first observation isn't correct. – JB King Mar 22 '14 at 1:58
• Very good point. I'll check my reasoning. Thanks very much! – Larry Freeman Mar 22 '14 at 2:02
• $x$ needs to be greater than $16$ otherwise the reasoning in Case 3 is not valid as you accurately point out. – Larry Freeman Mar 22 '14 at 2:07
• 24,25,26,27 would be a sequence of 4 Natural numbers that have only 2 with your property as 24 and 27 only have prime factorizations of 2s and 3s. – JB King Mar 22 '14 at 2:07
• your original observation is just the case of Catalan's conjecture restricted to powers of 2 and 3. I do not doubt that something can be wroked up for longer runs of consecutive numbers. – Will Jagy Mar 22 '14 at 2:07

I believe that I've worked out the answer for a sequence of $n$ consecutive integers: $x+1, x+2, \cdots, x+n$

We can assume at least one integer $x+c$ where $c \le n$ is not divisible by a prime greater than $3$ so that $x+c = 2^m3^n$ where $m,n \ge 0$

The question is under what circumstances will $2^m3^n \pm d = 2^u3^v$ where $u,v \ge 0$.

We know that either $2 | d$ or $3 | d$ so we just need to solve for three cases.

Case 1: $2\mid d$ and $3\nmid d$

We can assume $d>0$ and either $d=2^u3^v-2^w$ or $d=2^w - 2^u3^v$.

If $u > w$, then $\frac{d}{2^w} = 2^{u-w}3^v - 1$ and $\frac{d}{2^w}=1$ only if $v=0$ and $u-w=1$. So, it is not true if $d < 2^{u-1}$ or if $x > 2n$

If $w > u$, then $\frac{d}{2^u} = 3^v - 2^{w-u}$ or $\frac{d}{2^u} = 2^{w-u} - 3^v$. So, $\frac{d}{2^u} = 1$ only if $v=2$ and $w-u=3$ or $w-u=2$ and $v=1$ by the proof behind Catalan's Conjecture. So, it is not true if $d < \frac{x}{72}$ or if $x > 72n$ for the first condition or $d < \frac{x}{12}$ or if $x > 12n$ for the second condition.

If $w=u$, then $\frac{d}{2^w} = 3^v - 1$. If this is a power of $2$, then $3^v - \frac{d}{2^w} = 1$. So, that $v=2$ and $\frac{d}{2^w} = 8$ So, it is not true if $d < \frac{8x}{9}$ or $x > \frac{9}{8}n$

Case 2: $3\mid d$ and $2\nmid d$

We can assume $d>0$ and either $d=2^u3^v-3^w$ or $d=3^w - 2^u3^v$.

If $v > w$, then $\frac{d}{3^w} = 2^u3^{v-w} - 1$ and $\frac{d}{3^w}\ne1$ since $v-w>0$

If $w > v$, then $\frac{d}{3^v} = 3^{w-v} - 2^u$ or $\frac{d}{3^v} = 2^u - 3^{w-v}$. So, $\frac{d}{3^v} = 1$ only if $w-v=2$ and $u=3$ or $u=2$ and $w-v=1$ by the proof behind Catalan's Conjecture.

If $w=v$, then $\frac{d}{3^w} = 2^u - 1$. If this is a power of $3$, then $2^u - \frac{d}{3^w} = 1$. So, that $u=2$ and $\frac{d}{2^w} = 3$

Case 3: $6\mid d$

We can assume $d>0$ and $d=2^u3^v - 2^s3^t$ where $u,v > 1$ or $s,t > 1$

If $u = s$, then $\frac{d}{2^u} = 3^v - 3^t \ne 1$ or $\frac{d}{2^u} = 3^t - 3^v \ne 1$. So we can assume that $u \ne s$.

If $v=t$, then $\frac{d}{3^v} = 2^u - 2^s$ or $\frac{d}{3^v} - 2^s - 2^u$. In this case $\frac{d}{3^v} = 1$ only if $u=1$ and $s=0$ or $s=1$ and $u=0$.

If $u > s$ and $v > t$, then $\frac{d}{2^s3^t} = 2^{u-s}3^{v-t} - 1$ and $\frac{d}{2^s3^t} \ne 1$ since $v > t$.

If $s > u$ and $t > v$, then $\frac{d}{2^u3^v} = 2^{s-u}3^{t-v} -1$ and $\frac{d}{2^u3^v} \ne 1$ since $t > v$

If $u > s$ and $v < t$, then $\frac{d}{2^s3^v} = 2^{u-s} - 3^{t-v}$ or $\frac{d}{2^s3^v} = 3^{t-v} - 2^{u-s}$ so the only solutions are $u-s=2$ and $t-v=1$ or $t-v=2$ and $u-s=3$ by the proof of Catalan's Conjecture.

If $s > u$ and $t < v$, then $\frac{d}{2^u3^t} = 3^{v-t} - 2^{s-u}$ or $\frac{d}{2^u3^t} = 2^{s-u} - 3^{v-t}$ so the only solutions are $v-t=2$ and $s-u=3$ or $s-u=2$ and $v-t=1$.