Problem 58498. Compute the Sisyphus sequence
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 CommentsShow comments
Problem Recent Solvers4