Ruth-Aaron numbers: Difference between revisions
Add Mathematica/Wolfram Language implementation
(J) |
(Add Mathematica/Wolfram Language implementation) |
||
| (22 intermediate revisions by 15 users not shown) | |||
Line 1:
{{
A '''Ruth–Aaron''' pair consists of two consecutive integers (e.g., 714 and 715) for which the sums of the prime divisors of each integer are equal. So called because 714 is Babe Ruth's lifetime home run record; Hank Aaron's 715th home run broke this record and 714 and 715 have the same prime divisor sum.
Line 32:
;*[[oeis:A006145|OEIS:A006145 - Ruth-Aaron numbers (1): sum of prime divisors of n = sum of prime divisors of n+1]]
;*[[oeis:A039752|OEIS:A039752 - Ruth-Aaron numbers (2): sum of prime divisors of n = sum of prime divisors of n+1 (both taken with multiplicity)]]
=={{header|ALGOL 68}}==
Uses sieves for the prime factor sums and prime divisor sums, assumes that the first Ruth-Aaron triples are under 99 000 000.<br>
This uses a large amount of memory - too much for Algol 68G under Windows (and possibly under Linux).<br>
With max number set to 1 000 000, Algol 68G can find the first triple using factors in a few seconds (the loop to find the first divisors triple must be commented out or removed) - Real time: 0.941 s on TIO.RUN for the cutdown version.
<syntaxhighlight lang="algol68">BEGIN # find Ruth-Aaron pairs - pairs of consecutive integers where the sum #
# of the prime factors or divisors are equal #
INT max number = 99 000 000; # max number we will consider #
# construct a sieve of primes up to max number #
[ 1 : max number ]BOOL prime;
prime[ 1 ] := FALSE;
prime[ 2 ] := TRUE;
FOR i FROM 3 BY 2 TO UPB prime DO prime[ i ] := TRUE OD;
FOR i FROM 4 BY 2 TO UPB prime DO prime[ i ] := FALSE OD;
FOR i FROM 3 BY 2 TO ENTIER sqrt( UPB prime ) DO
IF prime[ i ] THEN
FOR s FROM i * i BY i + i TO UPB prime DO prime[ s ] := FALSE OD
FI
OD;
# construct the sums of prime divisors up to max number #
[ 1 : max number ]INT ps; FOR n TO max number DO ps[ n ] := 0 OD;
FOR n TO max number DO
IF prime[ n ] THEN
FOR j FROM n BY n TO max number DO ps[ j ] PLUSAB n OD
FI
OD;
INT max count = 30;
# first max count Ruth-Aaron (divisors) numbers #
[ 1 : max count ]INT dra;
INT count := 0;
INT prev sum := 0;
FOR n FROM 2 WHILE count < max count DO
INT this sum = ps[ n ];
IF prev sum = this sum THEN
# found another Ruth-Aaron number #
count PLUSAB 1;
IF count <= max count THEN dra[ count ] := n - 1 FI
FI;
prev sum := this sum
OD;
# first triple #
INT dra3 := 0;
INT pprev sum := ps[ 1 ];
prev sum := ps[ 2 ];
FOR n FROM 3 WHILE dra3 = 0 DO
INT this sum = ps[ n ];
IF prev sum = this sum THEN
IF pprev sum = this sum THEN
# found a Ruth-Aaron triple #
dra3 := n - 2
FI
FI;
pprev sum := prev sum;
prev sum := this sum
OD;
# replace ps with the prime factor count #
INT root max number = ENTIER sqrt( max number );
FOR n FROM 2 TO root max number DO
IF prime[ n ] THEN
INT p := n * n;
WHILE p < root max number DO
FOR j FROM p BY p TO max number DO ps[ j ] PLUSAB n OD;
p TIMESAB n
OD
FI
OD;
# first max count Ruth-Aaron (factors) numbers #
[ 1 : max count ]INT fra;
prev sum := ps[ 1 ];
count := 0;
FOR n FROM 2 WHILE count < 30 DO
INT this sum = ps[ n ];
IF prev sum = this sum THEN
# found another Ruth-Aaron number #
count PLUSAB 1;
fra[ count ] := n - 1
FI;
prev sum := this sum
OD;
# first triple #
prev sum := 0;
count := 0;
INT fra3 := 0;
FOR n FROM 2 WHILE fra3 = 0 DO
INT this sum = ps[ n ];
IF prev sum = this sum AND pprev sum = this sum THEN
# found a Ruth-Aaron triple #
fra3 := n - 2
FI;
pprev sum := prev sum;
prev sum := this sum
OD;
# show the numbers #
print( ( "The first ", whole( max count, 0 ), " Ruth-Aaron numbers (factors):", newline ) );
FOR n TO max count DO
print( ( whole( fra[ n ], - 6 ) ) );
IF n MOD 10 = 0 THEN print( ( newline ) ) FI
OD;
# divisors #
print( ( "The first ", whole( max count, 0 ), " Ruth-Aaron numbers (divisors):", newline ) );
FOR n TO max count DO
print( ( whole( dra[ n ], - 6 ) ) );
IF n MOD 10 = 0 THEN print( ( newline ) ) FI
OD;
# triples #
print( ( newline, "First Ruth-Aaron triple (factors): ", whole( fra3, 0 ) ) );
print( ( newline, "First Ruth-Aaron triple (divisors): ", whole( dra3, 0 ) ) )
END</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): 417162
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++}}==
This takes about 2 minutes 24 seconds (3.2GHz Quad-Core Intel Core i5).
<syntaxhighlight lang="cpp">#include <iomanip>
#include <iostream>
int prime_factor_sum(int n) {
int sum = 0;
for (; (n & 1) == 0; n >>= 1)
sum += 2;
for (int p = 3, sq = 9; sq <= n; p += 2) {
for (; n % p == 0; n /= p)
sum += p;
sq += (p + 1) << 2;
}
if (n > 1)
sum += n;
return sum;
}
int prime_divisor_sum(int n) {
int sum = 0;
if ((n & 1) == 0) {
sum += 2;
n >>= 1;
while ((n & 1) == 0)
n >>= 1;
}
for (int p = 3, sq = 9; sq <= n; p += 2) {
if (n % p == 0) {
sum += p;
n /= p;
while (n % p == 0)
n /= p;
}
sq += (p + 1) << 2;
}
if (n > 1)
sum += n;
return sum;
}
int main() {
const int limit = 30;
int dsum1 = 0, fsum1 = 0, dsum2 = 0, fsum2 = 0;
std::cout << "First " << limit << " Ruth-Aaron numbers (factors):\n";
for (int n = 2, count = 0; count < limit; ++n) {
fsum2 = prime_factor_sum(n);
if (fsum1 == fsum2) {
++count;
std::cout << std::setw(5) << n - 1
<< (count % 10 == 0 ? '\n' : ' ');
}
fsum1 = fsum2;
}
std::cout << "\nFirst " << limit << " Ruth-Aaron numbers (divisors):\n";
for (int n = 2, count = 0; count < limit; ++n) {
dsum2 = prime_divisor_sum(n);
if (dsum1 == dsum2) {
++count;
std::cout << std::setw(5) << n - 1
<< (count % 10 == 0 ? '\n' : ' ');
}
dsum1 = dsum2;
}
dsum1 = 0, fsum1 = 0, dsum2 = 0, fsum2 = 0;
for (int n = 2;; ++n) {
int fsum3 = prime_factor_sum(n);
if (fsum1 == fsum2 && fsum2 == fsum3) {
std::cout << "\nFirst Ruth-Aaron triple (factors): " << n - 2
<< '\n';
break;
}
fsum1 = fsum2;
fsum2 = fsum3;
}
for (int n = 2;; ++n) {
int dsum3 = prime_divisor_sum(n);
if (dsum1 == dsum2 && dsum2 == dsum3) {
std::cout << "\nFirst Ruth-Aaron triple (divisors): " << n - 2
<< '\n';
break;
}
dsum1 = dsum2;
dsum2 = dsum3;
}
}</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>
=={{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}}==
{{works with|Factor|0.99 2022-04-03}}
<syntaxhighlight lang="factor">USING: assocs.extras grouping io kernel lists lists.lazy math
math.primes.factors prettyprint ranges sequences ;
: pair-same? ( ... n quot: ( ... m -- ... n ) -- ... ? )
[ dup 1 + ] dip same? ; inline
: RA-f? ( n -- ? ) [ factors sum ] pair-same? ;
: RA-d? ( n -- ? ) [ group-factors sum-keys ] pair-same? ;
: filter-naturals ( quot -- list ) 1 lfrom swap lfilter ; inline
: RA-f ( -- list ) [ RA-f? ] filter-naturals ;
: RA-d ( -- list ) [ RA-d? ] filter-naturals ;
: list. ( list -- )
30 swap ltake list>array 10 group simple-table. ;
"First 30 Ruth-Aaron numbers (factors):" print
RA-f list. nl
"First 30 Ruth-Aaron numbers (divisors):" print
RA-d list.</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|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}}==
{{trans|Wren}}
{{libheader|Go-rcu}}
Takes about 4.5 minutes.
<syntaxhighlight lang="go">package main
import (
"fmt"
"rcu"
)
func prune(a []int) []int {
prev := a[0]
b := []int{prev}
for i := 1; i < len(a); i++ {
if a[i] != prev {
b = append(b, a[i])
prev = a[i]
}
}
return b
}
func main() {
var resF, resD, resT, factors1 []int
factors2 := []int{2}
factors3 := []int{3}
var sum1, sum2, sum3 int = 0, 2, 3
var countF, countD, countT int
for n := 2; countT < 1 || countD < 30 || countF < 30; n++ {
factors1 = factors2
factors2 = factors3
factors3 = rcu.PrimeFactors(n + 2)
sum1 = sum2
sum2 = sum3
sum3 = rcu.SumInts(factors3)
if countF < 30 && sum1 == sum2 {
resF = append(resF, n)
countF++
}
if sum1 == sum2 && sum2 == sum3 {
resT = append(resT, n)
countT++
}
if countD < 30 {
factors4 := make([]int, len(factors1))
copy(factors4, factors1)
factors5 := make([]int, len(factors2))
copy(factors5, factors2)
factors4 = prune(factors4)
factors5 = prune(factors5)
if rcu.SumInts(factors4) == rcu.SumInts(factors5) {
resD = append(resD, n)
countD++
}
}
}
fmt.Println("First 30 Ruth-Aaron numbers (factors):")
fmt.Println(resF)
fmt.Println("\nFirst 30 Ruth-Aaron numbers (divisors):")
fmt.Println(resD)
fmt.Println("\nFirst Ruth-Aaron triple (factors):")
fmt.Println(resT[0])
resT = resT[:0]
factors1 = factors1[:0]
factors2 = factors2[:1]
factors2[0] = 2
factors3 = factors3[:1]
factors3[0] = 3
countT = 0
for n := 2; countT < 1; n++ {
factors1 = factors2
factors2 = factors3
factors3 = prune(rcu.PrimeFactors(n + 2))
sum1 = sum2
sum2 = sum3
sum3 = rcu.SumInts(factors3)
if sum1 == sum2 && sum2 == sum3 {
resT = append(resT, n)
countT++
}
}
fmt.Println("\nFirst Ruth-Aaron triple (divisors):")
fmt.Println(resT[0])
}</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>
=={{header|Haskell}}==
<syntaxhighlight lang="haskell">import qualified Data.Set as S
import Data.List.Split ( chunksOf )
divisors :: Int -> [Int]
divisors n = [d | d <- [2 .. n] , mod n d == 0]
--for obvious theoretical reasons the smallest divisor of a number bare 1
--must be prime
primeFactors :: Int -> [Int]
primeFactors n = snd $ until ( (== 1) . fst ) step (n , [] )
where
step :: (Int , [Int] ) -> (Int , [Int] )
step (n , li) = ( div n h , li ++ [h] )
where
h :: Int
h = head $ divisors n
primeDivisors :: Int -> [Int]
primeDivisors n = S.toList $ S.fromList $ primeFactors n
solution :: (Int -> [Int] ) -> [Int]
solution f = snd $ until ( (== 30 ) . length . snd ) step ([2 , 3] , [] )
where
step :: ([Int] , [Int] ) -> ([Int] , [Int])
step ( neighbours , ranums ) = ( map ( + 1 ) neighbours , if (sum $ f
$ head neighbours ) == (sum $ f $ last neighbours) then
ranums ++ [ head neighbours ] else ranums )
formatNumber :: Int -> String -> String
formatNumber width num
|width > l = replicate ( width -l ) ' ' ++ num
|width == l = num
|width < l = num
where
l = length num
main :: IO ( )
main = do
let ruth_aaron_pairs = solution primeFactors
maxlen = length $ show $ last ruth_aaron_pairs
numberlines = chunksOf 8 $ map show ruth_aaron_pairs
ruth_aaron_divisors = solution primeDivisors
maxlen2 = length $ show $ last ruth_aaron_divisors
numberlines2 = chunksOf 8 $ map show ruth_aaron_divisors
putStrLn "First 30 Ruth-Aaaron numbers ( factors ) :"
mapM_ (\nlin -> putStrLn $ foldl1 ( ++ ) $ map (\st -> formatNumber (maxlen + 2) st )
nlin ) numberlines
putStrLn " "
putStrLn "First 30 Ruth-Aaron numbers( divisors ):"
mapM_ (\nlin -> putStrLn $ foldl1 ( ++ ) $ map (\st -> formatNumber (maxlen2 + 2) st )
nlin ) numberlines2</syntaxhighlight>
{{out}}
<pre>First 30 Ruth-Aaaron 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|J}}==
Line 38 ⟶ 692:
Thus:
<
30{.1 2+/~I. 2 =/\ +/@q: 1+i.100000
5 6
Line 102 ⟶ 756:
26642 26643
35456 35457
40081 40082</
=={{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}}==
<
using Primes
Line 131 ⟶ 926:
println("\nRuth Aaron triple starts at: ", findfirst(ruthaarontriple, 1:100000000))
println("\nRuth Aaron factor triple starts at: ", findfirst(ruthaaronfactorstriple, 1:10000000))
</
<pre>
30 Ruth Aaron numbers:
Line 146 ⟶ 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 151 ⟶ 1,092:
==={{header|Free Pascal}}===
all depends on fast prime decomposition.
<syntaxhighlight lang
program RuthAaronNumb;
// gets factors of consecutive integers fast
// limited to 1.2e11
Line 546 ⟶ 1,488:
until false
end;
var
T1,T0 : Int64;
Begin
T0 := GetTickCount64;
InitSmallPrimes;
Get_RA_Prime(30,false);
Get_RA_Prime(30,true);
writeln
writeln;
writeln('First Ruth-Aaron triple (factors) :');
T0 := GetTickCount64;
writeln(findfirstTripplesFactor(true):10,' in ',GettickCount64-T0,' ms');
writeln;
writeln('First Ruth-Aaron triple (divisors):');
T0 := GetTickCount64;
writeln(findfirstTripplesFactor(false):10,' in ',GettickCount64-T0,' ms');
end.</syntaxhighlight>
{{out|@TIO.RUN}}
<pre>
First 30 Ruth-Aaron numbers (divisors ):
5 24 49 77 104 153 369 492
Line 571 ⟶ 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
Real time: 7.011 s CPU share: 99.03 %</pre>
=={{header|Perl}}==
<
use strict;
Line 605 ⟶ 1,555:
$n++;
}
print "divisors:\n\n@answers\n" =~ s/.{60}\K /\n/gr;</
{{out}}
<pre>
Line 624 ⟶ 1,574:
{{libheader|Phix/online}}
You can run this online [http://phix.x10.mx/p2js/ruthaaron.htm here].
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">ruth_aaron</span><span style="color: #0000FF;">(</span><span style="color: #004080;">bool</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
Line 658 ⟶ 1,608:
<span style="color: #000000;">ruth_aaron</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">89460000</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (0.1s)
--ruth_aaron(true, 1, 3) -- (24 minutes 30s)</span>
<!--</
{{out}}
<pre>
Line 672 ⟶ 1,622:
First Ruth-Aaron triple (divisors):
89460294
</pre>
=={{header|Quackery}}==
<code>primefactors</code> is defined at [[Prime decomposition#Quackery]].
<syntaxhighlight lang="quackery"> [ behead dup dip nested rot
witheach
[ tuck != if
[ dup dip
[ nested join ] ] ]
drop ] is -duplicates ( [ --> [ )
[ primefactors -duplicates ] is primedivisors ( n --> n )
[ 0 swap witheach + ] is sum ( [ --> n )
[ [] temp put
3 2 primefactors sum
[ over primefactors sum
tuck = if
[ over 1 -
temp take
swap join
temp put ]
dip 1+
temp share size 30 = until ]
2drop
temp take ] is raf ( --> )
[ [] temp put
3 2 primedivisors sum
[ over primedivisors sum
tuck = if
[ over 1 -
temp take
swap join
temp put ]
dip 1+
temp share size 30 = until ]
2drop
temp take ] is rad ( --> )
raf echo
cr cr
rad echo</syntaxhighlight>
{{out}}
<pre>[ 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 ]
[ 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|Raku}}==
<syntaxhighlight lang="raku"
my @pf = lazy (^∞).hyper(:1000batch).map: *.&prime-factors.sum;
Line 694 ⟶ 1,696:
# Really, really, _really_ slow. 186(!) minutes... but with no cheating or "leg up".
put "\nFirst Ruth-Aaron triple (Divisors):\n" ~
(1..∞).first: { @upf[$_] == @upf[$_ + 1] == @upf[$_ + 2] }</
{{out}}
<pre>First 30 Ruth-Aaron numbers (Factors):
Line 707 ⟶ 1,709:
First Ruth-Aaron triple (Divisors):
89460294</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">say "First 30 Ruth-Aaron numbers (factors):"
say 30.by {|n| (sopfr(n) == sopfr(n+1)) && (n > 0) }.join(' ')
say "\nFirst 30 Ruth-Aaron numbers (divisors):"
say 30.by {|n| ( sopf(n) == sopf(n+1)) && (n > 0) }.join(' ')</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|Wren}}==
Line 715 ⟶ 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.
<
import "./seq" for Lst
import "./fmt" for Fmt
Line 792 ⟶ 1,810:
System.print("\nFirst Ruth-Aaron triple (divisors):")
System.print(resT[0])</
{{out}}
Line 807 ⟶ 1,825:
First Ruth-Aaron triple (divisors):
89460294
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang="xpl0">func DivSum(N, AllDiv); \Return sum of divisors
int N, AllDiv; \all divisors vs. only prime divisors
int F, F0, S, Q;
[F:= 2; F0:= 0; S:= 0;
repeat Q:= N/F;
if rem(0) = 0 then
[if AllDiv then S:= S+F
else if F # F0 then
[S:= S+F; F0:= F];
N:= Q;
]
else F:= F+1;
until F > N;
return S;
];
proc Ruth(AllDiv); \Show Ruth-Aaron numbers
int AllDiv;
int C, S, S0, N;
[C:= 0; S0:= 0;
N:= 2;
repeat S:= DivSum(N, AllDiv);
if S = S0 then
[IntOut(0, N-1);
C:= C+1;
if rem(C/10) = 0 then CrLf(0) else ChOut(0, ^ );
];
S0:= S;
N:= N+1;
until C >= 30;
];
[Ruth(true);
CrLf(0);
Ruth(false);
]</syntaxhighlight>
{{out}}
<pre>
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
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>
| |||