Rosetta Code

Amicable pairs: Difference between revisions

Page Discussion

Amicable pairs (view source)

Revision as of 16:19, 14 March 2024

13,705 bytes added ,  2 months ago
Add ABC
(Add ABC)
 
(41 intermediate revisions by 20 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 601 ⟶ 628:
 
=={{header|ALGOL 68}}==
<syntaxhighlight lang="algol68"># returns the sum of the proper divisors of n #
BEGIN # find amicable pairs p1, p2 where each is equal to the other's proper divisor sum #
# if n = 1, 0 or -1, we return 0 #
[ 1 : 20 000 ]INT pd sum; # table of proper divisors #
PROC sum proper divisors = ( INT n )INT:
FOR n TO UPB pd sum DO pd sum[ n ] := 1 OD;
BEGIN
FOR i FROM 2 TO INTUPB resultpd := 0;sum
DO INTFOR absj nFROM =i ABS+ n;i BY i TO UPB pd sum DO
IF abs n >pd 1sum[ THENj ] +:= i
OD
FOR d FROM ENTIER sqrt( abs n ) BY -1 TO 2 DO
OD;
IF abs n MOD d = 0 THEN
# find the amicable pairs up to 20 000 # found another divisor #
FOR p1 TO UPB pd sum - 1 result +:= d;DO
INT pd sum p1 = pd sum[ p1 IF d * d /= n THEN];
IF pd sum p1 > p1 AND pd sum p1 <= UPB pd sum # include the other divisor #THEN
IF pd sum[ pd sum p1 ] result +:= n OVERp1 dTHEN
print( ( whole( p1, -6 ), " and ", whole( pd sum p1, -6 ), " are an amicable pair", newline ) )
FI
FI
OD;
# 1 is always a proper divisor of numbers > 1 #
result +:= 1
FI;
result
END # sum proper divisors # ;
 
# construct a table of the sum of the proper divisors of numbers #
# up to 20 000 #
INT max number = 20 000;
[ 1 : max number ]INT proper divisor sum;
FOR n TO UPB proper divisor sum DO proper divisor sum[ n ] := sum proper divisors( n ) OD;
 
# returns TRUE if n1 and n2 are an amicable pair FALSE otherwise #
# n1 and n2 are amicable if the sum of the proper diviors #
# n1 = n2 and the sum of the proper divisors of n2 = n1 #
PROC is an amicable pair = ( INT n1, n2 )BOOL:
( proper divisor sum[ n1 ] = n2 AND proper divisor sum[ n2 ] = n1 );
 
# find the amicable pairs up to 20 000 #
FOR p1 TO max number DO
FOR p2 FROM p1 + 1 TO max number DO
IF is an amicable pair( p1, p2 ) THEN
print( ( whole( p1, -6 ), " and ", whole( p2, -6 ), " are an amicable pair", newline ) )
FI
OD
END
OD</syntaxhighlight>
</syntaxhighlight>
{{out}}
<pre>
Line 656 ⟶ 660:
</pre>
 
=={{header|ANSIALGOL Standard BASICW}}==
{{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;
{{Trans|GFA Basic}}
MAX_NUMBER := 20000;
 
begin
<syntaxhighlight lang="ansi standard basic">100 DECLARE EXTERNAL FUNCTION sum_proper_divisors
integer array pdSum( 1 :: MAX_NUMBER ); % table of proper divisors %
110 CLEAR
for i := 1 until MAX_NUMBER do pdSum( i ) := 1;
120 !
130 DIM f(20001) !for sumi of:= proper2 factorsuntil forMAX_NUMBER eachdo nbegin
for j := i + i step i until MAX_NUMBER do pdSum( j ) := pdSum( j ) + i
140 FOR i=1 TO 20000
end for_i ;
150 LET f(i)=sum_proper_divisors(i)
 
160 NEXT i
% find the amicable pairs up to 20 000 %
170 ! look for pairs
for p1 := 1 until MAX_NUMBER - 1 do begin
180 FOR i=1 TO 20000
integer pdSumP1;
190 FOR j=i+1 TO 20000
200 IF f(i)=j AND i pdSumP1 :=f pdSum(j) THENp1 );
if pdSumP1 > p1 and pdSumP1 <= MAX_NUMBER and pdSum( pdSumP1 ) = p1 then begin
210 PRINT "Amicable pair ";i;" ";j
write( i_w := 5, s_w := 0, p1, " and ", pdSumP1, " are an amicable pair" )
220 END IF
end if_pdSumP1_gt_p1_and_le_MAX_NUMBER
230 NEXT j
end for_p1
240 NEXT i
end
250 !
end.
260 PRINT
</syntaxhighlight>
270 PRINT "-- found all amicable pairs"
{{out}}
280 END
<pre>
290 !
220 and 284 are an amicable pair
300 ! Compute the sum of proper divisors of given number
1184 and 1210 are an amicable pair
310 !
2620 and 2924 are an amicable pair
320 EXTERNAL FUNCTION sum_proper_divisors(n)
5020 and 5564 are an amicable pair
330 !
6232 and 6368 are an amicable pair
340 IF n>1 THEN ! n must be 2 or larger
10744 and 10856 are an amicable pair
350 LET sum=1 ! start with 1
12285 and 14595 are an amicable pair
360 LET root=SQR(n) ! note that root is an integer
17296 and 18416 are an amicable pair
370 ! check possible factors, up to sqrt
</pre>
380 FOR i=2 TO root
390 IF MOD(n,i)=0 THEN
400 LET sum=sum+i ! i is a factor
410 IF i*i<>n THEN ! check i is not actual square root of n
420 LET sum=sum+n/i ! so n/i will also be a factor
430 END IF
440 END IF
450 NEXT i
460 END IF
470 LET sum_proper_divisors = sum
480 END FUNCTION</syntaxhighlight>
 
=={{header|AppleScript}}==
===Functional===
 
{{Trans|JavaScript}}
 
Line 850 ⟶ 849:
<syntaxhighlight lang="applescript">{{220, 284}, {1184, 1210}, {2620, 2924}, {5020, 5564},
{6232, 6368}, {10744, 10856}, {12285, 14595}, {17296, 18416}}</syntaxhighlight>
----
===Straightforward===
… and about 55 times as fast as the above.
<syntaxhighlight lang="applescript">on properDivisors(n)
set output to {}
if (n > 1) then
set sqrt to n ^ 0.5
set limit to sqrt div 1
if (limit = sqrt) then
set end of output to limit
set limit to limit - 1
end if
repeat with i from limit to 2 by -1
if (n mod i is 0) then
set beginning of output to i
set end of output to n div i
end if
end repeat
set beginning of output to 1
end if
return output
end properDivisors
 
on sumList(listOfNumbers)
script o
property l : listOfNumbers
end script
set sum to 0
repeat with n in o's l
set sum to sum + n
end repeat
return sum
end sumList
 
on amicablePairsBelow(limitPlus1)
script o
property pdSums : {missing value} -- Sums of proper divisors. (Dummy item for 1's.)
end script
set limit to limitPlus1 - 1
repeat with n from 2 to limit
set end of o's pdSums to sumList(properDivisors(n))
end repeat
set output to {}
repeat with n1 from 2 to (limit - 1)
set n2 to o's pdSums's item n1
if ((n1 < n2) and (n2 < limitPlus1) and (o's pdSums's item n2 = n1)) then ¬
set end of output to {n1, n2}
end repeat
return output
end amicablePairsBelow
 
on join(lst, delim)
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to delim
set txt to lst as text
set AppleScript's text item delimiters to astid
return txt
end join
 
on task()
set output to amicablePairsBelow(20000)
repeat with thisPair in output
set thisPair's contents to join(thisPair, " & ")
end repeat
return join(output, linefeed)
end task
 
task()</syntaxhighlight>
 
{{output}}
<syntaxhighlight lang="applescript">"220 & 284
1184 & 1210
2620 & 2924
5020 & 5564
6232 & 6368
10744 & 10856
12285 & 14595
17296 & 18416"</syntaxhighlight>
 
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi <br> or android 32 bits with application Termux}}
Line 1,272 ⟶ 1,355:
 
 
=={{header|BASIC256BASIC}}==
==={{header|ANSI BASIC}}===
{{trans|GFA Basic}}
{{works with|Decimal BASIC}}
<syntaxhighlight lang="basic">100 DECLARE EXTERNAL FUNCTION sum_proper_divisors
110 CLEAR
120 !
130 DIM f(20001) ! sum of proper factors for each n
140 FOR i=1 TO 20000
150 LET f(i)=sum_proper_divisors(i)
160 NEXT i
170 ! look for pairs
180 FOR i=1 TO 20000
190 FOR j=i+1 TO 20000
200 IF f(i)=j AND i=f(j) THEN
210 PRINT "Amicable pair ";i;" ";j
220 END IF
230 NEXT j
240 NEXT i
250 !
260 PRINT
270 PRINT "-- found all amicable pairs"
280 END
290 !
300 ! Compute the sum of proper divisors of given number
310 !
320 EXTERNAL FUNCTION sum_proper_divisors(n)
330 !
340 IF n>1 THEN ! n must be 2 or larger
350 LET sum=1 ! start with 1
360 LET root=SQR(n) ! note that root is an integer
370 ! check possible factors, up to sqrt
380 FOR i=2 TO root
390 IF MOD(n,i)=0 THEN
400 LET sum=sum+i ! i is a factor
410 IF i*i<>n THEN ! check i is not actual square root of n
420 LET sum=sum+n/i ! so n/i will also be a factor
430 END IF
440 END IF
450 NEXT i
460 END IF
470 LET sum_proper_divisors = sum
480 END FUNCTION</syntaxhighlight>
{{out}}
<pre>
Amicable pair 220 284
Amicable pair 1184 1210
Amicable pair 2620 2924
Amicable pair 5020 5564
Amicable pair 6232 6368
Amicable pair 10744 10856
Amicable pair 12285 14595
Amicable pair 17296 18416
 
-- found all amicable pairs
</pre>
 
==={{header|BASIC256}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="basic256">function SumProperDivisors(number)
Line 1,311 ⟶ 1,451:
17296 and 18416</pre>
 
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
<syntaxhighlight lang="qbasic">100 cls : rem 10 HOME for Applesoft BASIC
110 print "The pairs of amicable numbers below 20,000 are :"
120 print
130 size = 18500
140 for n = 1 to size
150 m = amicable(n)
160 if m > n and amicable(m) = n then
170 print using "#####";n;
180 print " and ";
190 print using "#####";m
200 endif
210 next
220 end
230 function amicable(nr)
240 suma = 1
250 for d = 2 to sqr(nr)
260 if nr mod d = 0 then suma = suma+d+nr/d
270 next
280 amicable = suma
290 end function</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
 
==={{header|Gambas}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="vbnet">Public sum[19999] As Integer
 
Public Sub Main()
Dim n As Integer, f As Integer
For n = 0 To 19998
sum[n] = SumProperDivisors(n)
Next
Print "The pairs of amicable numbers below 20,000 are :\n"
For n = 0 To 19998
' f = SumProperDivisors(n)
f = sum[n]
If f <= n Or f < 1 Or f > 19999 Then Continue
If f = sum[n] And n = sum[f] Then
Print Format$(Str$(n), "#####"); " And "; Format$(Str$(sum[n]), "#####")
End If
Next
End
 
Function SumProperDivisors(number As Integer) As Integer
If number < 2 Then Return 0
Dim sum As Integer = 0
For i As Integer = 1 To number \ 2
If number Mod i = 0 Then sum += i
Next
Return sum
End Function</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
 
==={{header|QBasic}}===
{{works with|QBasic|1.1}}
{{works with|QuickBasic|4.5}}
<syntaxhighlight lang="qbasic">FUNCTION amicable (nr)
suma = 1
FOR d = 2 TO SQR(nr)
IF nr MOD d = 0 THEN suma = suma + d + nr / d
NEXT
amicable = suma
END FUNCTION
 
PRINT "The pairs of amicable numbers below 20,000 are :"
PRINT
 
size = 18500
FOR n = 1 TO size
m = amicable(n)
IF m > n AND amicable(m) = n THEN
PRINT USING "##### and #####"; n; m
END IF
NEXT
END</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
 
==={{header|True BASIC}}===
<syntaxhighlight lang="qbasic">FUNCTION amicable(nr)
LET suma = 1
FOR d = 2 TO SQR(nr)
IF REMAINDER(nr, d) = 0 THEN
LET suma = suma + d + nr / d
END IF
NEXT d
LET amicable = suma
END FUNCTION
 
PRINT "The pairs of amicable numbers below 20,000 are :"
PRINT
 
LET size = 18500
FOR n = 1 TO size
LET m = amicable(n)
IF m > n AND amicable(m) = n THEN PRINT USING "##### and #####": n, m
NEXT n
END</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
 
=={{header|BCPL}}==
Line 1,848 ⟶ 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 1,888 ⟶ 2,160:
=={{header|Elena}}==
{{trans|C#}}
ELENA 56.0x :
<syntaxhighlight lang="elena">import extensions;
import system'routines;
Line 1,897 ⟶ 2,169:
{
ProperDivisors
= Range.new(1,self / 2).filterBy::(n => self.mod:(n) == 0);
get AmicablePairs()
Line 1,903 ⟶ 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 1,914 ⟶ 2,186:
^ (i < sum) && (sum < divsums.Length) && (divsums[sum] == i)
}
.selectBy::(i => new { Item1 = i; Item2 = divsums[i]; })
}
}
Line 1,920 ⟶ 2,192:
public program()
{
N.AmicablePairs.forEach::(pair)
{
console.printLine(pair.Item1, " ", pair.Item2)
Line 1,946 ⟶ 2,218:
{
Enumerator<int> ProperDivisors
= new Range(1,self / 2).filterBy::(int n => self.mod:(n) == 0);
get AmicablePairs()
Line 1,952 ⟶ 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 1,966 ⟶ 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 1,981 ⟶ 2,254:
{
Enumerator<int> function(int number)
= Range.new(1, number / 2).filterBy::(int n => number.mod:(n) == 0);
}
Line 1,995 ⟶ 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,012 ⟶ 2,285:
{
auto e := new AmicablePairs(Limit);
for(auto pair := e.next(),; pair != nil)
{
console.printLine(pair.Item1, " ", pair.Item2)
Line 2,623 ⟶ 2,896:
in map (fn (np,mp) => [#1 np, #1 mp]) amicable
</syntaxhighlight>
 
 
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
local fn Sigma( n as long ) as long
long i, root, sum = 1
if n == 1 then exit fn = 0
root = sqr(n)
for i = 2 to root
if ( n mod i == 0 ) then sum += i + n/i
next
if root * root == n then sum -= root
end fn = sum
 
void local fn CalculateAmicablePairs( limit as long )
long i, m
printf @"\nAmicable pairs through %ld are:\n", limit
for i = 2 to limit
m = fn Sigma(i)
if ( m > i )
if ( fn Sigma(m) == i ) then printf @"%6ld and %ld", i, m
end if
next
end fn
 
CFTimeInterval t
t = fn CACurrentMediaTime
fn CalculateAmicablePairs( 20000 )
printf @"\nCompute time: %.3f ms",(fn CACurrentMediaTime-t)*1000
 
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
Amicable pairs through 20000 are:
 
220 and 284
1184 and 1210
2620 and 2924
5020 and 5564
6232 and 6368
10744 and 10856
12285 and 14595
17296 and 18416
 
Compute time: 28.701 ms
</pre>
 
 
=={{header|GFA Basic}}==
Line 2,780 ⟶ 3,103:
<syntaxhighlight lang="j">factors=: [: /:~@, */&>@{@((^ i.@>:)&.>/)@q:~&__
properDivisors=: factors -. -.&1</syntaxhighlight>
 
(properDivisors is all factors except "the number itself when that number is greater than 1".)
 
Amicable pairs:
 
<syntaxhighlight lang="j"> 1 + 0 20000($ #: I.@,) ,(</~@i.@# * (* |:))(=/ +/@properDivisors@>) 1 + i.20000
220 284
1184 1210
Line 2,792 ⟶ 3,117:
12285 14595
17296 18416</syntaxhighlight>
 
Explanation: We generate sequence of positive integers, starting from 1, and compare each of them to the sum of proper divisors of each of them. Then we fold this comparison diagonally, keeping only the values where the comparison was equal both ways and the smaller value appears before the larger value. Finally, indices into true values give us our amicable pairs.
 
=={{header|Java}}==
Line 3,071 ⟶ 3,398:
 
amicables()
</syntaxhighlight>{{out}}
 
{{out}}
Note, the output is ''not'' ordered by the first figure, see e.g. counters 11, 15, ..., 139, 141, etc.
<pre>
Amicable pairs not greater than 20000000
Line 3,090 ⟶ 3,420:
15 => 100485, 124155
16 => 122265, 139815
[...]
17 => 141664, 153176
18 => 142310, 168730
19 => 171856, 176336
20 => 176272, 180848
21 => 196724, 202444
22 => 185368, 203432
23 => 280540, 365084
24 => 308620, 389924
25 => 356408, 399592
26 => 319550, 430402
27 => 437456, 455344
28 => 469028, 486178
29 => 503056, 514736
30 => 522405, 525915
31 => 643336, 652664
32 => 600392, 669688
33 => 609928, 686072
34 => 624184, 691256
35 => 635624, 712216
36 => 667964, 783556
37 => 726104, 796696
38 => 802725, 863835
39 => 879712, 901424
40 => 898216, 980984
41 => 998104, 1043096
42 => 1077890, 1099390
43 => 947835, 1125765
44 => 1154450, 1189150
45 => 1185376, 1286744
46 => 1156870, 1292570
47 => 1280565, 1340235
48 => 1175265, 1438983
49 => 1392368, 1464592
50 => 1328470, 1483850
51 => 1358595, 1486845
52 => 1511930, 1598470
53 => 1466150, 1747930
54 => 1468324, 1749212
55 => 1798875, 1870245
56 => 1669910, 2062570
57 => 2082464, 2090656
58 => 2236570, 2429030
59 => 2723792, 2874064
60 => 2739704, 2928136
61 => 2652728, 2941672
62 => 2802416, 2947216
63 => 2728726, 3077354
64 => 2803580, 3716164
65 => 3276856, 3721544
66 => 3606850, 3892670
67 => 3805264, 4006736
68 => 3786904, 4300136
69 => 4238984, 4314616
70 => 4259750, 4445050
71 => 4246130, 4488910
72 => 4482765, 5120595
73 => 4604776, 5162744
74 => 5459176, 5495264
75 => 5123090, 5504110
76 => 5357625, 5684679
77 => 5232010, 5799542
78 => 5385310, 5812130
79 => 5147032, 5843048
80 => 5730615, 6088905
81 => 4532710, 6135962
82 => 5726072, 6369928
83 => 6329416, 6371384
84 => 6377175, 6680025
85 => 6993610, 7158710
86 => 6955216, 7418864
87 => 7275532, 7471508
88 => 5864660, 7489324
89 => 7489112, 7674088
90 => 7677248, 7684672
91 => 7800544, 7916696
92 => 7850512, 8052488
93 => 7288930, 8221598
94 => 8262136, 8369864
95 => 7577350, 8493050
96 => 9363584, 9437056
97 => 9071685, 9498555
98 => 9199496, 9592504
99 => 8619765, 9627915
100 => 9339704, 9892936
101 => 9660950, 10025290
102 => 8826070, 10043690
103 => 10254970, 10273670
104 => 8666860, 10638356
105 => 9206925, 10791795
106 => 10572550, 10854650
107 => 8754130, 10893230
108 => 10533296, 10949704
109 => 9491625, 10950615
110 => 9478910, 11049730
111 => 10596368, 11199112
112 => 9773505, 11791935
113 => 11498355, 12024045
114 => 10992735, 12070305
115 => 11252648, 12101272
116 => 11545616, 12247504
117 => 11693290, 12361622
118 => 12397552, 13136528
119 => 11173460, 13212076
120 => 11905504, 13337336
121 => 13921528, 13985672
122 => 10634085, 14084763
123 => 12707704, 14236136
124 => 13813150, 14310050
125 => 14311688, 14718712
126 => 15002464, 15334304
127 => 13671735, 15877065
128 => 14443730, 15882670
129 => 16137628, 16150628
130 => 15363832, 16517768
131 => 14654150, 16817050
132 => 15938055, 17308665
133 => 17257695, 17578785
134 => 17908064, 18017056
135 => 14426230, 18087818
136 => 18056312, 18166888
137 => 17041010, 19150222
138 => 18655744, 19154336
139 => 16871582, 19325698
140 => 17844255, 19895265
141 => 17754165, 19985355
</pre>
 
 
===Alternative===
 
Using the <code>factor()</code> function from the <code>Primes</code> package allows for a quicker calculation, especially when it comes to big numbers. Here we use a busy one-liner with an iterator. The following code prints the amicable pairs in ''ascending order'' and also prints the sum of the amicable pair and the cumulative sum of all pairs found so far; this allows to check results, when solving [https://projecteuler.net/problem=21 Project Euler problem #21].
 
<syntaxhighlight lang="julia">
using Primes
 
function amicable_numbers(max::Integer = 200_000_000)
 
function sum_proper_divisors(n::Integer)
sum(vec(map(prod, Iterators.product((p.^(0:m) for (p, m) in factor(n))...)))) - n
end
 
count = 0
cumsum = 0
 
println("count, a, b, a+b, Sum(a+b)")
 
for a in 2:max
isprime(a) && continue
b = sum_proper_divisors(a)
if a < b && sum_proper_divisors(b) == a
count += 1
sumab = a + b
cumsum += sumab
println("$count, $a, $b, $sumab, $cumsum")
end
end
end
 
amicable_numbers()
</syntaxhighlight>
 
{{out}}
<pre>
count, a, b, a+b, Sum(a+b)
1, 220, 284, 504, 504
2, 1184, 1210, 2394, 2898
3, 2620, 2924, 5544, 8442
4, 5020, 5564, 10584, 19026
5, 6232, 6368, 12600, 31626
6, 10744, 10856, 21600, 53226
7, 12285, 14595, 26880, 80106
8, 17296, 18416, 35712, 115818
9, 63020, 76084, 139104, 254922
10, 66928, 66992, 133920, 388842
11, 67095, 71145, 138240, 527082
12, 69615, 87633, 157248, 684330
13, 79750, 88730, 168480, 852810
14, 100485, 124155, 224640, 1077450
15, 122265, 139815, 262080, 1339530
16, 122368, 123152, 245520, 1585050
[...]
300, 189406984, 203592056, 392999040, 31530421032
301, 190888155, 194594085, 385482240, 31915903272
302, 195857415, 196214265, 392071680, 32307974952
303, 196421715, 224703405, 421125120, 32729100072
304, 199432948, 213484172, 412917120, 33142017192
</pre>
 
Line 3,265 ⟶ 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,294 ⟶ 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,338 ⟶ 4,675:
 
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #004080008080;">integerwith</span> <span style="color: #000000008080;">njavascript_semantics</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">20000</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">m</span><span style="color: #0000FF;"><</span><span style="color: #000000;">n</span> <span style="color: #008080;">and</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?{</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
Line 4,653 ⟶ 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,716 ⟶ 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,750 ⟶ 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,521 ⟶ 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,567 ⟶ 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,582 ⟶ 5,989:
}
}</syntaxhighlight>
 
{{out}}
<pre>
Line 5,592 ⟶ 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,600 ⟶ 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,726 ⟶ 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,187 ⟶ 6,698:
Execution Time: 162 seconds</pre>
 
=={{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,208 ⟶ 6,720:
}
}
}
}</syntaxhighlight>
</syntaxhighlight>
 
{{output}}
Line 6,221 ⟶ 6,734:
12285 and 14595
17296 and 18416
 
</pre>
 
=={{header|VTL-2}}==
<syntaxhighlight lang="vtl2">10 M=20000
20 I=1
30 :I)=1
40 I=I+1
50 #=M>I*30
60 I=2
70 J=I+I
80 :J)=:J)+I
90 J=J+I
100 #=M>J*80
110 I=I+1
120 #=(M/2)>I*70
130 I=1
140 J=:I)
150 #=(I<J)*I=:J)*190
160 I=I+1
170 #=M>I*140
180 #=999
190 ?=I
200 $=9
210 ?=J
220 ?=""
230 #=!</syntaxhighlight>
{{out}}
<pre>220 284
1184 1210
2620 2924
5020 5564
6232 6368
10744 10856
12285 14595
17296 18416</pre>
 
=={{header|Wren}}==
{{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,237 ⟶ 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,319 ⟶ 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,374 ⟶ 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,094

edits

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