Blum integer: Difference between revisions
Content added Content deleted
(Added XPL0 example.) |
(Added Algol 68) |
||
Line 24: | Line 24: | ||
* OEIS sequence [[oeis:A016105|A016105: Blum integers]] |
* OEIS sequence [[oeis:A016105|A016105: Blum integers]] |
||
<br> |
<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}}== |
=={{header|C}}== |
||
{{trans|Wren}} |
{{trans|Wren}} |