Ruth-Aaron numbers: Difference between revisions
Added Algol 68
(Added Quackery.) |
(Added Algol 68) |
||
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).
<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</lang>
{{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|C++}}==
| |||