SidYuca - In memoriam

[karluk]

I would like to note the passing of Sid Hollander, who briefly posted in this Puzzles for Programmers forum under the handle SidYuca. I recently came across the following obituary:

https://yucalandia.com/2022/05/30/sid-hollander-yucatans-loss-heavens-gain/

In my view Sid's contributions to the Puzzles for Programmers forum were much greater than the short time he participated here. In particular I spent a significant amount of time on two of his threads, learning a lot about smooth numbers and Bertrand's Paradox in the process. See thread1551-1667009 and thread1551-1667663

 

[karluk]

In my opinion the best tribute we can pay Sid is to attempt a math challenge inspired by one of his old threads. Accordingly, I plan to work on the following problem:

List all pairs of consecutive positive integers where both numbers in the pair have no prime factor greater than seven.

Solutions are plentiful among small pairs. For example (2,3) and (49,50) are valid solutions, but (50,51) is not. It's less obvious but turns out to be true that there are only a finite number of solutions. I don't currently know the answer, but my online references indicate that the math is within my capability. Naturally I would welcome other participants, but I plan on working on the problem regardless of the level of interest it generates. (Note: I'm fairly sure that all valid pairs can easily be found via a computer search. That's a legitimate way of finding the answer, but it's also possible to find the pairs more systematically and prove that there are no others.)

 

[karluk]

Here are the solutions I've found.

[hide]
(1,2)
(2,3)
(3,4)
(4,5)
(5,6)
(6,7)
(7,8)
(8,9)
(9,10)
(14,15)
(15,16)
(20,21)
(24.25)
(27,28)
(35,36)
(48,49)
(49,50)
(63,64)
(80,81)
(125,126)
(224,225)
(2400,2401)
(4374,4375)
[/hide]

Perhaps someone will independently verify these results.

 

[karluk]

As can be seen from my previous post, all of the valid pairs are small and easily found via computer search, or even hand calculations. If I had solved the problem this way, my greatest concern would be uncertainty whether I had searched far enough to find all of the solutions. After all, mathematics abounds with problems where most of the solutions are small, but with a few outliers that require a much more extensive search to find.

Fortunately Størmer's theorem provides bounds for how large the solutions can be, as well as a method for systematically finding them all. The Wikipedia article is

https://en.wikipedia.org/wiki/Størmer's_theorem

 

[karluk]

Let's take a closer look at the algorithm presented in the Wikipedia article and see how much work it entails. Using the problem in this thread of finding pairs in which both numbers in the pair have no prime factors greater than seven, we need the following 15 Pell equations:

x[sup]2[/sup] - 2*y[sup]2[/sup] = 1
x[sup]2[/sup] - 6*y[sup]2[/sup] = 1
x[sup]2[/sup] - 10*y[sup]2[/sup] = 1
x[sup]2[/sup] - 12*y[sup]2[/sup] = 1
x[sup]2[/sup] - 14*y[sup]2[/sup] = 1
x[sup]2[/sup] - 20*y[sup]2[/sup] = 1
x[sup]2[/sup] - 28*y[sup]2[/sup] = 1
x[sup]2[/sup] - 30*y[sup]2[/sup] = 1
x[sup]2[/sup] - 42*y[sup]2[/sup] = 1
x[sup]2[/sup] - 60*y[sup]2[/sup] = 1
x[sup]2[/sup] - 70*y[sup]2[/sup] = 1
x[sup]2[/sup] - 84*y[sup]2[/sup] = 1
x[sup]2[/sup] - 140*y[sup]2[/sup] = 1
x[sup]2[/sup] - 210*y[sup]2[/sup] = 1
x[sup]2[/sup] - 420*y[sup]2[/sup] = 1

The first four solutions to each Pell equation generate a possible valid number pair, so we have 4*15 = 60 pairs to test. Not all of these pairs will be valid solutions, but Størmer's theorem guarantees that there are no others. It turns out that the largest pair that needs to be tested is (1040514048, 1040514049)

 

[karluk]

So far, so good. In exchange for a modest amount of work, we have definitively solved a bit of mathematical trivia which may be of interest to some. But of course there is nothing special about limiting the permitted prime factors to {2,3,5,7}. Adding each additional prime reveals an alarming trend - the number of pairs to test is increasing exponentially:

largest prime = 7, number of pairs to test = 60
largest prime = 11, number of pairs to test = 186
largest prime = 13, number of pairs to test = 441
largest prime = 17, number of pairs to test = 1143
largest prime = 19, number of pairs to test = 2550
largest prime = 23, number of pairs to test = 6132

 

[karluk]

Looked at another way, the success rate (measured by the number of solutions divided by the number of pairs that need to be tested) declines rapidly. When the largest prime allowed is seven, 23/60 = 38.3% of the pairs tested are actually solutions. This declines to a 241/6132 = 3.9% success rate when the largest prime is 23. In exchange for an explosive growth in the amount of testing required, we are being rewarded by finding a solution only about one tenth as often.