Rosetta Code

Amicable pairs: Difference between revisions

Page Discussion

Amicable pairs (view source)

Revision as of 16:19, 14 March 2024

8,875 bytes added ,  2 months ago
Add ABC
(Added Chipmunk Basic, Gambas, QBasic and True BASIC)
(Add ABC)
 
(25 intermediate revisions by 12 users not shown)
Line 439:
</pre>
 
=={{header|ABC}}==
<syntaxhighlight lang="abc">HOW TO RETURN proper.divisor.sum.table n:
PUT {} IN propdivs
FOR i IN {1..n}: PUT 1 IN propdivs[i]
FOR i IN {2..floor (n/2)}:
PUT i+i IN j
WHILE j<=n:
PUT propdivs[j] + i IN propdivs[j]
PUT i + j IN j
RETURN propdivs
 
PUT 20000 IN maximum
PUT proper.divisor.sum.table maximum IN propdivs
 
FOR cand IN {1..maximum}:
PUT propdivs[cand] IN other
IF cand<other<maximum AND propdivs[other]=cand:
WRITE cand, other/</syntaxhighlight>
{{out}}
<pre>220 284
1184 1210
2620 2924
5020 5564
6232 6368
10744 10856
12285 14595
17296 18416</pre>
=={{header|Action!}}==
Calculations on a real Atari 8-bit computer take quite long time. It is recommended to use an emulator capable with increasing speed of Atari CPU.
Line 538 ⟶ 565:
comment - return n mod m;
integer procedure mod(n, m);
value n, qm; integer n, m;
begin
mod := n - m * entier(n / m);
Line 611 ⟶ 638:
OD;
# find the amicable pairs up to 20 000 #
FOR p1 TO UPB pd sum - 1 DO
FORINT p2pd FROMsum p1 + 1 TO UPB= pd sum[ p1 DO];
IF pd sum[ p1 ]> = p2p1 AND pd sum[ p2 ]p1 <= p1UPB pd sum THEN
IF pd sum[ pd sum p1 ] = p1 THEN
print( ( whole( p1, -6 ), " and ", whole( p2, -6 ), " are an amicable pair", newline ) )
print( ( whole( p1, -6 ), " and ", whole( pd sum p1, -6 ), " are an amicable pair", newline ) )
FI
ODFI
OD
END
Line 630 ⟶ 658:
12285 and 14595 are an amicable pair
17296 and 18416 are an amicable pair
</pre>
 
=={{header|ALGOL W}}==
{{Trans|ALGOL 68}}
<syntaxhighlight lang="algolw">
begin % find amicable pairs p1, p2 where each is equal to the other's %
% proper divisor sum %
 
integer MAX_NUMBER;
MAX_NUMBER := 20000;
 
begin
integer array pdSum( 1 :: MAX_NUMBER ); % table of proper divisors %
for i := 1 until MAX_NUMBER do pdSum( i ) := 1;
for i := 2 until MAX_NUMBER do begin
for j := i + i step i until MAX_NUMBER do pdSum( j ) := pdSum( j ) + i
end for_i ;
 
% find the amicable pairs up to 20 000 %
for p1 := 1 until MAX_NUMBER - 1 do begin
integer pdSumP1;
pdSumP1 := pdSum( p1 );
if pdSumP1 > p1 and pdSumP1 <= MAX_NUMBER and pdSum( pdSumP1 ) = p1 then begin
write( i_w := 5, s_w := 0, p1, " and ", pdSumP1, " are an amicable pair" )
end if_pdSumP1_gt_p1_and_le_MAX_NUMBER
end for_p1
end
end.
</syntaxhighlight>
{{out}}
<pre>
220 and 284 are an amicable pair
1184 and 1210 are an amicable pair
2620 and 2924 are an amicable pair
5020 and 5564 are an amicable pair
6232 and 6368 are an amicable pair
10744 and 10856 are an amicable pair
12285 and 14595 are an amicable pair
17296 and 18416 are an amicable pair
</pre>
 
Line 2,031 ⟶ 2,098:
12285, 14595
17296, 18416</pre>
 
=={{header|EasyLang}}==
{{trans|Lua}}
<syntaxhighlight lang="easylang">
func sumdivs n .
sum = 1
for d = 2 to sqrt n
if n mod d = 0
sum += d + n div d
.
.
return sum
.
for n = 1 to 20000
m = sumdivs n
if m > n
if sumdivs m = n
print n & " " & m
.
.
.
</syntaxhighlight>
 
=={{header|EchoLisp}}==
Line 2,071 ⟶ 2,160:
=={{header|Elena}}==
{{trans|C#}}
ELENA 56.0x :
<syntaxhighlight lang="elena">import extensions;
import system'routines;
Line 2,080 ⟶ 2,169:
{
ProperDivisors
= Range.new(1,self / 2).filterBy::(n => self.mod:(n) == 0);
get AmicablePairs()
Line 2,086 ⟶ 2,175:
var divsums := Range
.new(0, self + 1)
.selectBy::(i => i.ProperDivisors.summarize(Integer.new()))
.toArray();
^ 1.repeatTill(divsums.Length)
.filterBy::(i)
{
var ii := i;
Line 2,097 ⟶ 2,186:
^ (i < sum) && (sum < divsums.Length) && (divsums[sum] == i)
}
.selectBy::(i => new { Item1 = i; Item2 = divsums[i]; })
}
}
Line 2,103 ⟶ 2,192:
public program()
{
N.AmicablePairs.forEach::(pair)
{
console.printLine(pair.Item1, " ", pair.Item2)
Line 2,129 ⟶ 2,218:
{
Enumerator<int> ProperDivisors
= new Range(1,self / 2).filterBy::(int n => self.mod:(n) == 0);
get AmicablePairs()
Line 2,135 ⟶ 2,224:
auto divsums := new List<int>(
cast Enumerator<int>(
new Range(0, self).selectBy::(int i => i.ProperDivisors.summarize(0))));
^ new Range(0, divsums.Length)
.filterBy::(int i)
{
auto sum := divsums[i];
^ (i < sum) && (sum < divsums.Length) && (divsums[sum] == i)
}
.selectBy::(int i => new Tuple<int,int>(i,divsums[i]));
}
}
Line 2,149 ⟶ 2,238:
public program()
{
N.AmicablePairs.forEach::(var Tuple<int,int> pair)
{
console.printLine(pair.Item1, " ", pair.Item2)
}
}</syntaxhighlight>
 
=== Alternative variant using yield enumerator ===
<syntaxhighlight lang="elena">import extensions;
Line 2,164 ⟶ 2,254:
{
Enumerator<int> function(int number)
= Range.new(1, number / 2).filterBy::(int n => number.mod:(n) == 0);
}
Line 2,178 ⟶ 2,268:
yieldable Tuple<int, int> next()
{
List<int> divsums := Range.new(0, max + 1).selectBy::(int i => ProperDivisors(i).summarize(0));
for (int i := 1,; i < divsums.Length,; i += 1)
{
int sum := divsums[i];
if(i < sum && sum <= divsums.Length && divsums[sum] == i) {
$yield: new Tuple<int, int>(i, sum);
}
};
Line 2,195 ⟶ 2,285:
{
auto e := new AmicablePairs(Limit);
for(auto pair := e.next(),; pair != nil)
{
console.printLine(pair.Item1, " ", pair.Item2)
Line 3,446 ⟶ 3,536:
 
=={{header|Lua}}==
Avoids unnecessary divisor sum calculations.<br>
0.02 of a second in 16 lines of code.
Runs in around 0.11 seconds on TIO.RUN.
The vital trick is to just set m to the sum of n's proper divisors each time. That way you only have to test the reverse, dividing your run time by half the loop limit (ie. 10,000)!
 
<syntaxhighlight lang="lua">function sumDivs (n)
local sum = 1
Line 3,475 ⟶ 3,566:
12285 14595
17296 18416
</pre>
 
Alternative version using a table of proper divisors, constructed without division/modulo.<br>
Runs is around 0.02 seconds on TIO.RUN.
<syntaxhighlight lang="lua">
MAX_NUMBER = 20000
sumDivs = {} -- table of proper divisors
for i = 1, MAX_NUMBER do sumDivs[ i ] = 1 end
for i = 2, MAX_NUMBER do
for j = i + i, MAX_NUMBER, i do
sumDivs[ j ] = sumDivs[ j ] + i
end
end
 
for n = 2, MAX_NUMBER do
m = sumDivs[n]
if m > n then
if sumDivs[m] == n then print(n, m) end
end
end
</syntaxhighlight>
 
{{out}}
<pre>
220 284
1184 1210
2620 2924
5020 5564
6232 6368
10744 10856
12285 14595
17296 18416
</pre>
 
=={{header|MiniScript}}==
{{Trans|ALGOL W}}
<syntaxhighlight lang="miniscript">
// find amicable pairs p1, p2 where each is equal to the other's proper divisor sum
 
MAX_NUMBER = 20000
pdSum = [1] * ( MAX_NUMBER + 1 ) // table of proper divisors
for i in range( 2, MAX_NUMBER )
for j in range( i + i, MAX_NUMBER, i )
pdSum[ j ] += i
end for
end for
// find the amicable pairs up to 20 000
ap = []
for p1 in range( 1, MAX_NUMBER - 1 )
pdSumP1 = pdSum[ p1 ]
if pdSumP1 > p1 and pdSumP1 <= MAX_NUMBER and pdSum[ pdSumP1 ] == p1 then
print str( p1 ) + " and " + str( pdSumP1 ) + " are an amicable pair"
end if
end for
</syntaxhighlight>
{{out}}
<pre>
220 and 284 are an amicable pair
1184 and 1210 are an amicable pair
2620 and 2924 are an amicable pair
5020 and 5564 are an amicable pair
6232 and 6368 are an amicable pair
10744 and 10856 are an amicable pair
12285 and 14595 are an amicable pair
17296 and 18416 are an amicable pair
</pre>
 
Line 4,834 ⟶ 4,990:
 
==={{header|PL/I-80}}===
====Computing the divisor sum on the fly====
Rather than populating an array with the sum of the proper divisors and then searching, the approach here calculates them on the fly as needed, saving memory, and avoiding a noticeable lag on program startup on the ancient systems that hosted PL/I-80.
<syntaxhighlight lang="pl/i">
Line 4,897 ⟶ 5,054:
8 pairs were found
</pre>
 
====Without using division/modulo====
 
<syntaxhighlight lang="pl/i">
amicable: procedure options (main);
 
%replace
search_limit by 20000;
 
dcl sumf( 1 : search_limit ) fixed bin;
dcl (a, b, found) fixed bin;
 
put skip list ('Searching for amicable pairs up to ');
put edit (search_limit) (f(5));
 
do a = 1 to search_limit; sumf( a ) = 1; end;
do a = 2 to search_limit;
do b = a + a to search_limit by a;
sumf( b ) = sumf( b ) + a;
end;
end;
 
found = 0;
do a = 2 to search_limit;
b = sumf(a);
if (b > a) then
do;
if (sumf(b) = a) then
do;
found = found + 1;
put skip edit (a,b) (f(7));
end;
end;
end;
put skip list (found, ' pairs were found');
stop;
 
end amicable;
</syntaxhighlight>
 
{{out}}
Same as the other PLI-80 sample.
 
=={{header|PL/M}}==
Line 4,931 ⟶ 5,130:
/* TEST EACH PAIR */
DO I=2 TO 20$000;
DOJ J= DIVSUM(I+1 TO 20$000);
IF J > I IFAND DIV$SUM(I)=J AND<= DIV20$SUM(J)=I000 THEN DO;
IF DIV$SUM(J) = I THEN DO;
CALL PRINT$NUMBER(I);
CALL PRINT(.', $');
Line 5,702 ⟶ 5,902:
return sum
</syntaxhighlight>
 
=={{header|RPL}}==
{{works with|HP|49}}
≪ {}
2 ROT '''FOR''' j
'''IF''' DUP j POS NOT '''THEN''' <span style="color:grey">@ avoiding duplicates</span>
j DIVIS ∑LIST j - DUP
'''IF''' DUP 1 ≠ OVER j ≠ AND '''THEN'''
'''IF''' DUP DIVIS ∑LIST SWAP - j == '''THEN'''
+ j +
'''ELSE''' DROP '''END'''
'''ELSE''' DROP2 '''END'''
'''END'''
'''NEXT'''
{}
1 3 PICK SIZE '''FOR''' j <span style="color:grey">@ formatting the list for output</span>
OVER j DUP 1 + SUB REVLIST 1 →LIST +
2 '''STEP''' NIP
≫ '<span style="color:blue">TASK</span>' STO
 
200000 <span style="color:blue">TASK</span>
{{out}}
<pre>
1: {{220 284} {1184 1210} {2620 2924} {5020 5564} {6232 6368} {10744 10856} {12285 14595} {17296 18416}}
</pre>
 
=={{header|Ruby}}==
Line 5,748 ⟶ 5,973:
=={{header|Rust}}==
 
<syntaxhighlight lang="rust">fn sum_of_divisors(val: u32) -> u32 {
fn sum_of_divisors(val: u32) -> u32 {
(1..val/2+1).filter(|n| val % n == 0)
.fold(0, |sum, n| sum + n)
Line 5,763 ⟶ 5,989:
}
}</syntaxhighlight>
 
{{out}}
<pre>
Line 5,773 ⟶ 6,000:
14595 12285
18416 17296
</pre>
 
{{trans|Python}}
 
<syntaxhighlight lang="rust">
fn main() {
const RANGE_MAX: u32 = 20_000;
let proper_divs = |n: u32| -> Vec<u32> {
(1..=(n + 1) / 2).filter(|&x| n % x == 0).collect()
};
let n2d: Vec<u32> = (1..=RANGE_MAX).map(|n| proper_divs(n).iter().sum()).collect();
for (n, &div_sum) in n2d.iter().enumerate() {
let n = n as u32 + 1;
if n < div_sum && div_sum <= RANGE_MAX && n2d[div_sum as usize - 1] == n {
println!("Amicable pair: {} and {} with proper divisors:", n, div_sum);
println!(" {:?}", proper_divs(n));
println!(" {:?}", proper_divs(div_sum));
}
}
}
</syntaxhighlight>
 
{{out}}
<pre>
Amicable pair: 220 and 284 with proper divisors:
[1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110]
[1, 2, 4, 71, 142]
Amicable pair: 1184 and 1210 with proper divisors:
[1, 2, 4, 8, 16, 32, 37, 74, 148, 296, 592]
[1, 2, 5, 10, 11, 22, 55, 110, 121, 242, 605]
Amicable pair: 2620 and 2924 with proper divisors:
[1, 2, 4, 5, 10, 20, 131, 262, 524, 655, 1310]
[1, 2, 4, 17, 34, 43, 68, 86, 172, 731, 1462]
Amicable pair: 5020 and 5564 with proper divisors:
[1, 2, 4, 5, 10, 20, 251, 502, 1004, 1255, 2510]
[1, 2, 4, 13, 26, 52, 107, 214, 428, 1391, 2782]
Amicable pair: 6232 and 6368 with proper divisors:
[1, 2, 4, 8, 19, 38, 41, 76, 82, 152, 164, 328, 779, 1558, 3116]
[1, 2, 4, 8, 16, 32, 199, 398, 796, 1592, 3184]
Amicable pair: 10744 and 10856 with proper divisors:
[1, 2, 4, 8, 17, 34, 68, 79, 136, 158, 316, 632, 1343, 2686, 5372]
[1, 2, 4, 8, 23, 46, 59, 92, 118, 184, 236, 472, 1357, 2714, 5428]
Amicable pair: 12285 and 14595 with proper divisors:
[1, 3, 5, 7, 9, 13, 15, 21, 27, 35, 39, 45, 63, 65, 91, 105, 117, 135, 189, 195, 273, 315, 351, 455, 585, 819, 945, 1365, 1755, 2457, 4095]
[1, 3, 5, 7, 15, 21, 35, 105, 139, 417, 695, 973, 2085, 2919, 4865]
Amicable pair: 17296 and 18416 with proper divisors:
[1, 2, 4, 8, 16, 23, 46, 47, 92, 94, 184, 188, 368, 376, 752, 1081, 2162, 4324, 8648]
[1, 2, 4, 8, 16, 1151, 2302, 4604, 9208]
</pre>
 
=={{header|Sage}}==
<syntaxhighlight lang="Sage">
# Define the sum of proper divisors function
def sum_of_proper_divisors(n):
return sum(divisors(n)) - n
 
# Iterate over the desired range
for x in range(1, 20001):
y = sum_of_proper_divisors(x)
if y > x:
if x == sum_of_proper_divisors(y):
print(f"{x} {y}")
</syntaxhighlight>
{{out}}
<pre>
220 284
1184 1210
2620 2924
5020 5564
6232 6368
10744 10856
12285 14595
17296 18416
</pre>
 
Line 5,781 ⟶ 6,085:
$constant search_limit = 20000
 
var a, b, count = integer
rem - return p mod q
dim integer sumf(search_limit)
function mod(p, q = integer) = integer
end = p - q * (p / q)
 
print "Searching up to"; search_limit; " for amicable pairs:"
rem - return sum of the proper divisors of n
 
function sumf(n = integer) = integer
rem - set up the table of proper divisor sums
var f1, f2, sum = integer
 
sum = 1
for a = 1 to search_limit
f1 = 2
while (f1 * f1sumf(a) <= n do1
next a
begin
 
if mod(n, f1) = 0 then
for a = 2 to search_limit
b = a + a
while (b > 0) and (b <= search_limit) do
begin
sum sumf(b) = sumsumf(b) + f1a
f2 b = nb /+ f1a
if f2 > f1 then sum = sum + f2
end
next a
f1 = f1 + 1
 
end
rem - search for pairs using the table
end = sum
 
rem - main program begins here
var a, b, count = integer
print "Searching up to"; search_limit; " for amicable pairs:"
count = 0
for a = 2 to search_limit do
b = sumf(a)
if (b > a) and (b < search_limit) then
if a = sumf(b) then
begin
Line 5,907 ⟶ 6,209:
Amicable pair: 17296 18416
</pre>
 
=={{header|SETL}}==
<syntaxhighlight lang="setl">program amicable_pairs;
p := propDivSums(20000);
 
loop for [n,m] in p | n = p(p(n)) and n<m do
print([n,m]);
end loop;
 
proc propDivSums(n);
divs := {};
loop for i in [1..n] do
loop for j in [i*2, i*3..n] do
divs(j) +:= i;
end loop;
end loop;
return divs;
end proc;
end program;</syntaxhighlight>
{{out}}
<pre>[220 284]
[1184 1210]
[2620 2924]
[5020 5564]
[6232 6368]
[10744 10856]
[12285 14595]
[17296 18416]</pre>
 
=={{header|Sidef}}==
Line 6,370 ⟶ 6,700:
=={{header|V (Vlang)}}==
{{trans|Go}}
<syntaxhighlight lang="goGo">fn pfac_sum(i int) int {
fn pfac_sum(i int) int {
mut sum := 0
for p := 1; p <= i / 2; p++{
if i % p == 0 {
sum += p
}
Line 6,389 ⟶ 6,720:
}
}
}
}</syntaxhighlight>
</syntaxhighlight>
 
{{output}}
Line 6,402 ⟶ 6,734:
12285 and 14595
17296 and 18416
 
</pre>
 
Line 6,442 ⟶ 6,773:
{{libheader|Wren-fmt}}
{{libheader|Wren-math}}
<syntaxhighlight lang="ecmascriptwren">import "./fmt" for Fmt
import "./math" for Int, Nums
 
var a = List.filled(20000, 0)
Line 6,451 ⟶ 6,782:
var m = a[n]
if (m > n && m < 20000 && n == a[m]) {
SystemFmt.print(" %(Fmt.d(5, n))$5d and %(Fmt.d(5$5d", n, m))")
}
}</syntaxhighlight>
Line 6,533 ⟶ 6,864:
 
print : print peek("millisrunning"), " ms"</syntaxhighlight>
 
=={{header|zkl}}==
Slooooow
<syntaxhighlight lang="zkl">fcn properDivs(n){ [1.. (n + 1)/2 + 1].filter('wrap(x){ n%x==0 and n!=x }) }
const N=20000;
sums:=[1..N].pump(T(-1),fcn(n){ properDivs(n).sum(0) });
[0..].zip(sums).filter('wrap([(n,s)]){ (n<s<=N) and sums[s]==n }).println();</syntaxhighlight>
{{out}}
<pre>
L(L(220,284),L(1184,1210),L(2620,2924),L(5020,5564),L(6232,6368),L(10744,10856),L(12285,14595),L(17296,18416))
</pre>
 
=={{header|Zig}}==
Line 6,588 ⟶ 6,908:
12285, 14595
17296, 18416</pre>
 
=={{header|zkl}}==
Slooooow
<syntaxhighlight lang="zkl">fcn properDivs(n){ [1.. (n + 1)/2 + 1].filter('wrap(x){ n%x==0 and n!=x }) }
const N=20000;
sums:=[1..N].pump(T(-1),fcn(n){ properDivs(n).sum(0) });
[0..].zip(sums).filter('wrap([(n,s)]){ (n<s<=N) and sums[s]==n }).println();</syntaxhighlight>
{{out}}
<pre>
L(L(220,284),L(1184,1210),L(2620,2924),L(5020,5564),L(6232,6368),L(10744,10856),L(12285,14595),L(17296,18416))
</pre>
 
=={{header|ZX Spectrum Basic}}==
Not a robot
2,100

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/346896...361892"