MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I apologize if this is a naive question about greatest prime factors (gpf). I was thinking about the sequence of integers where $\mathrm{gpf}(x) \le p$ where $p$ is any prime.

Clearly, as $x$ increases, the distance $d$ between an integer where $\mathrm{gpf}(x) \le p$ and $\mathrm{gpf}(x+d) \le p$ increases at a seemingly every increasing rate.

For all primes $p$, does there exist an integer $C$ where if $x \ge C$, then there is at most one integer in the sequence $x+1, x+2, \dots, x+p$ has $\mathrm{gpf}(x) \le p$

For example, if $p=2$, $C = 2$ since for any $x \ge 2$, either $x$ or $x+1, \mathrm{gpf}(x) > 2$

share|cite|improve this question
Thanks very much! Could you provide more details on why there are only finitely many such equations for each p? I suspected that this was correct but I was having trouble identifying the reasoning. Thanks! -Larry – Larry Freeman Sep 9 '12 at 17:34
Actually, I think that you answered my question with your mention of the Thue equation. I'll read up on the Thue equation to better understand the details! :-) – Larry Freeman Sep 9 '12 at 17:35
As suggested above, there is a theorem by Stormer on consecutive smooth numbers which supports your conjecture. I personally believe that C is O(nlogn). My memory says the equations are quadratic, though, and not cubic. Gerhard "Ask Me About System Design" Paseman, 2012.09.09 – Gerhard Paseman Sep 9 '12 at 18:22
Also, I think C=9 for p=3 and C=9801 for p=11. Doubtless OEIS has entries for you. Gerhard "Ask Me About System Design" Paseman, 2012.09.09 – Gerhard Paseman Sep 9 '12 at 18:37
Assuming the ABC-conjecture, $C$ can be taken as small as $c_{\epsilon} ( p e^p )^{1 + \epsilon} $ for any $\epsilon >0$. – js21 Sep 10 '12 at 8:27
up vote 3 down vote accepted

This is a summary of Gerhard Paseman's comment.

Suppose that $A$ and $B$ are two numbers with $A-B = c$ small such that $A$ and $B$ are only divisible by prime numbers less than or equal to $p$. Then one can write

$$A = a x^3, \qquad B = b y^3,$$

where all the prime factors of $a$ and $b$ are less than or equal to $p$, and all the exponents of each prime number is at most $2$ (the higher factors get absorbed into the cube). Note that if $p$ is the $n$th prime number, then there are $3^n$ possible values of $a$ and $b$. The answer to your problem will be positive provided that one can show that each of the ($3^{2n}$) equations

$$a x^3 - b y^3 = c$$

Has only finitely many solutions. Yet a theorem of Thue (1908) guarantees that if $f(x,y)$ is irreducible of degree $\ge 3$, then $f(x,y) = c$ has only finitely many integral solutions.

This leaves the reducible cases corresponding to the ratio $[a:b]$ being a perfect cube. Yet these are trivial; after absorbing the coefficients and multiplying through, one is left with an equation

$$X^3 - Y^3 = C$$

to solve in integers $X$ and $Y$. Yet this also has finitely many solutions for a trivial reason - the consecutive cubes become further apart.

Thue's results are actually effective, one can also prove this result by various other means, like Baker's method.

This problem is actually the baby case of the $S$-unit equation. In particular, it ultimately boils down to solving the equation

$$A + B = C$$

where $A$, $B$, and $C$ have a fixed set of prime factors dividing $S$ (Take $S$ to be the product of primes less than or equal to the maximum of $p$ and the range corresponding to $c$ in the Thue equations above). In other words, one is looking for a solution in units to the equation $A+B=C$ in the ring $\mathbf{Z}[1/S]$. The methods above can be generalized to applied to similar problems where $\mathbf{Z}[1/S]$ is replaced by the $S$-units in a number field, and one can even increase the number of terms (providing that one is careful only considers primitive solutions, ruling out trivialities like $A-A+B-B=0$.)

share|cite|improve this answer
Thanks very much, Pauline! That really provides the additional details to help me understand Gerhard's explanation! :-) – Larry Freeman Sep 10 '12 at 13:34

I don't know how far Larry went in pursuing this problem, but this touches on a topic I've spent some time on, ie. Lehmer's method.

Let $S_j$ be the maximum $S$ for which the pair {$S, S+j$} is $p$-smooth, and let $S_m$ be the maximum of $\{S_1, S_2 \ldots S_p\}$. Also let k = $\pi(p)$, ie. the number of primes $\leq p$.

It follows then that the minimal $C$ for which the desired property holds is $C = S_m$.

Determining each $S_j$ is not so straight-forward, apart from the cases $j=1, 2$, which are a direct application of Lehmer's method, which provides for the enumeration of all smooth pairs of the form $\{S, S+1\}$, $\{S, S+2\}$, by solving roughly $2^k$ standard Pell equations, ie. $x^2 - Dy^2 = 1$, for $D$ ranging over all combinations of the $k$ primes $\leq p$. Both sets of pairs can be obtained with a single pass.

For $3 \leq j \leq p$, however, things are not so simple. Lehmer did not address these cases, and perhaps we can understand why. We can in fact extend Lehmer's method to identify smooth pairs $\{S, S+j\}$, but this requires solving $x^2 - Dy^2 = j^2$, again for all $2^k$ values of $D$.

The good news is that these equations can be solved from the $x^2 - Dy^2 = 1$ solutions, so that the number of continued fractions we have to compute is still the same. See John Robertson's article on the LMM method (Lagrange-Matthews-Mollin) at JPR_Pell.

Note that there can be multiple solution classes for any $j$.

The bad news is that Lehmer's main achievement, by which he is able to reduce the number of Pell equations from $3^k$ to $2^k$, is not applicable for $j \geq 3$. For $j = 1, 2$ he showed that any smooth pair that does not turn up as a fundamental solution $(x_1, y_1)$ will be found at some $(x_m, y_m)$ with $m \leq (p+1)/2$. This is because the $y_n$ values form a Lucas sequence, and so $y_1$ divides all $y_n$. Thus, if $y_1$ isn't smooth, neither will be any other $y_n$. And if $y_1$ is smooth, we only need check a limited number of $y_n$.

Sadly, the multiple solutions in any class of solutions to $x^2 - Dy^2 = N$, $(N=j^2)$, do not have these Lucasian properties. So we don't know how many $(x_n, y_n)$ to look at, and we can't assume that $y_1$ not being smooth means that $y_2$ isn't either.

We could of course revert to the original Störmer method, where we solve for $D$ being all possible combinations of the $k$ primes to the power $\{ 0, 1, 2 \}$, thus requiring roughly $3^k$ equations to be solved. That's very slow, but guarantees that smooth pairs occur only as fundamental solutions.

Alternately, it might well be that $S_1 > S_j$ always, in which case we would avoid all of these complications, solving only the standard equations $x^2 - Dy^2 = 1$. I have not yet done any investigation of this question, but I remember that generally $S_2 < S_1$, so this property can't be ruled out.

Finally, I would like to know if Larry looked into the method described above involving $X^3 - Y^3 = C$, and if so, how it works.

share|cite|improve this answer
Correction: $S_2 < S_1$ was only true if $gcd(S, S+2)=1$. Clearly any $S, S+1$ will correspond to smooth pairs $(kS, kS + k)$ for any $k$ you like, so there is no avoiding the complications (wrt the Lehmer method) described above. – Jim White Jan 11 '13 at 2:20
Ah, but then again, we might still get lucky, for perhaps our $S_m$ is in fact always $(pS_1, pS_1 + p). – Jim White Jan 11 '13 at 2:38
I meant $(pS_1, pS_1 + p)$. You can't edit comments! – Jim White Jan 11 '13 at 2:40
Hi Dr. Memory, My interest in primarily in understanding the context behind the Sylvester-Schur Theorem:… For example, I am especially interested in patterns like this: Cheers, -Larry – Larry Freeman Jan 11 '13 at 21:28
I'm kind of preoccupied with a couple of other questions, so I don't quite know what you mean by "patterns like A213523". This could just be attention-deficit on my part, but can you explain in more detail what you are looking for? – Jim White Jan 12 '13 at 3:12

I heard a great answer to this question based on the Thue equation.

I investigated the Thue equation and there was one point that was not clear to me. It seems to me that there are an infinite number of values that $a$ and $b$ can take. If there are an infinite number of combinations of finite solutions, then there is an infinite number of solutions. Right?

So, if I understand it, the Thue equation alone doesn't seem to work. I apologize if I am misunderstanding the classical result there.

Here's an argument that seems to work as far as I understand:

(1) For any prime $p$, there is a finite number of combinations of primes that are less than $p$.

(2) For any of these combinations there exists an integer $x$ such that if a combination is greater than $x$, then at least one of the primes that make up the combination are of a degree greater than $2$.

(3) Let $c$ be either the highest of the values $x$ from step (2) or $4p^{4}(3\prod_{p} p^{\frac{1}{2}})^3$ depending on which is higher.

(4) There is a finite number of ways that we can pair these different combinations so that we have an equation of the form $ax^3 - by^3 = c$ where $c < p$.

(5) If $a \ne b$ and $gcd(x,y)=1$, then using a result from Siegel, there is at most $1$ solution (see Theorem A in the link below).

(6) if $a = b$ and $a = c$, then using a result from Michael Bennett, there is at most $1$ solution. Here's the reference:

M. A. Bennett, Rational approximation to algebraic numbers of small height : the Diophantine equation $|ax^n-by^n|=1$}, J. Reine Angew. Math. 535 (2001), 1-49

(7) if $a = b$ and $a < c$, then the equation has a form such as:

$x^3 - y^3 = \frac{c}{a}$

This is a Thue Equation and we can conclude that there is a finite number of solutions.

(8) if $a \ne b$ and $gcd(x,y) > 1$, then it means that both combinations consist of the same prime so we have an equation of the form:

$x^m - x^n = c$

Then, as I understand it, we have a Thue equation so we can again assume that there is a finite number solutions.

I believe that covers all the possible cases.

Since, there are only a finite number of solutions, it follows that there exists an integer $c$ which is greater than all of these solutions and for all $x \ge c$, we have at most $1$ integer in the sequence where $gpc(x+i) \le p$.

Apologies for the length of this argument. I'm sure a professional mathematician such as user 631 would be able to state the argument more elegantly. :-)

share|cite|improve this answer
You might prefer Lehmer's rewrite of Stormer's result. Check out the Wikipedia entry on Stormer's Theorem. Gerhard "Ask Me About System Design" Paseman, 2012.09.09 – Gerhard Paseman Sep 10 '12 at 3:55
Clearly your notion of being insulted differs from my notion,and likely differs from commonly accepted notions as well. I think he showed respect by referring to you by number. If that offends you, he might resort to something more oblique. Were I in a situation similar to Larry's, I might insult you further. Gerhard "Honk Honk Back At You" Paseman, 2012.09.09 – Gerhard Paseman Sep 10 '12 at 4:23
Thanks! I just read the link. It looks great: I'll start reading up on Stormer's Theorem to better understand it! – Larry Freeman Sep 10 '12 at 4:27
Hi Harpo, I meant no insult. You changed your name two times today. I thought your answer was brilliant. I willl change the user 61 to Harpo Marx immediately. Apologies. -Larry – Larry Freeman Sep 10 '12 at 4:28
I will do as you ask. I will remove your name. I meant no insult. Apologies. I really appreciated your comment about the Thue Equation! That was exactly the guidance I was looking for. :-) – Larry Freeman Sep 10 '12 at 4:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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