Ruth-Aaron numbers: Difference between revisions
Content added Content deleted
(Added Quackery.) |
(Added Algol 68) |
||
Line 32: | Line 32: | ||
;*[[oeis:A006145|OEIS:A006145 - Ruth-Aaron numbers (1): sum of prime divisors of n = sum of prime divisors of n+1]] |
;*[[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)]] |
;*[[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++}}== |
=={{header|C++}}== |