Sisyphus sequence
The Sisyphus sequence is an infinite sequence of positive integers that was devised in 2022 by Eric Angelini and Carole Dubois.
The first term is 1. Subsequent terms are found by applying the following rule:
- If the previous term was even, then halve it.
- If the previous term was odd, then add the smallest prime number that has not yet been added.
1 is odd and so the second term is: 1 + 2 = 3, because 2 is the smallest prime not yet added.
3 is odd and so the third term is: 3 + 3 = 6, because 3 is the smallest prime not yet added.
6 is even and so the fourth term is : 6 ÷ 2 = 3, and so on.
- Task
Find and show on this page (in 10 lines of 10 terms), the first 100 terms of the sequence.
What are the 1,000th, 10,000th, 100,000th and 1,000,000th terms of the sequence and, in each case, what is the highest prime needed to reach them?
If it is difficult or impossible for your language or output device to meet all of these requirements, then just do what you reasonably can.
- Stretch
What are the 10 millionth and 100 millionth terms and the highest prime needed to reach each one?
By the time the 100 millionth term is reached, which number(s) under 250:
- Have not yet occurred in the sequence.
- Have occurred the most times and their number of occurrences.
- Extreme stretch
What is the number of the first term to equal 36?
This was originally set as a challenge by Neil Sloane who was worried by its non-appearance and found by Russ Cox.
- References
- OEIS sequence A350877: The Sisyphus sequence
Python
from collections import Counter
from itertools import islice
from typing import Iterable
from typing import Iterator
from typing import Tuple
from typing import TypeVar
import primesieve
def primes() -> Iterator[int]:
it = primesieve.Iterator()
while True:
yield it.next_prime()
def sisyphus() -> Iterator[Tuple[int, int]]:
prime = primes()
n = 1
p = 0
yield n, p
while True:
if n % 2:
p = next(prime)
n = n + p
else:
n = n // 2
yield n, p
def consume(it: Iterator[Tuple[int, int]], n) -> Tuple[int, int]:
next(islice(it, n - 1, n - 1), None)
return next(it)
T = TypeVar("T")
def batched(it: Iterable[T], n: int) -> Iterable[Tuple[T, ...]]:
_it = iter(it)
batch = tuple(islice(_it, n))
while batch:
yield batch
batch = tuple(islice(_it, n))
if __name__ == "__main__":
it = sisyphus()
first_100 = list(islice(it, 100))
print("The first 100 members of the Sisyphus sequence are:")
for row in batched(first_100, 10):
print(" ".join(str(n).rjust(3) for n, _ in row))
print("")
for interval in [10**x for x in range(3, 9)]:
n, prime = consume(it, interval - (interval // 10))
print(f"{interval:11,}th number: {n:13,} highest prime needed: {prime:11,}")
print("")
sisyphus_lt_250 = Counter(n for n, _ in islice(sisyphus(), 10**8) if n < 250)
print("These numbers under 250 do not occur in the first 100,000,000 terms:")
print(" ", [n for n in range(1, 250) if n not in sisyphus_lt_250])
print("")
most_common = sisyphus_lt_250.most_common(1)[0][1]
print("These numbers under 250 occur the most in the first 100,000,000 terms:")
print(
f" {[n for n, c in sisyphus_lt_250.items() if c == most_common]} "
f"all occur {most_common} times."
)
- Output:
The first 100 members of the Sisyphus sequence are:
1 3 6 3 8 4 2 1 8 4
2 1 12 6 3 16 8 4 2 1
18 9 28 14 7 30 15 44 22 11
42 21 58 29 70 35 78 39 86 43
96 48 24 12 6 3 62 31 92 46
23 90 45 116 58 29 102 51 130 65
148 74 37 126 63 160 80 40 20 10
5 106 53 156 78 39 146 73 182 91
204 102 51 178 89 220 110 55 192 96
48 24 12 6 3 142 71 220 110 55
1,000th number: 990 highest prime needed: 2,273
10,000th number: 24,975 highest prime needed: 30,713
100,000th number: 265,781 highest prime needed: 392,111
1,000,000th number: 8,820,834 highest prime needed: 4,761,697
10,000,000th number: 41,369,713 highest prime needed: 55,900,829
100,000,000th number: 1,179,614,168 highest prime needed: 640,692,323
These numbers under 250 do not occur in the first 100,000,000 terms:
[36, 72, 97, 107, 115, 127, 144, 167, 194, 211, 214, 230, 232]
These numbers under 250 occur the most in the first 100,000,000 terms:
[28, 14, 7] all occur 7 times.
RPL
This is a very slow version (15 minutes to get the 10,000th term on a HP-50g) , but I'm not sure to have enough memory to generate a large enough sieve to find the millionth term in a reasonable amount of time. Anyway, even the first requirement (displaying 10 lines of 10 items) is out of range with a 22-character screen.
≪ 1 CF IF DUP 0 < THEN 1 SF NEG END @ A negative argument requires the sequence to be stored then displayed 0 { 1 } → n cnt seq ≪ 2 1 WHILE 'cnt' INCR n < REPEAT IF DUP 2 MOD THEN OVER + SWAP NEXTPRIME SWAP ELSE 2 / END IF 1 FS? THEN 'seq' OVER STO+ END END IF 1 FS? THEN DROP2 seq ELSE SWAP PREVPRIME R→C END ≫ ≫ 'SISYPH' STO
-100 SISYPH 1000 SISYPH 10000 SISYPH
- Output:
3: {1 3 6 3 8 4 2 1 8 4 2 1 12 6 3 16 8 4 2 1 18 9 28 14 7 30 15 44 22 11 42 21 58 29 70 35 78 39 86 43 96 48 24 12 6 3 62 31 92 46 23 90 45 116 58 29 102 51 130 65 148 74 37 126 63 160 80 40 20 10 5 106 53 156 78 39 146 73 182 91 204 102 51 178 89 220 110 55 192 96 48 24 12 6 3 142 71 220 110 55 }
2: (990.,2273.)
1: (24975.,30713.)
Wren
No option here but to use a sieve as relying on the 'nextPrime' method would be far too slow to achieve the stretch goal in a reasonable time using Wren. Sieve limit found by experimentation.
Extreme stretch not attempted and probably out of the question for Wren.
import "./math" for Int, Nums
import "./fmt" for Fmt
var limit = 1e8
var primes = Int.primeSieve(7 * limit)
var under250 = List.filled(250, 0)
var sisyphus = [1]
under250[1] = 1
var prev = 1
var nextPrimeIndex = 0
var specific = 1000
var count = 1
while (true) {
var next
if (prev % 2 == 0) {
next = prev / 2
} else {
next = prev + primes[nextPrimeIndex]
nextPrimeIndex = nextPrimeIndex + 1
}
count = count + 1
if (count <= 100) sisyphus.add(next)
if (next < 250) under250[next] = under250[next] + 1
if (count == 100) {
System.print("The first 100 members of the Sisyphus sequence are:")
Fmt.tprint("$3d ", sisyphus, 10)
System.print()
} else if (count == specific) {
var prime = primes[nextPrimeIndex-1]
Fmt.print("$,13r member is: $,13d and highest prime needed: $,11d", count, next, prime)
if (count == limit) {
var notFound = (1..249).where { |i| under250[i] == 0 }.toList
var max = Nums.max(under250)
var maxFound = (1..249).where { |i| under250[i] == max }.toList
Fmt.print("\nThese numbers under 250 do not occur in the first $,d terms:", count)
Fmt.print(" $n", notFound)
Fmt.print("\nThese numbers under 250 occur the most in the first $,d terms:", count)
Fmt.print(" $n all occur $d times.", maxFound, max)
return
}
specific = 10 * specific
}
prev = next
}- Output:
The first 100 members of the Sisyphus sequence are:
1 3 6 3 8 4 2 1 8 4
2 1 12 6 3 16 8 4 2 1
18 9 28 14 7 30 15 44 22 11
42 21 58 29 70 35 78 39 86 43
96 48 24 12 6 3 62 31 92 46
23 90 45 116 58 29 102 51 130 65
148 74 37 126 63 160 80 40 20 10
5 106 53 156 78 39 146 73 182 91
204 102 51 178 89 220 110 55 192 96
48 24 12 6 3 142 71 220 110 55
1,000th member is: 990 and highest prime needed: 2,273
10,000th member is: 24,975 and highest prime needed: 30,713
100,000th member is: 265,781 and highest prime needed: 392,111
1,000,000th member is: 8,820,834 and highest prime needed: 4,761,697
10,000,000th member is: 41,369,713 and highest prime needed: 55,900,829
100,000,000th member is: 1,179,614,168 and highest prime needed: 640,692,323
These numbers under 250 do not occur in the first 100,000,000 terms:
[36, 72, 97, 107, 115, 127, 144, 167, 194, 211, 214, 230, 232]
These numbers under 250 occur the most in the first 100,000,000 terms:
[7, 14, 28] all occur 7 times.