Problem 58498. Compute the Sisyphus sequence

Created by ChrisR
Appears in Prime Numbers III

Difficulty:Rate

Solve Later
Add To GroupÃ‚

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

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

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

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,