Rosetta Code

Ruth-Aaron numbers: Difference between revisions

Page Discussion

Ruth-Aaron numbers (view source)

Revision as of 00:10, 4 February 2024

13,541 bytes added ,  3 months ago
Add Mathematica/Wolfram Language implementation
m (syntax highlighting fixup automation)
(Add Mathematica/Wolfram Language implementation)
 
(10 intermediate revisions by 7 users not shown)
Line 154:
First Ruth-Aaron triple (divisors): 89460294
</pre>
 
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">fRuthAaron?: function [n]-> (sum factors.prime n) = sum factors.prime n+1
dRuthAaron?: function [n]-> (sum unique factors.prime n) = sum unique factors.prime n+1
 
print "First 30 Ruth-Aaron numbers (factors):"
loop split.every: 10 select.first:30 1..∞ => fRuthAaron? 'x ->
print map x 's -> pad to :string s 5
 
print ""
print "First 30 Ruth-Aaron numbers (divisors):"
loop split.every: 10 select.first:30 1..∞ => dRuthAaron? 'x ->
print map x 's -> pad to :string s 5</syntaxhighlight>
 
{{out}}
 
<pre>First 30 Ruth-Aaron numbers (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
 
First 30 Ruth-Aaron numbers (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</pre>
 
=={{header|C++}}==
Line 260 ⟶ 285:
 
First Ruth-Aaron triple (divisors): 89460294
</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>
 
Line 296 ⟶ 466:
13775 18655 21183 24024 24432 24880 25839 26642 35456 40081
</pre>
 
=={{header|FreeBASIC}}==
{{trans|XPL0}}
<syntaxhighlight lang="vb">Function DivSum(N As Integer, AllDiv As Boolean) As Integer
Dim As Integer Q, F = 2, F0 = 0, S1 = 0
Do
Q = N/F
If (N Mod F) = 0 Then
If AllDiv Then
S1 += F
Else
If F <> F0 Then S1 += F : F0 = F
End If
N = Q
Else
F += 1
End If
Loop Until F > N
Return S1
End Function
 
Sub Ruth_Aaron(AllDiv As Boolean)
Dim As Integer S, C = 0, S0 = 0, N = 2
Do
S = DivSum(N, AllDiv)
If S = S0 Then
Print Using "######"; N-1;
C += 1
If (C Mod 10) = 0 Then Print
End If
S0 = S
N += 1
Loop Until C >= 30
End Sub
 
Print "First 30 Ruth-Aaron numbers (factors):"
Ruth_Aaron(True) ' https://oeis.org/A039752
Print !"\nFirst 30 Ruth-Aaron numbers (divisors):"
Ruth_Aaron(False) ' https://oeis.org/A006145
 
Sleep</syntaxhighlight>
{{out}}
<pre>First 30 Ruth-Aaron numbers (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
 
First 30 Ruth-Aaron numbers (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</pre>
 
=={{header|Go}}==
Line 535 ⟶ 757:
35456 35457
40081 40082</syntaxhighlight>
 
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
 
public final class RuthAaronNumbers {
public static void main(String[] aArgs) {
System.out.println("The first 30 Ruth-Aaron numbers (factors):");
firstRuthAaronNumbers(30, NumberType.FACTOR);
System.out.println("The first 30 Ruth-Aaron numbers (divisors):");
firstRuthAaronNumbers(30, NumberType.DIVISOR);
System.out.println("First Ruth-Aaron triple (factors): " + firstRuthAaronTriple(NumberType.FACTOR));
System.out.println();
System.out.println("First Ruth-Aaron triple (divisors): " + firstRuthAaronTriple(NumberType.DIVISOR));
System.out.println();
}
private enum NumberType { DIVISOR, FACTOR }
private static void firstRuthAaronNumbers(int aCount, NumberType aNumberType) {
primeSumOne = 0;
primeSumTwo = 0;
for ( int n = 2, count = 0; count < aCount; n++ ) {
primeSumTwo = switch ( aNumberType ) {
case DIVISOR -> primeDivisorSum(n);
case FACTOR -> primeFactorSum(n);
};
if ( primeSumOne == primeSumTwo ) {
count += 1;
System.out.print(String.format("%6d", n - 1));
if ( count == aCount / 2 ) {
System.out.println();
}
}
primeSumOne = primeSumTwo;
}
System.out.println();
System.out.println();
}
private static int firstRuthAaronTriple(NumberType aNumberType) {
primeSumOne = 0;
primeSumTwo = 0;
primeSumThree = 0;
int n = 2;
boolean found = false;
while ( ! found ) {
primeSumThree = switch ( aNumberType ) {
case DIVISOR -> primeDivisorSum(n);
case FACTOR -> primeFactorSum(n);
};
if ( primeSumOne == primeSumTwo && primeSumTwo == primeSumThree ) {
found = true;
}
n += 1;
primeSumOne = primeSumTwo;
primeSumTwo = primeSumThree;
}
return n - 2;
}
private static int primeDivisorSum(int aNumber) {
return primeSum(aNumber, new HashSet<Integer>());
}
private static int primeFactorSum(int aNumber) {
return primeSum(aNumber, new ArrayList<Integer>());
}
private static int primeSum(int aNumber, Collection<Integer> aCollection) {
Collection<Integer> values = aCollection;
 
for ( int i = 0, prime = 2; prime * prime <= aNumber; i++ ) {
while ( aNumber % prime == 0 ) {
aNumber /= prime;
values.add(prime);
}
prime = primes.get(i + 1);
}
 
if ( aNumber > 1 ) {
values.add(aNumber);
}
return values.stream().reduce(0, ( l, r ) -> l + r );
}
private static List<Integer> listPrimeNumbersUpTo(int aNumber) {
BitSet sieve = new BitSet(aNumber + 1);
sieve.set(2, aNumber + 1);
final int squareRoot = (int) Math.sqrt(aNumber);
for ( int i = 2; i <= squareRoot; i = sieve.nextSetBit(i + 1) ) {
for ( int j = i * i; j <= aNumber; j += i ) {
sieve.clear(j);
}
}
List<Integer> result = new ArrayList<Integer>(sieve.cardinality());
for ( int i = 2; i >= 0; i = sieve.nextSetBit(i + 1) ) {
result.add(i);
}
return result;
}
private static int primeSumOne, primeSumTwo, primeSumThree;
private static List<Integer> primes = listPrimeNumbersUpTo(50_000);
 
}
</syntaxhighlight>
{{ out }}
<pre>
The first 30 Ruth-Aaron numbers (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
 
The first 30 Ruth-Aaron numbers (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
 
First Ruth-Aaron triple (factors): 417163
 
First Ruth-Aaron triple (divisors): 89460295
</pre>
 
=={{header|Julia}}==
Line 578 ⟶ 941:
 
Ruth Aaron factor triple starts at: 417162
</pre>
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
{{trans|Julia}}
<syntaxhighlight lang="Mathematica">
SumPrimeDivisors[n_] := Total[First /@ FactorInteger[n]]
RuthAaron[n_] := SumPrimeDivisors[n] == SumPrimeDivisors[n + 1]
 
SumPrimeFactors[n_] :=
Total[First[#] * Last[#] & /@ FactorInteger[n]]
RuthAaronFactors[n_] :=
SumPrimeFactors[n] == SumPrimeFactors[n + 1]
 
RuthAaronSeq := Select[Range[100000], RuthAaron]
RuthAaronFactorSeq := Select[Range[100000], RuthAaronFactors]
 
Print["30 Ruth Aaron numbers:"]
Print[Take[RuthAaronSeq, 30]]
 
Print["\n30 Ruth Aaron factor numbers:"]
Print[Take[RuthAaronFactorSeq, 30]]
</syntaxhighlight>
{{out}}
<pre>
30 Ruth Aaron numbers:
{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}
 
30 Ruth Aaron factor numbers:
{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}
 
</pre>
 
=={{header|Nim}}==
{{trans|C++}}
<syntaxhighlight lang="Nim">import std/strformat
 
template isEven(n: Natural): bool = (n and 1) == 0
 
func primeFactorSum(n: int): int =
var n = n
while n.isEven:
inc result, 2
n = n shr 1
var p = 3
var sq = 9
while sq <= n:
while n mod p == 0:
inc result, p
n = n div p
inc sq, (p + 1) shl 2
inc p, 2
if n > 1:
inc result, n
 
func primeDivisorSum(n: int): int =
var n = n
if n.isEven:
inc result, 2
n = n shr 1
while n.isEven:
n = n shr 1
var p = 3
var sq = 9
while sq <= n:
if n mod p == 0:
inc result, p
n = n div p
while n mod p == 0:
n = n div p
inc sq, (p + 1) shl 2
inc p, 2
if n > 1:
inc result, n
 
const Limit = 30
 
proc firstRuthAaronByFactors() =
echo &"First {Limit} Ruth-Aaron numbers (factors):"
var fsum1, fsum2 = 0
var n = 2
var count = 0
while count < Limit:
fsum2 = primeFactorSum(n)
if fsum1 == fsum2:
inc count
stdout.write &"{n - 1:5}", if count mod 10 == 0: '\n' else: ' '
fsum1 = fsum2
inc n
 
proc firstRuthAaronByDivisors() =
echo &"\nFirst {Limit} Ruth-Aaron numbers (divisors):"
var dsum1, dsum2 = 0
var n = 2
var count = 0
while count < Limit:
dsum2 = primeDivisorSum(n)
if dsum1 == dsum2:
inc count
stdout.write &"{n - 1:5}", if count mod 10 == 0: '\n' else: ' '
dsum1 = dsum2
inc n
 
proc firstRuthAaronTripleByFactors() =
var fsum1, fsum2 = 0
var n = 2
while true:
let fsum3 = primeFactorSum(n)
if fsum1 == fsum3 and fsum2 == fsum3:
echo &"\nFirst Ruth-Aaron triple (factors): {n - 2}"
break
fsum1 = fsum2
fsum2 = fsum3
inc n
 
proc firstRuthAaronTripleByDivisors() =
var dsum1, dsum2 = 0
var n = 2
while true:
let dsum3 = primeDivisorSum(n)
if dsum1 == dsum3 and dsum2 == dsum3:
echo &"\nFirst Ruth-Aaron triple (divisors): {n - 2}"
break
dsum1 = dsum2
dsum2 = dsum3
inc n
 
firstRuthAaronByFactors()
firstRuthAaronByDivisors()
firstRuthAaronTripleByFactors()
firstRuthAaronTripleByDivisors()
</syntaxhighlight>
 
{{out}}
<pre>First 30 Ruth-Aaron numbers (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
 
First 30 Ruth-Aaron numbers (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
 
First Ruth-Aaron triple (factors): 417162
 
First Ruth-Aaron triple (divisors): 89460294
</pre>
 
Line 583 ⟶ 1,092:
==={{header|Free Pascal}}===
all depends on fast prime decomposition.
<syntaxhighlight lang="pascal">program RuthAaronNumb;
program RuthAaronNumb;
// gets factors of consecutive integers fast
// limited to 1.2e11
Line 978 ⟶ 1,488:
until false
end;
var
 
T1,T0 : Int64;
Begin
T0 := GetTickCount64;
InitSmallPrimes;
Get_RA_Prime(30,false);
Get_RA_Prime(30,true);
writeln;('used time: ',GettickCount64-T0,' ms');
writeln;
 
writeln('First Ruth-Aaron triple (factors) :');
T0 := GetTickCount64;
writeln(findfirstTripplesFactor(true):10);
writeln(findfirstTripplesFactor(true):10,' in ',GettickCount64-T0,' ms');
writeln;
writeln('First Ruth-Aaron triple (divisors):');
T0 := GetTickCount64;
writeln(findfirstTripplesFactor(false):10);
writeln(findfirstTripplesFactor(false):10,' in ',GettickCount64-T0,' ms');
end.</syntaxhighlight>
{{out|@TIO.RUN}}
<pre>
Real time: 6.811 s CPU share: 99.35 %
First 30 Ruth-Aaron numbers (divisors ):
5 24 49 77 104 153 369 492
Line 1,003 ⟶ 1,519:
5959 6867 8280 8463 10647 12351 14587 16932
17080 18490 20450 24895 26642 26649
used time: 8 ms
 
First Ruth-Aaron triple (factors) :
417162 in 28 ms
 
First Ruth-Aaron triple (divisors):
89460294 in 6817 ms
 
</pre>
Real time: 7.011 s CPU share: 99.03 %</pre>
 
=={{header|Perl}}==
Line 1,215 ⟶ 1,733:
 
However, with nearly 90 million trios of numbers to slog through, it takes around 68 minutes to find the first triple based on divisors.
<syntaxhighlight lang="ecmascriptwren">import "./math" for Int, Nums
import "./seq" for Lst
import "./fmt" for Fmt
Aspen138
337

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/328317...355377"