Ruth-Aaron numbers: Difference between revisions
Content added Content deleted
(Created Nim solution.) |
No edit summary |
||
Line 286: | Line 286: | ||
First Ruth-Aaron triple (divisors): 89460294 |
First Ruth-Aaron triple (divisors): 89460294 |
||
</pre> |
</pre> |
||
=={{header|Delphi}}== |
|||
{{works with|Delphi|6.0}} |
|||
{{libheader|SysUtils,StdCtrls}} |
|||
<syntaxhighlight lang="Delphi"> |
|||
{These routines would normally be in a library, but are shown here for clarity} |
|||
function IsPrime(N: int64): boolean; |
|||
{Fast, optimised prime test} |
|||
var I,Stop: int64; |
|||
begin |
|||
if (N = 2) or (N=3) then Result:=true |
|||
else if (n <= 1) or ((n mod 2) = 0) or ((n mod 3) = 0) then Result:= false |
|||
else |
|||
begin |
|||
I:=5; |
|||
Stop:=Trunc(sqrt(N+0.0)); |
|||
Result:=False; |
|||
while I<=Stop do |
|||
begin |
|||
if ((N mod I) = 0) or ((N mod (I + 2)) = 0) then exit; |
|||
Inc(I,6); |
|||
end; |
|||
Result:=True; |
|||
end; |
|||
end; |
|||
procedure StoreNumber(N: integer; var IA: TIntegerDynArray); |
|||
{Expand and store number in array} |
|||
begin |
|||
SetLength(IA,Length(IA)+1); |
|||
IA[High(IA)]:=N; |
|||
end; |
|||
procedure GetPrimeFactors(N: integer; var Facts: TIntegerDynArray); |
|||
{Get all the prime factors of a number} |
|||
var I: integer; |
|||
begin |
|||
I:=2; |
|||
SetLength(Facts,0); |
|||
repeat |
|||
begin |
|||
if (N mod I) = 0 then |
|||
begin |
|||
StoreNumber(I,Facts); |
|||
N:=N div I; |
|||
end |
|||
else I:=GetNextPrime(I); |
|||
end |
|||
until N=1; |
|||
end; |
|||
procedure GetPrimeDivisors(N: integer; var Facts: TIntegerDynArray); |
|||
{Get all unique prime factors of a number} |
|||
var I: integer; |
|||
begin |
|||
I:=2; |
|||
SetLength(Facts,0); |
|||
repeat |
|||
begin |
|||
if (N mod I) = 0 then |
|||
begin |
|||
StoreNumber(I,Facts); |
|||
N:=N div I; |
|||
while (N mod I) = 0 do N:=N div I; |
|||
end |
|||
else I:=GetNextPrime(I); |
|||
end |
|||
until N=1; |
|||
end; |
|||
{------------------------------------------------------------} |
|||
procedure RuthAaronNumbers(Memo: TMemo; UseFactors: boolean); |
|||
var N,Sum1,Sum2,Cnt: integer; |
|||
var S: string; |
|||
function GetFactorSum(N: integer): integer; |
|||
{Get the sum of the prime factors or divisors} |
|||
var IA: TIntegerDynArray; |
|||
var I: integer; |
|||
begin |
|||
if UseFactors then GetPrimeFactors(N,IA) |
|||
else GetPrimeDivisors(N,IA); |
|||
Result:=0; |
|||
for I:=0 to High(IA) do Result:=Result+IA[I]; |
|||
end; |
|||
begin |
|||
Cnt:=0; |
|||
S:=''; |
|||
{Get first sum} |
|||
Sum1:=GetFactorSum(1); |
|||
for N:=1 to High(integer) do |
|||
begin |
|||
{Get next sum} |
|||
Sum2:=GetFactorSum(N+1); |
|||
{Look for matching sums = Ruth-Aaron numbers} |
|||
if Sum1=Sum2 then |
|||
begin |
|||
Inc(Cnt); |
|||
S:=S+Format('%6D',[N]); |
|||
if Cnt>=30 then break; |
|||
If (Cnt mod 10)=0 then S:=S+CRLF; |
|||
end; |
|||
Sum1:=Sum2; |
|||
end; |
|||
Memo.Lines.Add(S); |
|||
Memo.Lines.Add('Count = '+IntToStr(Cnt)); |
|||
end; |
|||
procedure ShowRuthAaronNumbers(Memo: TMemo); |
|||
begin |
|||
Memo.Lines.Add('The first 30 Ruth-Aaron numbers using factors'); |
|||
RuthAaronNumbers(Memo, True); |
|||
Memo.Lines.Add('The first 30 Ruth-Aaron numbers using divisors'); |
|||
RuthAaronNumbers(Memo, False); |
|||
end; |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
The first 30 Ruth-Aaron numbers using factors |
|||
5 8 15 77 125 714 948 1330 1520 1862 |
|||
2491 3248 4185 4191 5405 5560 5959 6867 8280 8463 |
|||
10647 12351 14587 16932 17080 18490 20450 24895 26642 26649 |
|||
Count = 30 |
|||
The first 30 Ruth-Aaron numbers using divisors |
|||
5 24 49 77 104 153 369 492 714 1682 |
|||
2107 2299 2600 2783 5405 6556 6811 8855 9800 12726 |
|||
13775 18655 21183 24024 24432 24880 25839 26642 35456 40081 |
|||
Count = 30 |
|||
Elapsed Time: 5.991 Sec. |
|||
</pre> |
|||
=={{header|Factor}}== |
=={{header|Factor}}== |