Untouchable numbers: Difference between revisions
Added Algol 68
(Added Algol 68) |
|||
Line 61:
:* Wikipedia: [https://en.wikipedia.org/wiki/Goldbach%27s_conjecture Goldbach's conjecture].
<br><br>
=={{header|ALGOL 68}}==
Generates the proper divisor sums with a sieve-like process.
<br>
As noted by the Wren, Go, etc. samples, it is hard to determine what upper limit to use to eliminate non-untouchable numbers. It seems that using the proper divisor sums only, to find untouchables up to limit, limit^2 must be considered.
<br>However, using the observations of the Wren, Go etc. solutions that by using the facts prime + 1 and prime + 3 are not untouchable, and that (probably) 5 is the only odd untouchable, the untouchables up to 1 000 000 can be found by considering numbers up to 64 000 000 (possibly less could be used). At least, this sample finds the same values as the other ones :).
<br>
Possibly, this works because the prime + 1 value eliminates the need to calculate the proper divisor sum of p^2 which appears to help a lot when p is close to the upper limit. Why the 64 * limit (or 63 * limit) is valid is unclear (to me, anyway).
<br>
Note that under Windows, Algol 68G does not allow the declaration of an array large enough for untouchables up to 100 000 (or 1 000 000), so the limit on the third line would need to be reduced to 10 000 or another compiler used. Possibly the Linux version of Algol 68G would have larger limits.
<lang algol68>BEGIN # find some untouchable numbers - numbers not equal to the sum of the #
# proper divisors of any +ve integer #
INT max untouchable = 1 000 000;
# a table of the untouchable numbers #
[ 1 : max untouchable ]BOOL untouchable; FOR i TO UPB untouchable DO untouchable[ i ] := TRUE OD;
# show the counts of untouchable numbers found #
PROC show untouchable statistics = VOID:
BEGIN
print( ( "Untouchable numbers:", newline ) );
INT u count := 0;
FOR i TO UPB untouchable DO
IF untouchable[ i ] THEN u count +:= 1 FI;
IF i = 10
OR i = 100
OR i = 1 000
OR i = 10 000
OR i = 100 000
OR i = 1 000 000
THEN
print( ( whole( u count, -7 ), " to ", whole( i, -8 ), newline ) )
FI
OD
END; # show untouchable counts #
# prints the untouchable numbers up to n #
PROC print untouchables = ( INT n )VOID:
BEGIN
print( ( "Untouchable numbers up to ", whole( n, 0 ), newline ) );
INT u count := 0;
FOR i TO n DO
IF untouchable[ i ] THEN
print( ( whole( i, -4 ) ) );
IF u count +:= 1;
u count MOD 16 = 0
THEN print( ( newline ) )
ELSE print( ( " " ) )
FI
FI
OD;
print( ( newline ) );
print( ( whole( u count, -7 ), " to ", whole( n, -8 ), newline ) )
END; # print untouchables #
# find the untouchable numbers #
# to find untouchable numbers up to e.g.: 10 000, we need to sieve up to #
# 10 000 ^2 i.e. 100 000 000 #
# however if we also use the facts that no untouchable = prime + 1 #
# and no untouchable = odd prime + 3 and 5 is (very probably) the only #
# odd untouchable, other samples suggest we can use limit * 64 to find #
# untlouchables up to 1 000 000 - experimentation reveals this to be true #
# assume the conjecture that there are no odd untouchables except 5 #
BEGIN
untouchable[ 1 ] := FALSE;
untouchable[ 3 ] := FALSE;
FOR i FROM 7 BY 2 TO UPB untouchable DO untouchable[ i ] := FALSE OD
END;
# sieve the primes to max untouchable and flag the non untouchables #
BEGIN
[ 1 : UPB untouchable ]BOOL prime;
prime[ 1 ] := FALSE; prime[ 2 ] := TRUE;
FOR i FROM 3 BY 2 TO UPB prime DO prime[ i ] := TRUE OD;
FOR i FROM 4 BY 2 TO UPB prime DO prime[ i ] := FALSE OD;
FOR i FROM 3 BY 2 TO ENTIER sqrt( UPB prime ) DO
IF prime[ i ] THEN
FOR s FROM i * i BY i + i TO UPB prime DO prime[ s ] := FALSE OD
FI
OD;
FOR i FROM 3 BY 2 TO UPB prime DO
IF prime[ i ] THEN
IF i < max untouchable THEN
untouchable[ i + 1 ] := FALSE;
IF i < ( max untouchable - 2 ) THEN
untouchable[ i + 3 ] := FALSE
FI
FI
FI
OD;
untouchable[ 2 + 1 ] := FALSE # special case for the only even prime #
END;
# construct the proper divisor sums and flag the non untouchables #
BEGIN
[ 1 : max untouchable * 64 ]INT spd;
FOR i TO UPB spd DO spd[ i ] := 1 OD;
FOR i FROM 2 TO UPB spd DO
FOR j FROM i + i BY i TO UPB spd DO spd[ j ] +:= i OD
OD;
FOR i TO UPB spd DO
IF spd[ i ] <= UPB untouchable THEN untouchable[ spd[ i ] ] := FALSE FI
OD
END;
# show the untouchable numbers up to 2000 #
print untouchables( 2 000 );
# show the counts of untouchable numbers #
show untouchable statistics
END</lang>
{{out}}
<pre>
2 5 52 88 96 120 124 146 162 188 206 210 216 238 246 248
262 268 276 288 290 292 304 306 322 324 326 336 342 372 406 408
426 430 448 472 474 498 516 518 520 530 540 552 556 562 576 584
612 624 626 628 658 668 670 708 714 718 726 732 738 748 750 756
766 768 782 784 792 802 804 818 836 848 852 872 892 894 896 898
902 926 934 936 964 966 976 982 996 1002 1028 1044 1046 1060 1068 1074
1078 1080 1102 1116 1128 1134 1146 1148 1150 1160 1162 1168 1180 1186 1192 1200
1212 1222 1236 1246 1248 1254 1256 1258 1266 1272 1288 1296 1312 1314 1316 1318
1326 1332 1342 1346 1348 1360 1380 1388 1398 1404 1406 1418 1420 1422 1438 1476
1506 1508 1510 1522 1528 1538 1542 1566 1578 1588 1596 1632 1642 1650 1680 1682
1692 1716 1718 1728 1732 1746 1758 1766 1774 1776 1806 1816 1820 1822 1830 1838
1840 1842 1844 1852 1860 1866 1884 1888 1894 1896 1920 1922 1944 1956 1958 1960
1962 1972 1986 1992
196 to 2000
Untouchable numbers:
2 to 10
5 to 100
89 to 1000
1212 to 10000
13863 to 100000
150232 to 1000000
</pre>
=={{header|C++}}==
Line 142 ⟶ 269:
real 11m28.031s
</pre>
=={{header|Delphi}}==
| |||