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…
Solution Stats
Problem Comments
5 Comments
Solution Comments
Show comments
Loading...
Problem Recent Solvers6
Suggested Problems
-
277 Solvers
-
Matrix with different incremental runs
130 Solvers
-
141 Solvers
-
48 Solvers
-
921 Solvers
More from this Author321
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
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….
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?
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.
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?
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,