Achilles numbers: Difference between revisions
no edit summary
(Nim solution.) |
No edit summary |
||
Line 1,694:
Elapsed time: 13.2644 seconds
</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
<syntaxhighlight lang="Delphi">
function GetTotient(N: integer): integer;
{Calculate Euler's Totient}
var M: integer;
begin
Result:= 0;
for M:= 1 to N do
if GreatestCommonDivisor(M, N) = 1 then
Result:= Result+1;
end;
function IsPowerfulNum(N: integer): boolean;
{Is a powerful number i.e. all prime factors square are divisor}
var I: integer;
var IA: TIntegerDynArray;
begin
Result:=False;
GetPrimeFactors(N,IA);
for I:=0 to High(IA) do
if (N mod (IA[I]*IA[I]))<>0 then exit;
Result:=True;
end;
function CanBeMtoK(N: integer): boolean;
{Can N be represented as M^K?}
var M, A: integer;
begin
Result:=False;
M:= 2;
A:= M*M;
repeat
begin
while true do
begin
if A = N then exit;
if A > N then break;
A:= A*M;
end;
M:= M+1;
A:= M*M;
end
until A > N;
Result:=True;
end;
function IsAchilles(N: integer): boolean;
{Achilles = Is Powerful and can be M^K}
begin
Result:=IsPowerfulNum(N) and CanBeMtoK(N);
end;
procedure AchillesNumbers(Memo: TMemo);
var I,Cnt,Digits: integer;
var S: string;
var DigCnt: array [0..5] of integer;
begin
Memo.Lines.Add('First 50 Achilles numbers:');
Cnt:=0; S:='';
for I:=2 to high(Integer) do
if IsAchilles(I) then
begin
Inc(Cnt);
S:=S+Format('%6d',[I]);
if (Cnt mod 10)=0 then S:=S+CRLF;
if Cnt>=50 then break;
end;
Memo.Lines.Add(S);
Memo.Lines.Add('First 20 Strong Achilles Numbers:');
Cnt:=0; S:='';
for I:=2 to high(Integer) do
if IsAchilles(I) then
if IsAchilles(GetTotient(I)) then
begin
Inc(Cnt);
S:=S+Format('%6d',[I]);
if (Cnt mod 10)=0 then S:=S+CRLF;
if Cnt>=20 then break;
end;
Memo.Lines.Add(S);
Memo.Lines.Add('Digits Counts:');
for I:=0 to High(DigCnt) do DigCnt[I]:=0;
for I:=2 to high(Integer) do
begin
Digits:=NumberOfDigits(I);
if Digits>High(DigCnt) then break;
if IsAchilles(I) then Inc(DigCnt[Digits]);
end;
Memo.Lines.Add('Last Count: '+IntToStr(I));
for I:=0 to High(DigCnt) do
if DigCnt[I]>0 then
begin
Memo.Lines.Add(Format('%d digits: %d',[I,DigCnt[I]]));
end
end;
</syntaxhighlight>
{{out}}
<pre>
First 50 Achilles 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 Achilles Numbers:
500 864 1944 2000 2592 3456 5000 10125 10368 12348
12500 16875 19652 19773 30375 31104 32000 33275 37044 40500
Digits Counts:
Last Count: 100000
2 digits: 1
3 digits: 12
4 digits: 47
5 digits: 192
</pre>
=={{header|Factor}}==
| |||