Achilles numbers: Difference between revisions
Content added Content deleted
(Added Algol 68) |
(Added XPL0 example.) |
||
Line 730: | Line 730: | ||
10 digits: 77330 |
10 digits: 77330 |
||
11 digits: 247449 |
11 digits: 247449 |
||
</pre> |
|||
=={{header|XPL0}}== |
|||
<lang XPL0>func GCD(N, D); \Return the greatest common divisor of N and D |
|||
int N, D; \numerator and denominator |
|||
int R; |
|||
[if D > N then |
|||
[R:= D; D:= N; N:= R]; \swap D and N |
|||
while D > 0 do |
|||
[R:= rem(N/D); |
|||
N:= D; |
|||
D:= R; |
|||
]; |
|||
return N; |
|||
]; \GCD |
|||
func Totient(N); \Return the totient of N |
|||
int N, Phi, M; |
|||
[Phi:= 0; |
|||
for M:= 1 to N do |
|||
if GCD(M, N) = 1 then Phi:= Phi+1; |
|||
return Phi; |
|||
]; |
|||
func Powerful(N0); \Return 'true' if N0 is a powerful number |
|||
int N0, N, F, Q, L; |
|||
[if N0 <= 1 then return false; |
|||
N:= N0; F:= 2; |
|||
L:= sqrt(N0); |
|||
loop [Q:= N/F; |
|||
if rem(0) = 0 then \found a factor |
|||
[if rem(N0/(F*F)) then return false; |
|||
N:= Q; |
|||
if F>N then quit; |
|||
] |
|||
else [F:= F+1; |
|||
if F > L then |
|||
[if rem(N0/(N*N)) then return false; |
|||
quit; |
|||
]; |
|||
]; |
|||
]; |
|||
return true; |
|||
]; |
|||
func Achilles(N); \Return 'true' if N is an Achilles number |
|||
int N, M, A; |
|||
[if not Powerful(N) then return false; |
|||
M:= 2; |
|||
A:= M*M; |
|||
repeat loop [if A = N then return false; |
|||
if A > N then quit; |
|||
A:= A*M; |
|||
]; |
|||
M:= M+1; |
|||
A:= M*M; |
|||
until A > N; |
|||
return true; |
|||
]; |
|||
int Cnt, N, Pwr, Start; |
|||
[Cnt:= 0; |
|||
N:= 1; |
|||
loop [if Achilles(N) then |
|||
[IntOut(0, N); |
|||
Cnt:= Cnt+1; |
|||
if Cnt >= 50 then quit; |
|||
if rem(Cnt/10) then ChOut(0, 9) else CrLf(0); |
|||
]; |
|||
N:= N+1; |
|||
]; |
|||
CrLf(0); CrLf(0); |
|||
Cnt:= 0; |
|||
N:= 1; |
|||
loop [if Achilles(N) then |
|||
if Achilles(Totient(N)) then |
|||
[IntOut(0, N); |
|||
Cnt:= Cnt+1; |
|||
if Cnt >= 20 then quit; |
|||
if rem(Cnt/10) then ChOut(0, 9) else CrLf(0); |
|||
]; |
|||
N:= N+1; |
|||
]; |
|||
CrLf(0); CrLf(0); |
|||
for Pwr:= 1 to 6 do |
|||
[IntOut(0, Pwr); Text(0, ": "); |
|||
Start:= fix(Pow(10.0, float(Pwr-1))); |
|||
Cnt:= 0; |
|||
for N:= Start to Start*10-1 do |
|||
if Achilles(N) then Cnt:= Cnt+1; |
|||
IntOut(0, Cnt); CrLf(0); |
|||
]; |
|||
]</lang> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
500 864 1944 2000 2592 3456 5000 10125 10368 12348 |
|||
12500 16875 19652 19773 30375 31104 32000 33275 37044 40500 |
|||
1: 0 |
|||
2: 1 |
|||
3: 12 |
|||
4: 47 |
|||
5: 192 |
|||
6: 664 |
|||
</pre> |
</pre> |