Achilles numbers: Difference between revisions
Added XPL0 example.
(Added Algol 68) |
(Added XPL0 example.) |
||
Line 730:
10 digits: 77330
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>
| |||