Størmer's theorem

If one chooses a finite set ${\displaystyle P=\{p_{1},p_{2},\dots p_{k}\}}$ of prime numbers then the P-smooth numbers are defined as the set of integers

${\displaystyle \left\{p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{k}^{e_{k}}\mid e_{i}\in \{0,1,2,\ldots \}\right\}}$

that can be generated by products of numbers in P. Then Størmer's theorem states that, for every choice of P, there are only finitely many pairs of consecutive P-smooth numbers. Further, it gives a method of finding them all using Pell equations.

Størmer's original procedure involves solving a set of roughly 3^k Pell equations, in each one finding only the smallest solution. A simplified version of the procedure, due to D. H. Lehmer,[2] is described below; it solves fewer equations but finds more solutions in each equation.

Let P be the given set of primes, and define a number to be P-smooth if all its prime factors belong to P. Assume p₁ = 2; otherwise there could be no consecutive P-smooth numbers, because all P-smooth numbers would be odd. Lehmer's method involves solving the Pell equation

${\displaystyle x^{2}-2qy^{2}=1}$

for each P-smooth square-free number q other than 2. Each such number q is generated as a product of a subset of P, so there are 2^k − 1 Pell equations to solve. For each such equation, let x_i, y_i be the generated solutions, for i in the range from 1 to max(3, (p_k + 1)/2) (inclusive), where p_k is the largest of the primes in P.

Then, as Lehmer shows, all consecutive pairs of P-smooth numbers are of the form (x_i − 1)/2, (x_i + 1)/2. Thus one can find all such pairs by testing the numbers of this form for P-smoothness.

To find the ten consecutive pairs of {2,3,5}-smooth numbers (in music theory, giving the superparticular ratios for just tuning) let P = {2,3,5}. There are seven P-smooth squarefree numbers q (omitting the eighth P-smooth squarefree number, 2): 1, 3, 5, 6, 10, 15, and 30, each of which leads to a Pell equation. The number of solutions per Pell equation required by Lehmer's method is max(3, (5 + 1)/2) = 3, so this method generates three solutions to each Pell equation, as follows.

• For q = 1, the first three solutions to the Pell equation x² − 2y² = 1 are (3,2), (17,12), and (99,70). Thus, for each of the three values x_i = 3, 17, and 99, Lehmer's method tests the pair (x_i − 1)/2, (x_i + 1)/2 for smoothness; the three pairs to be tested are (1,2), (8,9), and (49,50). Both (1,2) and (8,9) are pairs of consecutive P-smooth numbers, but (49,50) is not, as 49 has 7 as a prime factor.
• For q = 3, the first three solutions to the Pell equation x² − 6y² = 1 are (5,2), (49,20), and (485,198). From the three values x_i = 5, 49, and 485 Lehmer's method forms the three candidate pairs of consecutive numbers (x_i − 1)/2, (x_i + 1)/2: (2,3), (24,25), and (242,243). Of these, (2,3) and (24,25) are pairs of consecutive P-smooth numbers but (242,243) is not.
• For q = 5, the first three solutions to the Pell equation x² − 10y² = 1 are (19,6), (721,228), and (27379,8658). The Pell solution (19,6) leads to the pair of consecutive P-smooth numbers (9,10); the other two solutions to the Pell equation do not lead to P-smooth pairs.
• For q = 6, the first three solutions to the Pell equation x² − 12y² = 1 are (7,2), (97,28), and (1351,390). The Pell solution (7,2) leads to the pair of consecutive P-smooth numbers (3,4).
• For q = 10, the first three solutions to the Pell equation x² − 20y² = 1 are (9,2), (161,36), and (2889,646). The Pell solution (9,2) leads to the pair of consecutive P-smooth numbers (4,5) and the Pell solution (161,36) leads to the pair of consecutive P-smooth numbers (80,81).
• For q = 15, the first three solutions to the Pell equation x² − 30y² = 1 are (11,2), (241,44), and (5291,966). The Pell solution (11,2) leads to the pair of consecutive P-smooth numbers (5,6).
• For q = 30, the first three solutions to the Pell equation x² − 60y² = 1 are (31,4), (1921,248), and (119071,15372). The Pell solution (31,4) leads to the pair of consecutive P-smooth numbers (15,16).

Størmer's original result can be used to show that the number of consecutive pairs of integers that are smooth with respect to a set of k primes is at most 3^k − 2^k. Lehmer's result produces a tighter bound for sets of small primes: (2^k − 1) × max(3,(p_k+1)/2).[2]

The number of consecutive pairs of integers that are smooth with respect to the first k primes are

1, 4, 10, 23, 40, 68, 108, 167, 241, 345, ... (sequence A002071 in the OEIS).

The largest integer from all these pairs, for each k, is

2, 9, 81, 4375, 9801, 123201, 336141, 11859211, ... (sequence A117581 in the OEIS).

OEIS also lists the number of pairs of this type where the larger of the two integers in the pair is square (sequence A117582 in the OEIS) or triangular (sequence A117583 in the OEIS), as both types of pair arise frequently.

Louis Mordell wrote about this result, saying that it "is very pretty, and there are many applications of it."[3]