Blum integer: Difference between revisions
Added Algol 68
(Added XPL0 example.) |
(Added Algol 68) |
||
Line 24:
* OEIS sequence [[oeis:A016105|A016105: Blum integers]]
<br>
=={{header|ALGOL 68}}==
If running this with ALGOL 68G, you will need to specify a larger heap size with <code>-heap 256M</code> on the command line.<br>
Builds tables of the unique prime factor counts and the last prime factor to handle the stretch goal, uses prime factorisation to find the first 50 Blum integers.
<syntaxhighlight lang="algol68">
BEGIN # find Blum integers, semi-primes where both factors are 3 mod 4 #
# and the factors are distinct #
INT max number = 10 000 000; # maximum possible Blum we will consider #
[ 1 : max number ]INT upfc; # table of unique prime factor counts #
[ 1 : max number ]INT lpf; # table of last prime factors #
FOR i TO UPB upfc DO upfc[ i ] := 0; lpf[ i ] := 1 OD;
FOR i FROM 2 TO UPB upfc OVER 2 DO
FOR j FROM i + i BY i TO UPB upfc DO
upfc[ j ] +:= 1;
lpf[ j ] := i
OD
OD;
# returns TRUE if n is a Blum integer, FALSE otherwise #
PROC is blum = ( INT n )BOOL:
IF n < 21 THEN FALSE # the lowest primes modulo 4 that are 3 are #
# 3 & 7, so 21 is the lowest possible number #
ELIF NOT ODD n THEN FALSE
ELSE
INT v := n;
INT f count := 0;
INT f := 3;
WHILE f <= v AND f count < 3 DO
IF v MOD f = 0 THEN
IF f MOD 4 /= 3 THEN
f count := 9 # the prime factor mod 4 isn't 3 #
ELSE
v OVERAB f;
f count +:= 1
FI;
IF v MOD f = 0 THEN
f count := 9 # f is not a distinct factor of n #
FI
FI;
f +:= 2
OD;
f count = 2
FI # is blum # ;
# show various Blum integers #
print( ( "The first 50 Blum integers:", newline ) );
INT b count := 0;
[ 0 : 9 ]INT last count := []INT( 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 )[ AT 0 ];
FOR i FROM 21 WHILE b count < 400 000 DO
IF b count < 50 THEN
IF is blum( i ) THEN
b count +:= 1;
last count[ i MOD 10 ] +:= 1;
print( ( whole( i, -4 ) ) );
IF b count MOD 10 = 0 THEN print( ( newline ) ) FI
FI
ELIF upfc[ i ] = 2 THEN
# two unique prime factors - could be a Blum integer #
IF lpf[ i ] MOD 4 = 3 THEN
# the last prime factor mod 4 is three #
IF ( i OVER lpf[ i ] ) MOD 4 = 3 THEN
# and so is the other one #
b count +:= 1;
last count[ i MOD 10 ] +:= 1;
IF b count = 26 828
OR b count = 100 000
OR b count = 200 000
OR b count = 300 000
OR b count = 400 000
THEN
print( ( "The ", whole( b count, -6 )
, "th Blum integer is ", whole( i, -11 )
, newline
)
)
FI
FI
FI
FI
OD;
# show some statistics of the last digits #
print( ( "For Blum integers up to ", whole( b count, 0 ), ":", newline ) );
FOR i FROM LWB last count TO UPB last count DO
IF last count[ i ] /= 0 THEN
print( ( " ", fixed( ( last count[ i ] * 100 ) / b count, -8, 3 )
, "% end with ", whole( i, 0 )
, newline
)
)
FI
OD
END
</syntaxhighlight>
{{out}}
<pre>
The first 50 Blum integers:
21 33 57 69 77 93 129 133 141 161
177 201 209 213 217 237 249 253 301 309
321 329 341 381 393 413 417 437 453 469
473 489 497 501 517 537 553 573 581 589
597 633 649 669 681 713 717 721 737 749
The 26828th Blum integer is 524273
The 100000th Blum integer is 2075217
The 200000th Blum integer is 4275533
The 300000th Blum integer is 6521629
The 400000th Blum integer is 8802377
For Blum integers up to 400000:
25.001% end with 1
25.017% end with 3
24.997% end with 7
24.985% end with 9
</pre>
=={{header|C}}==
{{trans|Wren}}
| |||