Return to Revisions

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.