Sisyphus sequence: Difference between revisions

=={{header|Python}}==

{{libheader|primesieve}}

<syntaxhighlight lang="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."

)</syntaxhighlight>

{{out}}

<pre>

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.

</pre>