Sisyphus sequence: Difference between revisions
Content added Content deleted
(Add Python) |
(Added Algol 68) |
||
Line 40: | Line 40: | ||
* OEIS sequence [[oeis:A350877|A350877: The Sisyphus sequence]] |
* OEIS sequence [[oeis:A350877|A350877: The Sisyphus sequence]] |
||
<br> |
<br> |
||
=={{header|ALGOL 68}}== |
|||
Using a "generous" estimate of the number of primes required to reach the sequence element 100 000 000 (see the Wren sample).<br> |
|||
Note that a sieve size of 1 000 000 000 is not possible with Algol 68G (so you'll need to use another compiler), though a sieve size of 100 000 000 is allowed - specify e.g.: <code>-heap 768M</code> on the command line. It took in the region of 2-3 minutes for Algol 68G to find the elements up to 10 000 000 on a Windows 11 laptop.<br> |
|||
This sample also shows first the positions of 1..100 in the sequence - apart from the values which don't appear up to element 100 000 000, some of them are quite a long way into the sequence before they appear. |
|||
<syntaxhighlight lang="algol68"> |
|||
BEGIN # generate elements of the Sysiphus Sequence: see OEIS A350877 # |
|||
# returns the largest element in a # |
|||
OP MAX = ( []INT a )INT: |
|||
IF LWB a >UPB a THEN 0 |
|||
ELSE |
|||
INT result := a[ LWB a ]; |
|||
FOR i FROM LWB a + 1 TO UPB a DO |
|||
IF result < a[ i ] THEN result := a[ i ] FI |
|||
OD; |
|||
result |
|||
FI # MAX # ; |
|||
# sieve the primes # |
|||
INT sieve max = 1 000 000 000; ### CHANGE TO E.G.: 100 000 000 FOR ALGOL 68G ### |
|||
BOOL is odd := TRUE; |
|||
[ sieve max ]BOOL sieve; FOR i TO UPB sieve DO sieve[ i ] := is odd; is odd := NOT is odd OD; |
|||
sieve[ 1 ] := FALSE; |
|||
sieve[ 2 ] := TRUE; |
|||
FOR s FROM 3 BY 2 TO ENTIER sqrt( sieve max ) DO |
|||
IF sieve[ s ] THEN |
|||
FOR p FROM s * s BY s TO sieve max DO sieve[ p ] := FALSE OD |
|||
FI |
|||
OD; |
|||
[ 1 : 250 ]INT pos; # positions of 1..250 in the sequence # |
|||
[ 1 : 250 ]INT occurs; # occurances of 1..250 in the sequence # |
|||
FOR i TO UPB pos DO pos[ i ] := occurs[ i ] := 0 OD; |
|||
INT max count = sieve max OVER 10; # highest element required # |
|||
INT s := 1; # the first element is defined as 1 # |
|||
INT count := 1; # count of elements found so far # |
|||
print( ( "Sysiphus sequence - first 100 elements:", newline ) ); |
|||
print( ( whole( s, -4 ) ) ); |
|||
pos[ s ] := count; |
|||
INT next to show := 1000; # next power-of-10 element to show # |
|||
INT last used prime := 0; # latest prime from the list # |
|||
INT p pos := 0; # current position in the sieve # |
|||
WHILE count < max count DO |
|||
# calculate the next element # |
|||
IF NOT ODD s THEN |
|||
# the previous element was even - halve it # |
|||
s OVERAB 2 |
|||
ELSE |
|||
# the previous element was odd: add the next prime from the list # |
|||
WHILE p pos +:= 1; |
|||
NOT sieve[ p pos ] |
|||
DO SKIP OD; |
|||
s +:= ( last used prime := p pos ) |
|||
FI; |
|||
count +:= 1; |
|||
IF count <= 100 THEN # have one of the first 100 elements # |
|||
print( ( whole( s, -4 ) ) ); |
|||
IF count MOD 10 = 0 THEN print( ( newline ) ) FI; |
|||
IF count = 100 THEN print( ( newline ) ) FI |
|||
ELIF count = next to show THEN |
|||
# reached a power of ten count # |
|||
print( ( "sequence element ", whole( count, -10 ) |
|||
, " is ", whole( s, -10 ) |
|||
, ", highest used prime is ", whole( last used prime, -10 ) |
|||
, newline |
|||
) |
|||
); |
|||
next to show *:= 10 |
|||
FI; |
|||
IF s < UPB pos THEN |
|||
IF pos[ s ] = 0 THEN |
|||
# have the first appearence of s in the sequence # |
|||
pos[ s ] := count |
|||
FI; |
|||
occurs[ s ] +:= 1 |
|||
FI |
|||
OD; |
|||
print( ( newline ) ); |
|||
print( ( "Integers in 1..", whole( UPB pos, 0 ) |
|||
, " not found in the sequence up to element ", whole( max count, 0 ) |
|||
, ":", newline |
|||
) |
|||
); |
|||
FOR i TO UPB pos DO |
|||
IF pos[ i ] = 0 THEN print( ( " ", whole( i, 0 ) ) ) FI |
|||
OD; |
|||
print( ( newline ) ); |
|||
INT max occurs = MAX occurs; |
|||
print( ( "Integers in 1..", whole( UPB pos, 0 ) |
|||
, " that occur most often ( ", whole( max occurs, 0 ) |
|||
, " times ) up to element ", whole( max count, 0 ) |
|||
, ":", newline |
|||
) |
|||
); |
|||
FOR i TO UPB occurs DO |
|||
IF occurs[ i ] = max occurs THEN print( ( " ", whole( i, 0 ) ) ) FI |
|||
OD; |
|||
print( ( newline, newline ) ); |
|||
print( ( "Position in the sequence of 1..100 up to element ", whole( max count, 0 ) |
|||
, ":", newline |
|||
) |
|||
); |
|||
FOR i TO 100 DO |
|||
print( ( IF pos[ i ] = 0 THEN " unknown" ELSE whole( pos[ i ], -8 ) FI ) ); |
|||
IF i MOD 8 = 0 THEN print( ( newline ) ) FI |
|||
OD |
|||
END |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Sysiphus sequence - first 100 elements: |
|||
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 |
|||
sequence element 1000 is 990, highest used prime is 2273 |
|||
sequence element 10000 is 24975, highest used prime is 30713 |
|||
sequence element 100000 is 265781, highest used prime is 392111 |
|||
sequence element 1000000 is 8820834, highest used prime is 4761697 |
|||
sequence element 10000000 is 41369713, highest used prime is 55900829 |
|||
sequence element 100000000 is 1179614168, highest used prime is 640692323 |
|||
Integers in 1..250 not found in the sequence up to element 100000000: |
|||
36 72 97 107 115 127 144 167 194 211 214 230 232 250 |
|||
Integers in 1..250 that occur most often ( 7 times ) up to element 100000000: |
|||
7 14 28 |
|||
Position in the sequence of 1..100 up to element 100000000: |
|||
1 7 2 6 71 3 25 5 |
|||
22 70 30 13 345 24 27 16 |
|||
161 21 148 69 32 29 51 43 |
|||
1154 344 161336 23 34 26 48 737 |
|||
156 160 36 unknown 63 147 38 68 |
|||
234 31 40 28 53 50 126 42 |
|||
639 1153 58 343 73 161335 88 111 |
|||
108 33 135 614667 192 47 65 736 |
|||
60 155 454 159 186 35 97 unknown |
|||
78 62 2340 146 143 37 24841 67 |
|||
476 233 433 10579 140 39 359 169 |
|||
85 52 80 49 195 125 166 41 |
|||
unknown 638 204 1152 |
|||
</pre> |
|||
Using Algol 68G with max sieve set to 100 000 000 (sequence elements up to 10 000 000) is as above, except for the missing elements and counts of occurrences (and obviously, the line showing the 100 000 000th element is not present): |
|||
<pre> |
|||
Integers in 1..250 not found in the sequence up to element 10000000: |
|||
36 72 97 107 115 127 144 167 194 211 214 223 230 232 250 |
|||
Integers in 1..250 that occur most often ( 6 times ) up to element 10000000: |
|||
3 57 65 85 114 125 130 170 228 |
|||
</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |