Problem 58498. Compute the Sisyphus sequence

Created by ChrisR

Solve Later

A recent article in the New York Times featured the Online Encyclopedia of Integer Sequences, founded by Neil J.A. Sloane. One of the sequences discussed in the article is the Sisyphus sequence. The first term is 1. Subsequent terms are computed with this rule: if the previous term is even, then divide it by 2; if the previous term is odd, add the next available prime. Therefore, the sequence starts 1, 3, 6, 3, 8, 4, 2, 1, 8, 4, 2, 1, 12,… 
The sequence gets its name from the story of Sisyphus, whom one of the Greek gods punished by making him roll a boulder up a hill. Every time Sisyphus neared the top, the boulder would roll back down—just as the sequence “rolls” down to 1 when it hits a power of 2. 
An open question is whether every integer appears in this sequence. Some appear multiple times, but others resist appearance for quite a while. For example, 36 appears some time after a billion terms. 
Write a function to generate the Sisyphus sequence and a variant and determine the smallest missing numbers. The function should have two inputs, n and flag, and four outputs, an, z10, amax, and nrestart. The output an is the nth term of the sequence; z10 is a list of the 10 smallest integers not in the sequence; amax is the maximum value in the sequence; and nrestart is the number of times the sequence rolls back to 1 (i.e., not counting the first 1).
If flag is true or unspecified, generate the sequence as described above—i.e., by adding the next available prime to an odd term. If flag is false, add the next largest unused prime to an odd term. In the latter case, the sequence would start 1, 3, 8, 4, 2, 1, 4, 2, 1, 8, 4, 2, 1, 12, 6, 3, 16, 8, 4, 2, 1… 

Solve

Solution Stats

11 Solutions
6 Solvers

Last Solution submitted on Dec 10, 2024

Last 200 Solutions

Problem Comments

5 Comments

5 Comments

Show 2 older comments

Tim on 19 Jul 2023

For the case flag=false, what does "next largest prime" mean? I don't understand how you get 1, 3, 8, 4, 2, 1, 4, 2, 1, 8, 4, 2, 1, 12, 6, 3, 16, 8, 4, 2, 1….

ChrisR on 19 Jul 2023

I changed it to "next largest unused prime". That is, once you use a prime, delete it from the list. Start at 1, which is odd. The NLUP is 2, so the next term is 3. Then the NLUP is 5, so the next term is 8. Then 4, 2, 1. Then the NLUP is 3. Then 4, 2, 1. Then NLUP = 7, etc. Does that help?

Tim on 19 Jul 2023

I see now--because a(2)=3 you add p=5 instead of p=3, and then go back and use p=3 the next time. It seems like this is the only time this happens--from then on the next largest unused prime is always the next prime.

GeeTwo on 5 Dec 2024 at 13:34

I still don't get why 3 is not "unused" in the alternate form on the second climb but is later on the third; it implies that it was "de-used". Is it that your step up can't be a doubling?

GeeTwo on 11 Dec 2024 at 0:56

Yes, the flag only affects the addition of 3 and 5. After the two is used and a_n < the first prime, adding that prime produces an even number less than twice that prime. Half it, and it's smaller than that prime, hence smaller than the next prime as well. first four steps,

Solution Comments

Show comments

Problem Recent Solvers6

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 58498. Compute the Sisyphus sequence

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers6

Suggested Problems

More from this Author284

Problem Tags

Community Treasure Hunt

Problem 58498. Compute the Sisyphus sequence

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers6

Suggested Problems

More from this Author284

Problem Tags

Community Treasure Hunt

Players