×
INTELLIGENT WORK FORUMS
FOR COMPUTER PROFESSIONALS

Contact US

Log In

Come Join Us!

Are you a
Computer / IT professional?
Join Tek-Tips Forums!
  • Talk With Other Members
  • Be Notified Of Responses
    To Your Posts
  • Keyword Search
  • One-Click Access To Your
    Favorite Forums
  • Automated Signatures
    On Your Posts
  • Best Of All, It's Free!

*Tek-Tips's functionality depends on members receiving e-mail. By joining you are opting in to receive e-mail.

Posting Guidelines

Promoting, selling, recruiting, coursework and thesis posting is forbidden.

Students Click Here

SidYuca - In memoriam

SidYuca - In memoriam

SidYuca - In memoriam

(OP)
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-yu...

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: I can Predict your response with '90%' accuracy. and thread1551-1667663: BULLS' EYE- Students A, B & C

RE: SidYuca - In memoriam

(OP)
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.)

RE: SidYuca - In memoriam

(OP)
Here are the solutions I've found.

Hidden:


(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)

Perhaps someone will independently verify these results.

RE: SidYuca - In memoriam

(OP)
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%C3%B8rmer%27s_the...

RE: SidYuca - In memoriam

(OP)
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:

x2 - 2*y2 = 1
x2 - 6*y2 = 1
x2 - 10*y2 = 1
x2 - 12*y2 = 1
x2 - 14*y2 = 1
x2 - 20*y2 = 1
x2 - 28*y2 = 1
x2 - 30*y2 = 1
x2 - 42*y2 = 1
x2 - 60*y2 = 1
x2 - 70*y2 = 1
x2 - 84*y2 = 1
x2 - 140*y2 = 1
x2 - 210*y2 = 1
x2 - 420*y2 = 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)

RE: SidYuca - In memoriam

(OP)
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

RE: SidYuca - In memoriam

(OP)
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.

Red Flag This Post

Please let us know here why this post is inappropriate. Reasons such as off-topic, duplicates, flames, illegal, vulgar, or students posting their homework.

Red Flag Submitted

Thank you for helping keep Tek-Tips Forums free from inappropriate posts.
The Tek-Tips staff will check this out and take appropriate action.

Reply To This Thread

Posting in the Tek-Tips forums is a member-only feature.

Click Here to join Tek-Tips and talk with other members! Already a Member? Login

Close Box

Join Tek-Tips® Today!

Join your peers on the Internet's largest technical computer professional community.
It's easy to join and it's free.

Here's Why Members Love Tek-Tips Forums:

Register now while it's still free!

Already a member? Close this window and log in.

Join Us             Close