Sisyphus sequence: Difference between revisions
Add Python
(Relaxed the task requirements to help RPL and other onboard calculator languages.) |
(Add Python) |
||
Line 40:
* OEIS sequence [[oeis:A350877|A350877: The Sisyphus sequence]]
<br>
=={{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>
=={{header|RPL}}==
| |||