Rosetta Code

Ruth-Aaron numbers: Difference between revisions

Page Discussion

Ruth-Aaron numbers (view source)

Revision as of 00:10, 4 February 2024

23,623 bytes added ,  3 months ago
Add Mathematica/Wolfram Language implementation
(Added Go)
(Add Mathematica/Wolfram Language implementation)
 
(17 intermediate revisions by 12 users not shown)
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).
<langsyntaxhighlight lang="cpp">#include <iomanip>
#include <iostream>
 
Line 121 ⟶ 268:
dsum2 = dsum3;
}
}</langsyntaxhighlight>
 
{{out}}
Line 139 ⟶ 286:
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}}==
Line 144 ⟶ 523:
{{libheader|Go-rcu}}
Takes about 4.5 minutes.
<langsyntaxhighlight lang="go">package main
 
import (
Line 225 ⟶ 604:
fmt.Println("\nFirst Ruth-Aaron triple (divisors):")
fmt.Println(resT[0])
}</langsyntaxhighlight>
 
{{out}}
Line 240 ⟶ 619:
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>
 
Line 247 ⟶ 692:
 
Thus:
<langsyntaxhighlight Jlang="j"> NB. using factors
30{.1 2+/~I. 2 =/\ +/@q: 1+i.100000
5 6
Line 311 ⟶ 756:
26642 26643
35456 35457
40081 40082</langsyntaxhighlight>
 
=={{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}}==
<langsyntaxhighlight lang="julia">using Lazy
using Primes
 
Line 340 ⟶ 926:
println("\nRuth Aaron triple starts at: ", findfirst(ruthaarontriple, 1:100000000))
println("\nRuth Aaron factor triple starts at: ", findfirst(ruthaaronfactorstriple, 1:10000000))
</langsyntaxhighlight>{{out}}
<pre>
30 Ruth Aaron numbers:
Line 355 ⟶ 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 360 ⟶ 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 755 ⟶ 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.</lang>
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 780 ⟶ 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}}==
<langsyntaxhighlight lang="perl">#!/usr/bin/perl
 
use strict;
Line 814 ⟶ 1,555:
$n++;
}
print "divisors:\n\n@answers\n" =~ s/.{60}\K /\n/gr;</langsyntaxhighlight>
{{out}}
<pre>
Line 833 ⟶ 1,574:
{{libheader|Phix/online}}
You can run this online [http://phix.x10.mx/p2js/ruthaaron.htm here].
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<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 867 ⟶ 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>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 881 ⟶ 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" perl6line>use Prime::Factor;
 
my @pf = lazy (^∞).hyper(:1000batch).map: *.&prime-factors.sum;
Line 903 ⟶ 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] }</langsyntaxhighlight>
{{out}}
<pre>First 30 Ruth-Aaron numbers (Factors):
Line 918 ⟶ 1,711:
 
=={{header|Sidef}}==
<langsyntaxhighlight 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(' ')</langsyntaxhighlight>
 
{{out}}
Line 940 ⟶ 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.
<langsyntaxhighlight ecmascriptlang="wren">import "./math" for Int, Nums
import "./seq" for Lst
import "./fmt" for Fmt
Line 1,017 ⟶ 1,810:
 
System.print("\nFirst Ruth-Aaron triple (divisors):")
System.print(resT[0])</langsyntaxhighlight>
 
{{out}}
Line 1,035 ⟶ 1,828:
 
=={{header|XPL0}}==
<langsyntaxhighlight XPL0lang="xpl0">func DivSum(N, AllDiv); \Return sum of divisors
int N, AllDiv; \all divisors vs. only prime divisors
int F, F0, S, Q;
Line 1,070 ⟶ 1,863:
CrLf(0);
Ruth(false);
]</langsyntaxhighlight>
 
{{out}}
Aspen138
337

edits

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