4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – JB King Mar 22 '14 at 1:58
  • $\begingroup$ Very good point. I'll check my reasoning. Thanks very much! $\endgroup$ – Larry Freeman Mar 22 '14 at 2:02
  • $\begingroup$ $x$ needs to be greater than $16$ otherwise the reasoning in Case 3 is not valid as you accurately point out. $\endgroup$ – Larry Freeman Mar 22 '14 at 2:07
  • $\begingroup$ 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. $\endgroup$ – JB King Mar 22 '14 at 2:07
  • $\begingroup$ 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. $\endgroup$ – Will Jagy Mar 22 '14 at 2:07
0
$\begingroup$

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$.

$\endgroup$

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.