Ruth-Aaron numbers: Difference between revisions
No edit summary |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 37: | Line 37: | ||
This uses a large amount of memory - too much for Algol 68G under Windows (and possibly under Linux).<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. |
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 # |
# of the prime factors or divisors are equal # |
||
INT max number = 99 000 000; # max number we will consider # |
INT max number = 99 000 000; # max number we will consider # |
||
Line 139: | Line 139: | ||
print( ( newline, "First Ruth-Aaron triple (factors): ", whole( fra3, 0 ) ) ); |
print( ( newline, "First Ruth-Aaron triple (factors): ", whole( fra3, 0 ) ) ); |
||
print( ( newline, "First Ruth-Aaron triple (divisors): ", whole( dra3, 0 ) ) ) |
print( ( newline, "First Ruth-Aaron triple (divisors): ", whole( dra3, 0 ) ) ) |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 157: | Line 157: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
This takes about 2 minutes 24 seconds (3.2GHz Quad-Core Intel Core i5). |
This takes about 2 minutes 24 seconds (3.2GHz Quad-Core Intel Core i5). |
||
< |
<syntaxhighlight lang="cpp">#include <iomanip> |
||
#include <iostream> |
#include <iostream> |
||
Line 243: | Line 243: | ||
dsum2 = dsum3; |
dsum2 = dsum3; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 264: | Line 264: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
{{works with|Factor|0.99 2022-04-03}} |
{{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 ; |
math.primes.factors prettyprint ranges sequences ; |
||
Line 283: | Line 283: | ||
"First 30 Ruth-Aaron numbers (divisors):" print |
"First 30 Ruth-Aaron numbers (divisors):" print |
||
RA-d list.</ |
RA-d list.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 301: | Line 301: | ||
{{libheader|Go-rcu}} |
{{libheader|Go-rcu}} |
||
Takes about 4.5 minutes. |
Takes about 4.5 minutes. |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 382: | Line 382: | ||
fmt.Println("\nFirst Ruth-Aaron triple (divisors):") |
fmt.Println("\nFirst Ruth-Aaron triple (divisors):") |
||
fmt.Println(resT[0]) |
fmt.Println(resT[0]) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 400: | Line 400: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">import qualified Data.Set as S |
||
import Data.List.Split ( chunksOf ) |
import Data.List.Split ( chunksOf ) |
||
Line 450: | Line 450: | ||
putStrLn "First 30 Ruth-Aaron numbers( divisors ):" |
putStrLn "First 30 Ruth-Aaron numbers( divisors ):" |
||
mapM_ (\nlin -> putStrLn $ foldl1 ( ++ ) $ map (\st -> formatNumber (maxlen2 + 2) st ) |
mapM_ (\nlin -> putStrLn $ foldl1 ( ++ ) $ map (\st -> formatNumber (maxlen2 + 2) st ) |
||
nlin ) numberlines2</ |
nlin ) numberlines2</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>First 30 Ruth-Aaaron numbers ( factors ) : |
<pre>First 30 Ruth-Aaaron numbers ( factors ) : |
||
Line 470: | Line 470: | ||
Thus: |
Thus: |
||
< |
<syntaxhighlight lang="j"> NB. using factors |
||
30{.1 2+/~I. 2 =/\ +/@q: 1+i.100000 |
30{.1 2+/~I. 2 =/\ +/@q: 1+i.100000 |
||
5 6 |
5 6 |
||
Line 534: | Line 534: | ||
26642 26643 |
26642 26643 |
||
35456 35457 |
35456 35457 |
||
40081 40082</ |
40081 40082</syntaxhighlight> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">using Lazy |
||
using Primes |
using Primes |
||
Line 563: | Line 563: | ||
println("\nRuth Aaron triple starts at: ", findfirst(ruthaarontriple, 1:100000000)) |
println("\nRuth Aaron triple starts at: ", findfirst(ruthaarontriple, 1:100000000)) |
||
println("\nRuth Aaron factor triple starts at: ", findfirst(ruthaaronfactorstriple, 1:10000000)) |
println("\nRuth Aaron factor triple starts at: ", findfirst(ruthaaronfactorstriple, 1:10000000)) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
30 Ruth Aaron numbers: |
30 Ruth Aaron numbers: |
||
Line 583: | Line 583: | ||
==={{header|Free Pascal}}=== |
==={{header|Free Pascal}}=== |
||
all depends on fast prime decomposition. |
all depends on fast prime decomposition. |
||
< |
<syntaxhighlight lang="pascal">program RuthAaronNumb; |
||
// gets factors of consecutive integers fast |
// gets factors of consecutive integers fast |
||
// limited to 1.2e11 |
// limited to 1.2e11 |
||
Line 989: | Line 989: | ||
writeln('First Ruth-Aaron triple (divisors):'); |
writeln('First Ruth-Aaron triple (divisors):'); |
||
writeln(findfirstTripplesFactor(false):10); |
writeln(findfirstTripplesFactor(false):10); |
||
end.</ |
end.</syntaxhighlight> |
||
{{out|@TIO.RUN}} |
{{out|@TIO.RUN}} |
||
<pre> |
<pre> |
||
Line 1,012: | Line 1,012: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">#!/usr/bin/perl |
||
use strict; |
use strict; |
||
Line 1,037: | Line 1,037: | ||
$n++; |
$n++; |
||
} |
} |
||
print "divisors:\n\n@answers\n" =~ s/.{60}\K /\n/gr;</ |
print "divisors:\n\n@answers\n" =~ s/.{60}\K /\n/gr;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,056: | Line 1,056: | ||
{{libheader|Phix/online}} |
{{libheader|Phix/online}} |
||
You can run this online [http://phix.x10.mx/p2js/ruthaaron.htm here]. |
You can run this online [http://phix.x10.mx/p2js/ruthaaron.htm here]. |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<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> |
<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 1,090: | Line 1,090: | ||
<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) |
<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> |
--ruth_aaron(true, 1, 3) -- (24 minutes 30s)</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,110: | Line 1,110: | ||
<code>primefactors</code> is defined at [[Prime decomposition#Quackery]]. |
<code>primefactors</code> is defined at [[Prime decomposition#Quackery]]. |
||
< |
<syntaxhighlight lang="quackery"> [ behead dup dip nested rot |
||
witheach |
witheach |
||
[ tuck != if |
[ tuck != if |
||
Line 1,149: | Line 1,149: | ||
raf echo |
raf echo |
||
cr cr |
cr cr |
||
rad echo</ |
rad echo</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,160: | Line 1,160: | ||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
<lang |
<syntaxhighlight lang="raku" line>use Prime::Factor; |
||
my @pf = lazy (^∞).hyper(:1000batch).map: *.&prime-factors.sum; |
my @pf = lazy (^∞).hyper(:1000batch).map: *.&prime-factors.sum; |
||
Line 1,178: | Line 1,178: | ||
# Really, really, _really_ slow. 186(!) minutes... but with no cheating or "leg up". |
# Really, really, _really_ slow. 186(!) minutes... but with no cheating or "leg up". |
||
put "\nFirst Ruth-Aaron triple (Divisors):\n" ~ |
put "\nFirst Ruth-Aaron triple (Divisors):\n" ~ |
||
(1..∞).first: { @upf[$_] == @upf[$_ + 1] == @upf[$_ + 2] }</ |
(1..∞).first: { @upf[$_] == @upf[$_ + 1] == @upf[$_ + 2] }</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>First 30 Ruth-Aaron numbers (Factors): |
<pre>First 30 Ruth-Aaron numbers (Factors): |
||
Line 1,193: | Line 1,193: | ||
=={{header|Sidef}}== |
=={{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 30.by {|n| (sopfr(n) == sopfr(n+1)) && (n > 0) }.join(' ') |
||
say "\nFirst 30 Ruth-Aaron numbers (divisors):" |
say "\nFirst 30 Ruth-Aaron numbers (divisors):" |
||
say 30.by {|n| ( sopf(n) == sopf(n+1)) && (n > 0) }.join(' ')</ |
say 30.by {|n| ( sopf(n) == sopf(n+1)) && (n > 0) }.join(' ')</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,215: | Line 1,215: | ||
However, with nearly 90 million trios of numbers to slog through, it takes around 68 minutes to find the first triple based on divisors. |
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="ecmascript">import "./math" for Int, Nums |
||
import "./seq" for Lst |
import "./seq" for Lst |
||
import "./fmt" for Fmt |
import "./fmt" for Fmt |
||
Line 1,292: | Line 1,292: | ||
System.print("\nFirst Ruth-Aaron triple (divisors):") |
System.print("\nFirst Ruth-Aaron triple (divisors):") |
||
System.print(resT[0])</ |
System.print(resT[0])</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,310: | Line 1,310: | ||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
< |
<syntaxhighlight lang="xpl0">func DivSum(N, AllDiv); \Return sum of divisors |
||
int N, AllDiv; \all divisors vs. only prime divisors |
int N, AllDiv; \all divisors vs. only prime divisors |
||
int F, F0, S, Q; |
int F, F0, S, Q; |
||
Line 1,345: | Line 1,345: | ||
CrLf(0); |
CrLf(0); |
||
Ruth(false); |
Ruth(false); |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
Revision as of 13:13, 28 August 2022
You are encouraged to solve this task according to the task description, using any language you may know.
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.
A Ruth–Aaron triple consists of three consecutive integers with the same properties.
There is a second variant of Ruth–Aaron numbers, one which uses prime factors rather than prime divisors. The difference; divisors are unique, factors may be repeated. The 714, 715 pair appears in both, so the name still fits.
It is common to refer to each Ruth–Aaron group by the first number in it.
- Task
- Find and show, here on this page, the first 30 Ruth-Aaron numbers (factors).
- Find and show, here on this page, the first 30 Ruth-Aaron numbers (divisors).
- Stretch
- Find and show the first Ruth-Aaron triple (factors).
- Find and show the first Ruth-Aaron triple (divisors).
- See also
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.
This uses a large amount of memory - too much for Algol 68G under Windows (and possibly under Linux).
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.
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
- Output:
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
C++
This takes about 2 minutes 24 seconds (3.2GHz Quad-Core Intel Core i5).
#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;
}
}
- Output:
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
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.
- Output:
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
Go
Takes about 4.5 minutes.
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])
}
- Output:
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
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
- Output:
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
J
Currently, the task asks for Ruth-Aaron numbers, rather than Ruth-Aaron groups.
Thus:
NB. using factors
30{.1 2+/~I. 2 =/\ +/@q: 1+i.100000
5 6
8 9
15 16
77 78
125 126
714 715
948 949
1330 1331
1520 1521
1862 1863
2491 2492
3248 3249
4185 4186
4191 4192
5405 5406
5560 5561
5959 5960
6867 6868
8280 8281
8463 8464
10647 10648
12351 12352
14587 14588
16932 16933
17080 17081
18490 18491
20450 20451
24895 24896
26642 26643
26649 26650
NB. using divisors
30{.1 2+/~I. 2 =/\ (+/@{.@q:~&__) 1+i.100000
5 6
24 25
49 50
77 78
104 105
153 154
369 370
492 493
714 715
1682 1683
2107 2108
2299 2300
2600 2601
2783 2784
5405 5406
6556 6557
6811 6812
8855 8856
9800 9801
12726 12727
13775 13776
18655 18656
21183 21184
24024 24025
24432 24433
24880 24881
25839 25840
26642 26643
35456 35457
40081 40082
Julia
using Lazy
using Primes
sumprimedivisors(n) = sum([p[1] for p in factor(n)])
ruthaaron(n) = sumprimedivisors(n) == sumprimedivisors(n + 1)
ruthaarontriple(n) = sumprimedivisors(n) == sumprimedivisors(n + 1) ==
sumprimedivisors(n + 2)
sumprimefactors(n) = sum([p[1] * p[2] for p in factor(n)])
ruthaaronfactors(n) = sumprimefactors(n) == sumprimefactors(n + 1)
ruthaaronfactorstriple(n) = sumprimefactors(n) == sumprimefactors(n + 1) ==
sumprimefactors(n + 2)
raseq = @>> Lazy.range() filter(ruthaaron)
rafseq = @>> Lazy.range() filter(ruthaaronfactors)
println("30 Ruth Aaron numbers:")
foreach(p -> print(lpad(p[2], 6), p[1] % 10 == 0 ? "\n" : ""),
enumerate(collect(take(30, raseq))))
println("\n30 Ruth Aaron factor numbers:")
foreach(p -> print(lpad(p[2], 6), p[1] % 10 == 0 ? "\n" : ""),
enumerate(collect(take(30, rafseq))))
println("\nRuth Aaron triple starts at: ", findfirst(ruthaarontriple, 1:100000000))
println("\nRuth Aaron factor triple starts at: ", findfirst(ruthaaronfactorstriple, 1:10000000))
- Output:
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 Ruth Aaron triple starts at: 89460294 Ruth Aaron factor triple starts at: 417162
Pascal
Free Pascal
all depends on fast prime decomposition.
program RuthAaronNumb;
// gets factors of consecutive integers fast
// limited to 1.2e11
{$IFDEF FPC}
{$MODE DELPHI} {$OPTIMIZATION ON,ALL} {$COPERATORS ON}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF}
uses
sysutils,
strutils //Numb2USA
{$IFDEF WINDOWS},Windows{$ENDIF}
;
//######################################################################
//prime decomposition
const
//HCN(86) > 1.2E11 = 128,501,493,120 count of divs = 4096 7 3 1 1 1 1 1 1 1
HCN_DivCnt = 4096;
//used odd size for test only
SizePrDeFe = 32768;//*72 <= 64kb level I or 2 Mb ~ level 2 cache
type
tItem = Uint64;
tDivisors = array [0..HCN_DivCnt] of tItem;
tpDivisor = pUint64;
tdigits = array [0..31] of Uint32;
//the first number with 11 different prime factors =
//2*3*5*7*11*13*17*19*23*29*31 = 2E11
//56 byte
tprimeFac = packed record
pfSumOfDivs,
pfRemain : Uint64;
pfDivCnt : Uint32;
pfMaxIdx : Uint32;
pfpotPrimIdx : array[0..9] of word;
pfpotMax : array[0..11] of byte;
end;
tpPrimeFac = ^tprimeFac;
tPrimeDecompField = array[0..SizePrDeFe-1] of tprimeFac;
tPrimes = array[0..65535] of Uint32;
var
{$ALIGN 8}
SmallPrimes: tPrimes;
{$ALIGN 32}
PrimeDecompField :tPrimeDecompField;
pdfIDX,pdfOfs: NativeInt;
procedure InitSmallPrimes;
//get primes. #0..65535.Sieving only odd numbers
const
MAXLIMIT = (821641-1) shr 1;
var
pr : array[0..MAXLIMIT] of byte;
p,j,d,flipflop :NativeUInt;
Begin
SmallPrimes[0] := 2;
fillchar(pr[0],SizeOf(pr),#0);
p := 0;
repeat
repeat
p +=1
until pr[p]= 0;
j := (p+1)*p*2;
if j>MAXLIMIT then
BREAK;
d := 2*p+1;
repeat
pr[j] := 1;
j += d;
until j>MAXLIMIT;
until false;
SmallPrimes[1] := 3;
SmallPrimes[2] := 5;
j := 3;
d := 7;
flipflop := (2+1)-1;//7+2*2,11+2*1,13,17,19,23
p := 3;
repeat
if pr[p] = 0 then
begin
SmallPrimes[j] := d;
inc(j);
end;
d += 2*flipflop;
p+=flipflop;
flipflop := 3-flipflop;
until (p > MAXLIMIT) OR (j>High(SmallPrimes));
end;
function OutPots(pD:tpPrimeFac;n:NativeInt):Ansistring;
var
s: String[31];
chk,p,i: NativeInt;
Begin
str(n,s);
result := Format('%15s : ',[Numb2USA(s)]);
with pd^ do
begin
chk := 1;
For n := 0 to pfMaxIdx-1 do
Begin
if n>0 then
result += '*';
p := SmallPrimes[pfpotPrimIdx[n]];
chk *= p;
str(p,s);
result += s;
i := pfpotMax[n];
if i >1 then
Begin
str(pfpotMax[n],s);
result += '^'+s;
repeat
chk *= p;
dec(i);
until i <= 1;
end;
end;
p := pfRemain;
If p >1 then
Begin
str(p,s);
chk *= p;
result += '*'+s;
end;
end;
end;
function CnvtoBASE(var dgt:tDigits;n:Uint64;base:NativeUint):NativeInt;
//n must be multiple of base aka n mod base must be 0
var
q,r: Uint64;
i : NativeInt;
Begin
fillchar(dgt,SizeOf(dgt),#0);
i := 0;
n := n div base;
result := 0;
repeat
r := n;
q := n div base;
r -= q*base;
n := q;
dgt[i] := r;
inc(i);
until (q = 0);
//searching lowest pot in base
result := 0;
while (result<i) AND (dgt[result] = 0) do
inc(result);
inc(result);
end;
function IncByBaseInBase(var dgt:tDigits;base:NativeInt):NativeInt;
var
q :NativeInt;
Begin
result := 0;
q := dgt[result]+1;
if q = base then
repeat
dgt[result] := 0;
inc(result);
q := dgt[result]+1;
until q <> base;
dgt[result] := q;
result +=1;
end;
function SieveOneSieve(var pdf:tPrimeDecompField):boolean;
var
dgt:tDigits;
i,j,k,pr,fac,n,MaxP : Uint64;
begin
n := pdfOfs;
if n+SizePrDeFe >= sqr(SmallPrimes[High(SmallPrimes)]) then
EXIT(FALSE);
//init
for i := 0 to SizePrDeFe-1 do
begin
with pdf[i] do
Begin
pfDivCnt := 1;
pfSumOfDivs := 1;
pfRemain := n+i;
pfMaxIdx := 0;
pfpotPrimIdx[0] := 0;
pfpotMax[0] := 0;
end;
end;
//first factor 2. Make n+i even
i := (pdfIdx+n) AND 1;
IF (n = 0) AND (pdfIdx<2) then
i := 2;
repeat
with pdf[i] do
begin
j := BsfQWord(n+i);
pfMaxIdx := 1;
pfpotPrimIdx[0] := 0;
pfpotMax[0] := j;
pfRemain := (n+i) shr j;
pfSumOfDivs := (Uint64(1) shl (j+1))-1;
pfDivCnt := j+1;
end;
i += 2;
until i >=SizePrDeFe;
//i now index in SmallPrimes
i := 0;
maxP := trunc(sqrt(n+SizePrDeFe))+1;
repeat
//search next prime that is in bounds of sieve
if n = 0 then
begin
repeat
inc(i);
pr := SmallPrimes[i];
k := pr-n MOD pr;
if k < SizePrDeFe then
break;
until pr > MaxP;
end
else
begin
repeat
inc(i);
pr := SmallPrimes[i];
k := pr-n MOD pr;
if (k = pr) AND (n>0) then
k:= 0;
if k < SizePrDeFe then
break;
until pr > MaxP;
end;
//no need to use higher primes
if pr*pr > n+SizePrDeFe then
BREAK;
//j is power of prime
j := CnvtoBASE(dgt,n+k,pr);
repeat
with pdf[k] do
Begin
pfpotPrimIdx[pfMaxIdx] := i;
pfpotMax[pfMaxIdx] := j;
pfDivCnt *= j+1;
fac := pr;
repeat
pfRemain := pfRemain DIV pr;
dec(j);
fac *= pr;
until j<= 0;
pfSumOfDivs *= (fac-1)DIV(pr-1);
inc(pfMaxIdx);
k += pr;
j := IncByBaseInBase(dgt,pr);
end;
until k >= SizePrDeFe;
until false;
//correct sum of & count of divisors
for i := 0 to High(pdf) do
Begin
with pdf[i] do
begin
j := pfRemain;
if j <> 1 then
begin
pfSumOFDivs *= (j+1);
pfDivCnt *=2;
end;
end;
end;
result := true;
end;
function NextSieve:boolean;
begin
dec(pdfIDX,SizePrDeFe);
inc(pdfOfs,SizePrDeFe);
result := SieveOneSieve(PrimeDecompField);
end;
function GetNextPrimeDecomp:tpPrimeFac;
begin
if pdfIDX >= SizePrDeFe then
if Not(NextSieve) then
EXIT(NIL);
result := @PrimeDecompField[pdfIDX];
inc(pdfIDX);
end;
function Init_Sieve(n:NativeUint):boolean;
//Init Sieve pdfIdx,pdfOfs are Global
begin
pdfIdx := n MOD SizePrDeFe;
pdfOfs := n-pdfIdx;
result := SieveOneSieve(PrimeDecompField);
end;
//end prime decomposition
//######################################################################
procedure Get_RA_Prime(cntlimit:NativeUInt;useFactors:Boolean);
var
pPrimeDecomp :tpPrimeFac;
pr,sum0,sum1,n,i,cnt : NativeUInt;
begin
write('First 30 Ruth-Aaron numbers (');
if useFactors then
writeln('factors ):')
else
writeln('divisors ):');
cnt := 0;
sum1:= 0;
n := 2;
Init_Sieve(n);
repeat
pPrimeDecomp:= GetNextPrimeDecomp;
with pPrimeDecomp^ do
begin
sum0:= pfRemain;
//if not(prime)
if (sum0 <> n) then
begin
if sum0 = 1 then
sum0 := 0;
For i := 0 to pfMaxIdx-1 do
begin
pr := smallprimes[pfpotPrimIdx[i]];
if useFactors then
sum0 += pr*pfpotMax[i]
else
sum0 += pr;
end;
if sum1 = sum0 then
begin
write(n-1:10);
inc(cnt);
if cnt mod 8 = 0 then
writeln;
end;
sum1 := sum0;
end
else
sum1:= 0;
end;
inc(n);
until cnt>=cntlimit;
writeln;
end;
function findfirstTripplesFactor(useFactors:boolean):NativeUint;
var
pPrimeDecomp :tpPrimeFac;
pr,sum0,sum1,sum2,i : NativeUInt;
begin
sum1:= 0;
sum2:= 0;
result:= 2;
Init_Sieve(result);
repeat
pPrimeDecomp:= GetNextPrimeDecomp;
with pPrimeDecomp^ do
begin
sum0:= pfRemain;
//if not(prime)
if (sum0 <> result) then
begin
if sum0 = 1 then
sum0 := 0;
For i := 0 to pfMaxIdx-1 do
begin
pr := smallprimes[pfpotPrimIdx[i]];
if useFactors then
pr *= pfpotMax[i];
sum0 += pr
end;
if (sum2 = sum0) AND (sum1=sum0) then
Exit(result-2);
end
else
sum0 := 0;
sum2:= sum1;
sum1 := sum0;
end;
inc(result);
until false
end;
Begin
InitSmallPrimes;
Get_RA_Prime(30,false);
Get_RA_Prime(30,true);
writeln;
writeln('First Ruth-Aaron triple (factors) :');
writeln(findfirstTripplesFactor(true):10);
writeln;
writeln('First Ruth-Aaron triple (divisors):');
writeln(findfirstTripplesFactor(false):10);
end.
- @TIO.RUN:
Real time: 6.811 s CPU share: 99.35 % 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 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 Ruth-Aaron triple (factors) : 417162 First Ruth-Aaron triple (divisors): 89460294
Perl
#!/usr/bin/perl
use strict;
use warnings;
use ntheory qw( factor vecsum );
use List::AllUtils qw( uniq );
#use Data::Dump 'dd'; dd factor(6); exit;
my $n = 1;
my @answers;
while( @answers < 30 )
{
vecsum(factor($n)) == vecsum(factor($n+1)) and push @answers, $n;
$n++;
}
print "factors:\n\n@answers\n\n" =~ s/.{60}\K /\n/gr;
$n = 1;
@answers = ();
while( @answers < 30 )
{
vecsum(uniq factor($n)) == vecsum(uniq factor($n+1)) and push @answers, $n;
$n++;
}
print "divisors:\n\n@answers\n" =~ s/.{60}\K /\n/gr;
- Output:
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 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
Phix
You can run this online here.
with javascript_semantics procedure ruth_aaron(bool d, integer n=30, l=2, i=1) string fd = iff(d?"divisors":"factors"), ns = iff(n=1?"":sprintf(" %d",n)), ss = iff(n=1?"":"s"), nt = iff(l=2?"number":"triple") printf(1,"First%s Ruth-Aaron %s%s (%s):\n",{ns,nt,ss,fd}) integer prev = -1, k = i, c = 0 while n do sequence f = prime_factors(k,true,-1) if d then f = unique(f) end if integer s = sum(f) if s and s=prev then c += 1 if c=l-1 then printf(1,"%d ",k-c) n -= 1 end if else c = 0 end if prev = s k += 1 end while printf(1,"\n\n") end procedure atom t0 = time() ruth_aaron(false) -- https://oeis.org/A039752 ruth_aaron(true) -- https://oeis.org/A006145 ruth_aaron(false, 1, 3) -- (2.1s) -- give this one a little leg-up :-) ... ruth_aaron(true, 1, 3, 89460000) -- (0.1s) --ruth_aaron(true, 1, 3) -- (24 minutes 30s)
- Output:
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
Quackery
primefactors
is defined at Prime decomposition#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
- Output:
[ 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 ]
Raku
use Prime::Factor;
my @pf = lazy (^∞).hyper(:1000batch).map: *.&prime-factors.sum;
my @upf = lazy (^∞).hyper(:1000batch).map: *.&prime-factors.unique.sum;
# Task: < 1 second
put "First 30 Ruth-Aaron numbers (Factors):\n" ~
(1..∞).grep( { @pf[$_] == @pf[$_ + 1] } )[^30];
put "\nFirst 30 Ruth-Aaron numbers (Divisors):\n" ~
(1..∞).grep( { @upf[$_] == @upf[$_ + 1] } )[^30];
# Stretch: ~ 5 seconds
put "\nFirst Ruth-Aaron triple (Factors):\n" ~
(1..∞).first: { @pf[$_] == @pf[$_ + 1] == @pf[$_ + 2] }
# 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] }
- Output:
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
Sidef
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(' ')
- Output:
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
Wren
To find the first thirty Ruth-Aaron pairs and the first triple based on factors takes around 2.2 seconds.
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 "./math" for Int, Nums
import "./seq" for Lst
import "./fmt" for Fmt
var resF = []
var resD = []
var resT = [] // factors only
var n = 2
var factors1 = []
var factors2 = [2]
var factors3 = [3]
var sum1 = 0
var sum2 = 2
var sum3 = 3
var countF = 0
var countD = 0
var countT = 0
while (countT < 1 || countD < 30 || countF < 30) {
factors1 = factors2
factors2 = factors3
factors3 = Int.primeFactors(n+2)
sum1 = sum2
sum2 = sum3
sum3 = Nums.sum(factors3)
if (countF < 30 && sum1 == sum2) {
resF.add(n)
countF = countF + 1
}
if (sum1 == sum2 && sum2 == sum3) {
resT.add(n)
countT = countT + 1
}
if (countD < 30) {
var factors4 = factors1.toList
var factors5 = factors2.toList
Lst.prune(factors4)
Lst.prune(factors5)
if (Nums.sum(factors4) == Nums.sum(factors5)) {
resD.add(n)
countD = countD + 1
}
}
n = n + 1
}
System.print("First 30 Ruth-Aaron numbers (factors):")
System.print(resF.join(" "))
System.print("\nFirst 30 Ruth-Aaron numbers (divisors):")
System.print(resD.join(" "))
System.print("\nFirst Ruth-Aaron triple (factors):")
System.print(resT[0])
resT = [] // divisors only
n = 2
factors1 = []
factors2 = [2]
factors3 = [3]
sum1 = 0
sum2 = 2
sum3 = 3
countT = 0
while (countT < 1) {
factors1 = factors2
factors2 = factors3
factors3 = Int.primeFactors(n+2)
Lst.prune(factors3)
sum1 = sum2
sum2 = sum3
sum3 = Nums.sum(factors3)
if (sum1 == sum2 && sum2 == sum3) {
resT.add(n)
countT = countT + 1
}
n = n + 1
}
System.print("\nFirst Ruth-Aaron triple (divisors):")
System.print(resT[0])
- Output:
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
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);
]
- Output:
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