Achilles numbers: Difference between revisions

=={{header|ALGOL 68}}==

{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}

{{libheader|ALGOL 68-primes}}

<lang algol68>BEGIN # find Achiles Numbers: numbers whose prime factors p appear at least #

# twice (i.e. if p is a prime factor, so is p^2) and cannot be #

# expressed as m^k for any integer m, k > 1 #

# also find strong Achiles Numbers: Achiles Numbers where the Euler's #

# totient of the number is also Achiles #

# returns the number of integers k where 1 <= k <= n that are mutually #

# prime to n #

PROC totient = ( INT n )INT: # algorithm from the second Go sample #

IF n < 3 THEN 1 # in the Totient Function task #

ELIF n = 3 THEN 2

ELSE

INT result := n;

INT v := n;

INT i := 2;

WHILE i * i <= v DO

IF v MOD i = 0 THEN

WHILE v MOD i = 0 DO v OVERAB i OD;

result -:= result OVER i

FI;

IF i = 2 THEN

i := 1

FI;

i +:= 2

OD;

IF v > 1 THEN result -:= result OVER v FI;

result

FI # totient # ;

# find the numbers #

INT max number = 1 000 000; # max number we will consider #

PR read "primes.incl.a68" PR # include prime utilities #

[]BOOL prime = PRIMESIEVE max number; # construct a sieve of primes #

# table of numbers, will be set to TRUE for the Achiles Numbers #

[ 1 : max number ]BOOL achiles;

FOR a TO UPB achiles DO

achiles[ a ] := TRUE

OD;

# remove the numbers that don't have squared primes as factors #

achiles[ 1 ] := FALSE;

FOR a TO UPB achiles DO

IF prime[ a ] THEN

# have a prime, remove it and every multiple of it that isn't a #

# multiple of a squared #

INT a count := 0;

FOR j FROM a BY a TO UPB achiles DO

a count +:= 1;

IF a count = a THEN # have a multiple of i^2, keep the number #

a count := 0

ELSE # not a multiple of i^2, remove the number #

achiles[ j ] := FALSE

FI

OD

FI

OD;

# achiles now has TRUE for the powerful numbers, remove all m^k (m,k > 1) #

FOR m FROM 2 TO UPB achiles DO

INT mk := m;

INT max mk = UPB achiles OVER m; # avoid overflow if INT is 32 bit #

WHILE mk <= max mk DO

mk *:= m;

achiles[ mk ] := FALSE

OD

OD;

# achiles now has TRUE for imperfect powerful numbers #

# show the first 50 Achiles Numbers #

BEGIN

print( ( "First 50 Achiles Numbers:", newline ) );

INT a count := 0;

FOR a WHILE a count < 50 DO

IF achiles[ a ] THEN

a count +:= 1;

print( ( " ", whole( a, -6 ) ) );

IF a count MOD 10 = 0 THEN

print( ( newline ) )

FI

FI

OD

END;

# show the first 50 Strong Achiles numbers #

BEGIN

print( ( "First 20 Strong Achiles Numbers:", newline ) );

INT s count := 0;

FOR s WHILE s count < 20 DO

IF achiles[ s ] THEN

IF achiles[ totient( s ) ] THEN

s count +:= 1;

print( ( " ", whole( s, -6 ) ) );

IF s count MOD 10 = 0 THEN

print( ( newline ) )

FI

FI

FI

OD

END;

# count the number of Achiles Numbers by their digit counts #

BEGIN

INT a count := 0;

INT power of 10 := 100;

INT digit count := 2;

FOR a TO UPB achiles DO

IF achiles[ a ] THEN

# have an Achiles Number #

a count +:= 1

FI;

IF a = power of 10 THEN

# have reached a power of 10 #

print( ( "Achiles Numbers with ", whole( digit count, 0 )

, " digits: ", whole( a count, -6 )

, newline

)

);

digit count +:= 1;

power of 10 *:= 10;

a count := 0

FI

OD

END

END</lang>

{{out}}

<pre>

First 50 Achiles Numbers:

72 108 200 288 392 432 500 648 675 800

864 968 972 1125 1152 1323 1352 1372 1568 1800

1944 2000 2312 2592 2700 2888 3087 3200 3267 3456

3528 3872 3888 4000 4232 4500 4563 4608 5000 5292

5324 5400 5408 5488 6075 6125 6272 6728 6912 7200

First 20 Strong Achiles Numbers:

500 864 1944 2000 2592 3456 5000 10125 10368 12348

12500 16875 19652 19773 30375 31104 32000 33275 37044 40500

Achiles Numbers with 2 digits: 1

Achiles Numbers with 3 digits: 12

Achiles Numbers with 4 digits: 47

Achiles Numbers with 5 digits: 192

Achiles Numbers with 6 digits: 66</pre>