Amicable pairs: Difference between revisions
Content deleted Content added
No edit summary |
Not a robot (talk | contribs) Add ABC |
||
(55 intermediate revisions by 23 users not shown) | |||
Line 21:
=={{header|11l}}==
<
R I n < 2 {0} E sum((1 .. n I/ 2).filter(it -> (@n % it) == 0))
Line 27:
V m = sum_proper_divisors(n)
I m > n & sum_proper_divisors(m) == n
print(n"\t"m)</
=={{header|8080 Assembly}}==
<
;;; Calculate proper divisors of 2..20000
lxi h,pdiv + 4 ; 2 bytes per entry
Line 151:
nbuf: db ' $'
nl: db 13,10,'$'
pdiv: equ $ ; base</
{{out}}
<pre>220 284
Line 163:
=={{header|8086 Assembly}}==
<
cpu 8086
org 100h
Line 252:
nbuf: db ' $'
nl: db 13,10,'$'
final: equ $</
{{out}}
<pre>220 284
Line 264:
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits <br> or android 64 bits with application Termux }}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program amicable64.s */
Line 427:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
<pre>
220 : 284
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.
{{libheader|Action! Sieve of Eratosthenes}}
<
CARD FUNC SumDivisors(CARD x)
Line 480 ⟶ 507:
FI
OD
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Amicable_pairs.png Screenshot from Atari 8-bit computer]
Line 499 ⟶ 526:
[[http://rosettacode.org/wiki/Proper_divisors#Ada]].
<
procedure Amicable_Pairs is
Line 518 ⟶ 545:
end if;
end loop;
end Amicable_Pairs;</
{{Out}}
<pre>
Line 533 ⟶ 560:
=={{header|ALGOL 60}}==
{{works with|A60}}
<
begin
comment - return
integer procedure mod(
value
begin
mod :=
end;
Line 550 ⟶ 577:
sum := 1;
f1 := 2;
for f1 := f1 while (f1 * f1) <= n do
begin
if mod(n, f1) = 0 then
Line 585 ⟶ 612:
end
</syntaxhighlight>
{{out}}
<pre>
Line 601 ⟶ 628:
=={{header|ALGOL 68}}==
<syntaxhighlight lang="algol68">
BEGIN # find amicable pairs p1, p2 where each is equal to the other's proper divisor sum #
[ 1 : 20 000 ]INT pd sum; # table of proper divisors #
FOR n TO UPB pd sum DO pd sum[ n ] := 1 OD;
FOR i FROM 2 TO
DO
OD
OD;
# find the amicable pairs up to 20 000
FOR p1 TO UPB pd sum - 1
INT pd sum p1 = pd sum[ p1
IF pd sum p1 > p1 AND pd sum p1 <= UPB pd sum
IF pd sum[ pd sum p1 ]
print( ( whole( p1, -6 ), " and ", whole( pd sum p1, -6 ), " are an amicable pair", newline ) )
FI
OD
END
</syntaxhighlight>
{{out}}
<pre>
Line 656 ⟶ 660:
</pre>
=={{header|
{{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 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;
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>
=={{header|AppleScript}}==
===Functional===
{{Trans|JavaScript}}
<
-- amicablePairsUpTo :: Int -> Int
Line 846 ⟶ 845:
end script
end if
end mReturn</
{{Out}}
<
{6232, 6368}, {10744, 10856}, {12285, 14595}, {17296, 18416}}</
----
===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}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI or android with termux */
/* program amicable.s */
Line 1,004 ⟶ 1,087:
/***************************************************/
.include "../affichage.inc"
</syntaxhighlight>
<pre>
220 : 284
Line 1,016 ⟶ 1,099:
</pre>
=={{header|Arturo}}==
<
(factors x) -- x
Line 1,035 ⟶ 1,118:
]
print unique amicables</
{{out}}
Line 1,042 ⟶ 1,125:
=={{header|ATS}}==
<syntaxhighlight lang="ats">
(* ****** ****** *)
//
Line 1,147 ⟶ 1,230:
(* ****** ****** *)
</syntaxhighlight>
{{out}}
Line 1,162 ⟶ 1,245:
=={{header|AutoHotkey}}==
<
Loop, 20000
{
Line 1,214 ⟶ 1,297:
}
MsgBox % final
ExitApp</
{{out}}
<pre>
Line 1,228 ⟶ 1,311:
=={{header|AWK}}==
<
#!/bin/awk -f
function sumprop(num, i,sum,root) {
Line 1,256 ⟶ 1,339:
}
}
}</
{{out}}
<pre>
Line 1,272 ⟶ 1,355:
=={{header|
==={{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}}
<
if number < 2 then return 0
sum = 0
Line 1,298 ⟶ 1,438:
end if
next n
end</
{{out}}
<pre>The pairs of amicable numbers below 20,000 are :
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}}==
<
manifest $(
Line 1,342 ⟶ 1,592:
if amicable(pds, x, y) do
writef("%N, %N*N", x, y)
$)</
{{out}}
Line 1,356 ⟶ 1,606:
=={{header|Befunge}}==
<
1>$$:28*:*:*%\28*:*:*/`06p28*:*:*/\2v %%^:*:<>*v
+|!:-1g60/*:*:*82::+**:*:<<>:#**#8:#<*^>.28*^8 :
:v>>*:*%/\28*:*:*%+\v>8+#$^#_+#`\:#0<:\`1/*:*2#<
2v^:*82\/*:*:*82:::_v#!%%*:*:*82\/*:*:*82::<_^#<
>>06p:28*:*:**1+01-\>1+::28*:*:*/\28*:*:*%:*\`!^</
{{out}}
Line 1,378 ⟶ 1,628:
The program will overflow and error in all sorts of ways when given a commandline argument >= UINT_MAX/2 (generally 2^31)
<
#include <stdlib.h>
Line 1,433 ⟶ 1,683:
printf("\nTop %u count : %u\n",top,cnt);
return 0;
}</
{{out}}
<pre>
Line 1,462 ⟶ 1,712:
=={{header|C sharp|C#}}==
<
using System.Collections.Generic;
using System.Linq;
Line 1,498 ⟶ 1,748:
}
}
}</
{{out}}
<pre>
Line 1,512 ⟶ 1,762:
=={{header|C++}}==
<
#include <vector>
#include <unordered_map>
Line 1,561 ⟶ 1,811:
std::cout << count << " amicable pairs discovered" << std::endl;
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,576 ⟶ 1,826:
=={{header|Clojure}}==
<
(ns example
(:gen-class))
Line 1,600 ⟶ 1,850:
(doseq [q find-pairs]
(println q))
</syntaxhighlight>
{{Out}}
<pre>
Line 1,614 ⟶ 1,864:
=={{header|CLU}}==
<
proper_divisors = proc (max: int) returns (array[int])
divs: array[int] := array[int]$fill(1, max, 0)
Line 1,643 ⟶ 1,893:
end
end
end start_up</
{{out}}
<pre>220, 284
Line 1,655 ⟶ 1,905:
=={{header|Common Lisp}}==
<
(defun sum-proper-divisors (n)
(or (gethash n cache)
Line 1,669 ⟶ 1,919:
collect (list x sum-divs)))
(amicable-pairs-up-to 20000)</
{{out}}
<pre>((220 284) (1184 1210) (2620 2924) (5020 5564) (6232 6368) (10744 10856)
Line 1,675 ⟶ 1,925:
=={{header|Cowgol}}==
<
const LIMIT := 20000;
Line 1,714 ⟶ 1,964:
end loop;
i := i + 1;
end loop;</
{{out}}
<pre>220, 284
Line 1,726 ⟶ 1,976:
=={{header|Crystal}}==
<syntaxhighlight lang="crystal">
MX = 524_000_000
N = Math.sqrt(MX).to_u32
Line 1,747 ⟶ 1,997:
end
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,767 ⟶ 2,017:
=={{header|D}}==
{{trans|Python}}
<
import std.stdio, std.algorithm, std.range, std.typecons, std.array;
Line 1,780 ⟶ 2,030:
writefln("Amicable pair: %d and %d with proper divisors:\n %s\n %s",
n, divSum, properDivs(n), properDivs(divSum));
}</
{{out}}
<pre>Amicable pair: 220 and 284 with proper divisors:
Line 1,811 ⟶ 2,061:
=={{header|Draco}}==
<
* P[n] is the sum of proper divisors of N */
proc nonrec propdivs([*] word p) void:
Line 1,838 ⟶ 2,088:
od
od
corp</
{{out}}
<pre> 220, 284
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}}==
<
;; using (sum-divisors) from math.lib
Line 1,869 ⟶ 2,141:
→ (... (802725 . 863835) (879712 . 901424) (898216 . 980984) (947835 . 1125765) (998104 . 1043096))
</syntaxhighlight>
=={{header|Ela}}==
{{trans|Haskell}}
<
divisors n = filter ((0 ==) << (n `mod`)) [1..(n `div` 2)]
Line 1,880 ⟶ 2,152:
pairs = [(n, m) \\ (n, nd) <- divs, (m, md) <- divs | n < m && nd == m && md == n]
do putLn pairs ::: IO</
{{out}}
Line 1,888 ⟶ 2,160:
=={{header|Elena}}==
{{trans|C#}}
ELENA
<
import system'routines;
Line 1,897 ⟶ 2,169:
{
ProperDivisors
= Range.new(1,self / 2).filterBy::(n => self.mod
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)
}
}</
{{out}}
<pre>
Line 1,937 ⟶ 2,209:
</pre>
=== Alternative variant using strong-typed closures ===
<
import system'routines'stex;
import system'collections;
Line 1,946 ⟶ 2,218:
{
Enumerator<int> ProperDivisors
= new Range(1,self / 2).filterBy::(int n => self.mod
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)
}
}</
=== Alternative variant using yield enumerator ===
<
import system'routines'stex;
import system'collections;
Line 1,981 ⟶ 2,254:
{
Enumerator<int> function(int number)
= Range.new(1, number / 2).filterBy::(int n => number.mod
}
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
{
int sum := divsums[i];
if(i < sum && sum <= divsums.Length && divsums[sum] == i) {
$yield
}
};
Line 2,012 ⟶ 2,285:
{
auto e := new AmicablePairs(Limit);
for(auto pair := e.next()
{
console.printLine(pair.Item1, " ", pair.Item2)
}
}</
{{out}}
<pre>
Line 2,032 ⟶ 2,305:
{{works with|Elixir|1.2}}
With [[proper_divisors#Elixir]] in place:
<
def divisors(1), do: []
def divisors(n), do: [1 | divisors(2,n,:math.sqrt(n))] |> Enum.sort
Line 2,045 ⟶ 2,318:
Enum.filter(map, fn {n,sum} -> map[sum] == n and n < sum end)
|> Enum.sort
|> Enum.each(fn {i,j} -> IO.puts "#{i} and #{j}" end)</
{{out}}
Line 2,063 ⟶ 2,336:
Very slow solution. Same functions by and large as in proper divisors and co.
<
-module(properdivs).
-export([amicable/1,divs/1,sumdivs/1]).
Line 2,099 ⟶ 2,372:
sumdivs(N) -> lists:sum(divs(N)).
</
{{out}}
<pre>
Line 2,135 ⟶ 2,408:
[See the talk section '''amicable pairs, out of order''' for this Rosetta Code task.]
<
friendly(Limit) ->
List = [{X,properdivs:sumdivs(X)} || X <- lists:seq(3,Limit)],
Line 2,144 ⟶ 2,417:
io:format("L: ~w~n", [Final]).
</syntaxhighlight>
{{output}}
Line 2,154 ⟶ 2,427:
We might answer a challenge by saying:
<
friendly(Limit) ->
List = [{X,properdivs:sumdivs(X)} || X <- lists:seq(3,Limit)],
Line 2,175 ⟶ 2,448:
end.
</syntaxhighlight>
{{out}}
<pre>
Line 2,192 ⟶ 2,465:
=={{header|ERRE}}==
<
CONST LIMIT=20000
Line 2,219 ⟶ 2,492:
IF (N=M2 AND N<M1) THEN PRINT(N,M1)
END FOR
END PROGRAM</
{{out}}
<pre>Amicable pairs < 20000
Line 2,233 ⟶ 2,506:
=={{header|F_Sharp|F#}}==
<
[2..20000 - 1]
|> List.map (fun n-> n, ([1..n/2] |> List.filter (fun x->n % x = 0) |> List.sum))
Line 2,242 ⟶ 2,515:
|> List.map List.head
|> List.iter (printfn "%A")
</syntaxhighlight>
{{out}}
<pre>
Line 2,258 ⟶ 2,531:
This solution focuses on the language's namesake: factoring code into small words which are subsequently composed to form more powerful — yet just as simple — words. Using this approach, the final word naturally arrives at the solution. This is often referred to as the bottom-up approach, which is a way in which Factor (and other concatenative languages) commonly differs from other languages.
<syntaxhighlight lang="factor">
USING: grouping math.primes.factors math.ranges ;
Line 2,275 ⟶ 2,548:
print-am
</syntaxhighlight>
{{out}}
<pre>
Line 2,295 ⟶ 2,568:
Calculate many times the divisors.
<
dup 2 / 1+ 1 ?do
dup i mod 0= if i swap then
Line 2,318 ⟶ 2,591:
loop ;
20000 amicable-list</
{{out}}
Line 2,333 ⟶ 2,606:
Use memory to store sum of divisors, a little quicker.
<
: proper-divisors ( n -- 1..n )
Line 2,365 ⟶ 2,638:
build-amicable-table .amicables ;
20000 amicable-list</
{{out}}
Line 2,394 ⟶ 2,667:
Amicable! 17296 18416
<syntaxhighlight lang="fortran">
MODULE FACTORSTUFF !This protocol evades the need for multiple parameters, or COMMON, or one shapeless main line...
Concocted by R.N.McLean, MMXV.
Line 2,461 ⟶ 2,734:
END DO !On to the next.
END !Done.
</syntaxhighlight>
=={{header|FreeBASIC}}==
===using Mod===
<
' FreeBASIC v1.05.0 win64
Line 2,501 ⟶ 2,774:
Sleep
End
</syntaxhighlight>
{{out}}
Line 2,517 ⟶ 2,790:
</pre>
===using "Sieve of Erathosthenes" style===
<
' compile with: fbc -s console
' replaced the function with 2 FOR NEXT loops
Line 2,554 ⟶ 2,827:
Print : Print : Print " Hit any key to end program"
Sleep
End</
<pre>
The pairs of amicable numbers below 20,000 are :
Line 2,569 ⟶ 2,842:
=={{header|Frink}}==
This example uses Frink's built-in efficient factorization algorithms. It can work for arbitrarily large numbers.
<
n = 1
seen = new set
Line 2,586 ⟶ 2,859:
}
} while n <= 20000
</syntaxhighlight>
{{out}}
<pre>
Line 2,605 ⟶ 2,878:
This program is much too parallel and manifests all the pairs, which requires a giant amount of memory.
<syntaxhighlight lang="text">
fun divisors(n: int): []int =
filter (fn x => n%x == 0) (map (1+) (iota (n/2)))
Line 2,622 ⟶ 2,895:
let amicable = filter amicable (map (getPair divs) (iota (upper*upper)))
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}}==
<syntaxhighlight lang="text">
OPENW 1
CLEARW 1
Line 2,668 ⟶ 2,991:
RETURN sum%
ENDFUNC
</syntaxhighlight>
Output is:
Line 2,685 ⟶ 3,008:
=={{header|Go}}==
<
import "fmt"
Line 2,711 ⟶ 3,034:
}
}
}</
{{output}}
Line 2,727 ⟶ 3,050:
=={{header|Haskell}}==
<
divisors n = filter ((0 ==) . (n `mod`)) [1 .. (n `div` 2)]
Line 2,736 ⟶ 3,059:
pairs = [(n, m) | (n, nd) <- divs, (m, md) <- divs,
n < m, nd == m, md == n]
print pairs</
{{out}}
<pre>[(220,284),(1184,1210),(2620,2924),(5020,5564),(6232,6368),(10744,10856),(12285,14595),(17296,18416)]</pre>
Line 2,743 ⟶ 3,066:
Or, deriving proper divisors above the square root as cofactors (for better performance)
<
amicablePairsUpTo :: Int -> [(Int, Int)]
Line 2,763 ⟶ 3,086:
main :: IO ()
main = mapM_ print $ amicablePairsUpTo 20000</
{{Out}}
<pre>(220,284)
Line 2,778 ⟶ 3,101:
[[Proper divisors#J|Proper Divisor implementation]]:
<
properDivisors=: factors -. -.&1</
(properDivisors is all factors except "the number itself when that number is greater than 1".)
Amicable pairs:
<
220 284
1184 1210
Line 2,791 ⟶ 3,116:
10744 10856
12285 14595
17296 18416</
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}}==
{{works with|Java|8}}
<
import java.util.function.Function;
import java.util.stream.Collectors;
Line 2,821 ⟶ 3,148:
return LongStream.rangeClosed(1, (n + 1) / 2).filter(i -> n % i == 0).sum();
}
}</
<pre>220 284
Line 2,836 ⟶ 3,163:
===ES5===
<
// Proper divisors
Line 2,896 ⟶ 3,223:
) + '\n\n' + JSON.stringify(pairs);
})(20000);</
{{out}}
Line 2,921 ⟶ 3,248:
|}
<
[6232,6368],[10744,10856],[12285,14595],[17296,18416]]</
===ES6===
<
'use strict';
Line 2,986 ⟶ 3,313:
// MAIN ---
return main();
})();</
{{Out}}
<pre>[220,284]
Line 2,998 ⟶ 3,325:
=={{header|jq}}==
<
def proper_divisors:
. as $n
Line 3,023 ⟶ 3,350:
end ;
task(20000)</
{{out}}
<
220 and 284 are amicable
1184 and 1210 are amicable
Line 3,033 ⟶ 3,360:
10744 and 10856 are amicable
12285 and 14595 are amicable
17296 and 18416 are amicable</
=={{header|Julia}}==
Given <code>factor</code>, it is not necessary to calculate the individual divisors to compute their sum. See [[Abundant,_deficient_and_perfect_number_classifications#Julia|Abundant, deficient and perfect number classifications]] for the details.
It is safe to exclude primes from consideration; their proper divisor sum is always 1. This code also uses a minor trick to ensure that none of the numbers identified are above the limit. All numbers in the range are checked for an amicable partner, but the pair is cataloged only when the greater member is reached.
<
function pcontrib(p::Int64, a::Int64)
Line 3,071 ⟶ 3,398:
amicables()
</syntaxhighlight>
{{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
[...]
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>
=={{header|K}}==
<syntaxhighlight lang="k">
propdivs:{1+&0=x!'1+!x%2}
(8,2)#v@&{(x=+/propdivs[a])&~x=a:+/propdivs[x]}' v:1+!20000
Line 3,229 ⟶ 3,500:
12285 14595
17296 18416)
</syntaxhighlight>
=={{header|Kotlin}}==
<
fun sumProperDivisors(n: Int): Int {
Line 3,248 ⟶ 3,519:
}
}
}</
{{out}}
Line 3,265 ⟶ 3,536:
=={{header|Lua}}==
Avoids unnecessary divisor sum calculations.<br>
Runs in around 0.11 seconds on TIO.RUN.
<syntaxhighlight lang="lua">function sumDivs (n)
local sum = 1
for d = 2, math.sqrt(n) do
Line 3,283 ⟶ 3,555:
if sumDivs(m) == n then print(n, m) end
end
end</
{{out}}<pre>
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>
=={{header|MAD}}==
<
DIMENSION DIVS(20000)
PRINT COMMENT $ AMICABLE PAIRS$
Line 3,322 ⟶ 3,659:
VECTOR VALUES AMI = $I6,I6*$
END OF PROGRAM</
{{out}}
Line 3,342 ⟶ 3,679:
{{output?}}
<syntaxhighlight lang="maple">
with(NumberTheory):
pairs:=[];
Line 3,356 ⟶ 3,693:
end do;
pairs;
</syntaxhighlight>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
Module[{sum = Total[Most@Divisors@n]},
sum != n && n == Total[Most@Divisors@sum]]
Grid@Partition[Cases[Range[4, 20000], _?(amicableQ@# &)], 2]</
{{out}}<pre>
Line 3,377 ⟶ 3,714:
=={{header|MATLAB}}==
<
tic
N=2:1:20000; aN=[];
Line 3,411 ⟶ 3,748:
K=1:ceil(x/2);
D=K(~(rem(x, K)));
end</
{{out}}
Line 3,433 ⟶ 3,770:
Being a novice, I submitted my code to the Nim community for review and received much feedback and advice.
They were instrumental in fine-tuning this code for style and readability, I can't thank them enough.
<syntaxhighlight lang="nim">
from math import sqrt
Line 3,452 ⟶ 3,789:
if m != 0 and n == sumProperDivisors(m, false):
echo $n, " ", $m
</syntaxhighlight>
{{out}}
<pre>
Line 3,472 ⟶ 3,809:
Here's a second version that uses a large amount of memory but runs in 2m32seconds.
Again, thanks to the Nim community
<syntaxhighlight lang="nim">
from math import sqrt
Line 3,490 ⟶ 3,827:
if n < m and n != 0 and m == x[n] + 1:
echo n, " ", m
</syntaxhighlight>
{{out}}
<pre>
Line 3,509 ⟶ 3,846:
=={{header|Oberon-2}}==
<syntaxhighlight lang="oberon2">
MODULE AmicablePairs;
IMPORT
Line 3,548 ⟶ 3,885:
END
END AmicablePairs.
</syntaxhighlight>
{{Out}}
<pre>
Line 3,565 ⟶ 3,902:
Using properDivs implementation tasks without optimization (calculating proper divisors sum without returning a list for instance) :
<
Integer method: properDivs -- []
Line 3,578 ⟶ 3,915:
[ i, j ] over add
]
;</
{{out}}
Line 3,585 ⟶ 3,922:
[[220, 284], [1184, 1210], [2620, 2924], [5020, 5564], [6232, 6368], [10744, 10856], [12285, 14595], [17296, 18416]]
</pre>
=={{header|OCaml}}==
<syntaxhighlight lang="ocaml">let rec isqrt n =
if n = 1 then 1
else let _n = isqrt (n - 1) in
(_n + (n / _n)) / 2
let sum_divs n =
let sum = ref 1 in
for d = 2 to isqrt n do
if (n mod d) = 0 then sum := !sum + (n / d + d);
done;
!sum
let () =
for n = 2 to 20000 do
let m = sum_divs n in
if (m > n) then
if (sum_divs m) = n then Printf.printf "%d %d\n" n m;
done
</syntaxhighlight>
{{out}}
<pre>220 284
1184 1210
2620 2924
5020 5564
6232 6368
10744 10856
12285 14595
17296 18416</pre>
=={{header|PARI/GP}}==
<
{{out}}
<pre>220 284
Line 3,620 ⟶ 3,987:
Amicable! 17296,18416,
Source file:<
Program SumOfFactors; uses crt; {Perpetrated by R.N.McLean, December MCMXCV}
//{$DEFINE ShowOverflow}
Line 3,709 ⟶ 4,076:
end;
Close (outf);
END.</
===More expansive.===
a "normal" Version. Nearly fast as perl using nTheory.
<
{$IFDEF FPC}
{$MODE DELPHI}
Line 3,944 ⟶ 4,311:
writeln('Time to find amicable pairs ',FormatDateTime('HH:NN:SS.ZZZ' ,T2-T1));
{$IFNDEF UNIX} readln;{$ENDIF}
end.</
Output
<pre> 1 220 284 ratio 1.2909091
Line 4,001 ⟶ 4,368:
Using "Sieve of Erathosthenes"-style
<
{find amicable pairs in a limited region 2..MAX
beware that >both< numbers must be smaller than MAX
Line 4,241 ⟶ 4,608:
readln;
{$ENDIF}
end.</
output
<pre>
Line 4,292 ⟶ 4,659:
Not particularly clever, but instant for this example, and does up to 20 million in 11 seconds.
{{libheader|ntheory}}
<
for my $x (1..20000) {
my $y = divisor_sum($x)-$x;
say "$x $y" if $y > $x && $x == divisor_sum($y)-$y;
}</
{{out}}
<pre>220 284
Line 4,308 ⟶ 4,675:
=={{header|Phix}}==
<!--<
<span style="color: #
<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>
<!--</
{{out}}
<pre>
Line 4,328 ⟶ 4,695:
=={{header|Phixmonti}}==
<
var n
1 var sum n sqrt
Line 4,349 ⟶ 4,716:
endfor
nl msec print " s" print</
=={{header|PHP}}==
<
function sumDivs ($n) {
Line 4,370 ⟶ 4,737:
}
?></
{{out}}
<pre>220 284
Line 4,380 ⟶ 4,747:
12285 14595
17296 18416</pre>
=={{header|Picat}}==
Different approaches to solve this task:
* foreach loop (two variants)
* list comprehension
* while loop.
Also, the calculation of the sum of divisors is tabled (the table is cleared between each run).
<syntaxhighlight lang="picat">go =>
N = 20000,
println(amicable1),
time(amicable1(N)),
% initialize_table is needed to clear the table cache
% of sum_divisors/1 between each run.
initialize_table,
println(amicable2),
time(amicable2(N)),
initialize_table,
println(amicable3),
time(amicable3(N)),
initialize_table,
println(amicable4),
time(amicable4(N)),
nl.
% Foreach loop and a map (hash table)
amicable1(N) =>
Pairs = new_map(),
foreach(A in 1..N)
B = sum_divisors(A),
C = sum_divisors(B),
if A != B, A == C then
Pairs.put([A,B].sort(),1)
end
end,
println(Pairs.keys().sort()).
% List comprehension
amicable2(N) =>
println([[A,B].sort() : A in 1..N,
B = sum_divisors(A),
C = sum_divisors(B),
A != B, A == C].remove_dups()).
% While loop
amicable3(N) =>
A = 1,
while(A <= N)
B = sum_divisors(A),
if A < B, A == sum_divisors(B) then
print([A,B]), print(" ")
end,
A := A + 1
end,
nl.
% Foreach loop, everything in the condition
amicable4(N) =>
foreach(A in 1..N, B = sum_divisors(A), A < B, A == sum_divisors(B))
print([A,B]), print(" ")
end,
nl.
%
% Sum of divisors of N
%
table
sum_divisors(N) = Sum =>
sum_divisors(2,N,1,Sum).
% Base case: exceeding the limit
sum_divisors(I,N,Sum0,Sum), I > floor(sqrt(N)) =>
Sum = Sum0.
% I is a divisor of N
sum_divisors(I,N,Sum0,Sum), N mod I == 0 =>
Sum1 = Sum0 + I,
(I != N div I ->
Sum2 = Sum1 + N div I
;
Sum2 = Sum1
),
sum_divisors(I+1,N,Sum2,Sum).
% I is not a divisor of N.
sum_divisors(I,N,Sum0,Sum) =>
sum_divisors(I+1,N,Sum0,Sum).
</syntaxhighlight>
{{out}}
<pre>
amicable1
[[220,284],[1184,1210],[2620,2924],[5020,5564],[6232,6368],[10744,10856],[12285,14595],[17296,18416]]
CPU time 0.114 seconds.
amicable2
[[220,284],[1184,1210],[2620,2924],[5020,5564],[6232,6368],[10744,10856],[12285,14595],[17296,18416]]
CPU time 0.106 seconds.
amicable3
[220,284] [1184,1210] [2620,2924] [5020,5564] [6232,6368] [10744,10856] [12285,14595] [17296,18416]
CPU time 0.111 seconds.
amicable4
[220,284] [1184,1210] [2620,2924] [5020,5564] [6232,6368] [10744,10856] [12285,14595] [17296,18416]
CPU time 0.107 seconds.
</pre>
=={{header|PicoLisp}}==
<
(if (assoc Key (val Var))
(con @ (inc (cdr @)))
Line 4,417 ⟶ 4,901:
(< I X)
(= I (factor-sum X))
(println I X) ) ) ) )</
{{output}}
<pre>
Line 4,433 ⟶ 4,917:
=={{header|PL/I}}==
{{trans|REXX}}
<
ami: Proc Options(main);
p9a=time();
Line 4,492 ⟶ 4,976:
Return((p9c-p9b)/1000);
End;
End;</
{{out}}
<pre> sum(pd) computed in 0.510 seconds elapsed
Line 4,506 ⟶ 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">
amicable: procedure options (main);
Line 4,533 ⟶ 5,018:
sumf:
procedure(n) returns (fixed bin);
dcl (n, sum, f1, f2) fixed bin;
Line 4,554 ⟶ 5,040:
end amicable;
</syntaxhighlight>
{{out}}
<pre>
Line 4,568 ⟶ 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}}==
<
/* CP/M CALLS */
BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS;
Line 4,602 ⟶ 5,130:
/* TEST EACH PAIR */
DO I=2 TO 20$000;
IF J > I
IF DIV$SUM(J) = I THEN DO;
CALL PRINT$NUMBER(I);
CALL PRINT(.', $');
Line 4,613 ⟶ 5,142:
CALL EXIT;
EOF</
{{out}}
<pre>220, 284
Line 4,626 ⟶ 5,155:
=={{header|PowerShell}}==
{{works with|PowerShell|2}}
<syntaxhighlight lang="powershell">
function Get-ProperDivisorSum ( [int]$N )
{
Line 4,656 ⟶ 5,185:
Get-AmicablePairs 20000
</syntaxhighlight>
{{out}}
<pre>
Line 4,675 ⟶ 5,204:
With some guidance from other solutions here:
<
UpperBound is round(sqrt(N)),
between(1, UpperBound, D),
Line 4,707 ⟶ 5,236:
amicable_pairs_under_20000(Pairs) :-
assoc_num_divsSum_in_range(1,20000, Assoc),
findall(P, get_amicable_pair(Assoc, P), Pairs).</
Output:
<
R = [220-284, 1184-1210, 2620-2924, 5020-5564, 6232-6368, 10744-10856, 12285-14595, 17296-18416].</
=={{header|PureBasic}}==
<syntaxhighlight lang="purebasic">
EnableExplicit
Line 4,750 ⟶ 5,279:
CloseConsole()
EndIf
</syntaxhighlight>
{{out}}
Line 4,768 ⟶ 5,297:
=={{header|Python}}==
Importing [[Proper_divisors#Python:_From_prime_factors|Proper divisors from prime factors]]:
<
def amicable(rangemax=20000):
Line 4,779 ⟶ 5,308:
for num, divsum in amicable():
print('Amicable pair: %i and %i With proper divisors:\n %r\n %r'
% (num, divsum, sorted(proper_divs(num)), sorted(proper_divs(divsum))))</
{{out}}
Line 4,810 ⟶ 5,339:
Or, supplying our own '''properDivisors''' function, and defining the harvest in terms of a generic '''concatMap''':
<
from itertools import chain
Line 4,886 ⟶ 5,415:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>(220, 284)
Line 4,901 ⟶ 5,430:
<code>properdivisors</code> is defined at [[Proper divisors#Quackery]].
<
dup size 0 = iff
[ drop 0 ] done
Line 4,915 ⟶ 5,444:
nested join ] ] ] is amicables ( n --> [ )
20000 amicables witheach [ witheach [ echo sp ] cr ]</
{{out}}
Line 4,932 ⟶ 5,461:
=={{header|R}}==
<syntaxhighlight lang="r">
divisors <- function (n) {
Filter( function (m) 0 == n %% m, 1:(n/2) )
Line 4,944 ⟶ 5,473:
cat(n, " ", m, "\n")
}
</syntaxhighlight>
{{out}}
Line 4,960 ⟶ 5,489:
=={{header|Racket}}==
With [[Proper_divisors#Racket]] in place:
<
(require "proper-divisors.rkt")
(define SCOPE 20000)
Line 4,991 ⟶ 5,520:
EOS
n m n (proper-divisors n) m (proper-divisors m)))
</syntaxhighlight>
{{out}}
Line 5,031 ⟶ 5,560:
(formerly Perl 6)
{{Works with|Rakudo|2019.03.1}}
<syntaxhighlight lang="raku"
my @l = 1 if x > 1;
(2 .. x.sqrt.floor).map: -> \d {
Line 5,042 ⟶ 5,571:
my $j = propdivsum($i);
say "$i $j" if $j > $i and $i == propdivsum($j);
}</
{{out}}
<pre>220 284
Line 5,054 ⟶ 5,583:
=={{header|REBOL}}==
<
sum-of-divisors: func[n /local sum][
Line 5,069 ⟶ 5,598:
if n = sum-of-divisors m [ print [n tab m] ]
]
]</
{{out}}
Line 5,081 ⟶ 5,610:
12285 14595
17296 18416
</pre>
=={{header|ReScript}}==
<syntaxhighlight lang="rescript">let isqrt = (v) => {
Belt.Float.toInt(
sqrt(Belt.Int.toFloat(v)))
}
let sum_divs = (n) => {
let sum = ref(1)
for d in 2 to isqrt(n) {
if mod(n, d) == 0 {
sum.contents = sum.contents + (n / d + d)
}
}
sum.contents
}
{
for n in 2 to 20000 {
let m = sum_divs(n)
if (m > n) {
if sum_divs(m) == n {
Printf.printf("%d %d\n", n, m)
}
}
}
}
</syntaxhighlight>
{{output}}
<pre>
$ bsc ampairs.res > ampairs.bs.js
$ node ampairs.bs.js
220 284
1184 1210
2620 2924
5020 5564
6232 6368
10744 10856
12285 14595
17296 18416
</pre>
=={{header|REXX}}==
===version 1, with factoring===
<
/*REXX*/
Line 5,126 ⟶ 5,696:
sum=sum+word(list,i)
End
Return sum</
{{out}}
<pre>sum(pd) computed in 48.502000 seconds
Line 5,150 ⟶ 5,720:
CPU time consumption note: for every doubling of '''H''' (the upper limit for searches), the CPU time consumed triples.
<
parse arg H .; if H=='' | H=="," then H= 20000 /*get optional arguments (high limit).*/
w= length(H) ; low= 220 /*W: used for columnar output alignment*/
Line 5,177 ⟶ 5,747:
/* ___ */
if j*j==x then return s + j /*Was X a square? If so, add √ X */
return s /*return (sigma) sum of the divisors. */</
{{out|output|text= when using the default input:}}
<pre>
Line 5,197 ⟶ 5,767:
The optimization makes it about <u>another</u> '''30%''' faster when searching for amicable numbers up to one million.
<
parse arg H .; if H=='' | H=="," then H=20000 /*get optional arguments (high limit).*/
w=length(H) ; low=220 /*W: used for columnar output alignment*/
Line 5,226 ⟶ 5,796:
/* ___ */
if j*j==x then return s + j /*Was X a square? If so, add √ X */
return s /*return (sigma) sum of the divisors. */</
{{out|output|text= is identical to the 2<sup>nd</sup> REXX version.}} <br><br>
Line 5,234 ⟶ 5,804:
The optimization makes it about <u>another</u> '''20%''' faster when searching for amicable numbers up to one million.
<
parse arg H .; if H=='' | H=="," then H=20000 /*get optional arguments (high limit).*/
w= length(H) ; low= 220 /*W: used for columnar output alignment*/
Line 5,267 ⟶ 5,837:
/* ___ */
if j*j==x then return s + j /*Was X a square? If so, add √ X */
return s /*return (sigma) sum of the divisors. */</
{{out|output|text= is identical to the 2<sup>nd</sup> REXX version.}} <br><br>
Line 5,277 ⟶ 5,847:
The optimization makes it about <u>another</u> '''15%''' faster when searching for amicable numbers up to one million.
<
parse arg H .; if H=='' | H=="," then H=20000 /*get optional arguments (high limit).*/
w= length(H) ; low= 220 /*W: used for columnar output alignment*/
Line 5,310 ⟶ 5,880:
/* ___ */
if j*j==x then return s + j /*Was X a square? If so, add √ X */
return s /*return (sigma) sum of the divisors. */</
{{out|output|text= is identical to the 2<sup>nd</sup> REXX version.}} <br><br>
=={{header|Ring}}==
<
size = 18500
for n = 1 to size
Line 5,331 ⟶ 5,901:
next
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}}==
With [[proper_divisors#Ruby]] in place:
<
(1..20_000).each{|n| h[n] = n.proper_divisors.sum }
h.select{|k,v| h[v] == k && k < v}.each do |key,val| # k<v filters out doubles and perfects
puts "#{key} and #{val}"
end
</syntaxhighlight>
{{out}}<pre>
220 and 284
Line 5,353 ⟶ 5,948:
=={{header|Run BASIC}}==
<
for n = 1 to size
m = amicable(n)
Line 5,364 ⟶ 5,959:
if nr mod d = 0 then amicable = amicable + d + nr / d
next
end function</
<pre>
220 and 284
Line 5,378 ⟶ 5,973:
=={{header|Rust}}==
<syntaxhighlight lang="rust">
fn sum_of_divisors(val: u32) -> u32 {
(1..val/2+1).filter(|n| val % n == 0)
.fold(0, |sum, n| sum + n)
Line 5,392 ⟶ 5,988:
}
}
}</
{{out}}
<pre>
Line 5,403 ⟶ 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>
=={{header|S-BASIC}}==
<syntaxhighlight lang = "BASIC">
$lines
$constant search_limit = 20000
var a, b, count = integer
dim integer sumf(search_limit)
print "Searching up to"; search_limit; " for amicable pairs:"
rem - set up the table of proper divisor sums
for a = 1 to search_limit
sumf(a) = 1
next a
for a = 2 to search_limit
b = a + a
while (b > 0) and (b <= search_limit) do
begin
sumf(b) = sumf(b) + a
b = b + a
end
next a
rem - search for pairs using the table
count = 0
for a = 2 to search_limit
b = sumf(a)
if (b > a) and (b < search_limit) then
if a = sumf(b) then
begin
print using "##### #####"; a; b
count = count + 1
end
next a
print count; " pairs were found"
end
</syntaxhighlight>
{{out}}
<pre>
Searching up to 20000 for amicable pairs:
220 284
1184 1210
2620 2924
5020 5564
6232 6368
10744 10856
12285 14595
17296 18416
8 pairs were found
</pre>
=={{header|Scala}}==
<
val divisorsSum = (1 to 20000).map(i => i -> properDivisors(i).sum).toMap
val result = divisorsSum.filter(v => v._1 < v._2 && divisorsSum.get(v._2) == Some(v._1))
println( result mkString ", " )</
{{out}}
<pre>5020 -> 5564, 220 -> 284, 6232 -> 6368, 17296 -> 18416, 2620 -> 2924, 10744 -> 10856, 12285 -> 14595, 1184 -> 1210</pre>
Line 5,416 ⟶ 6,146:
=={{header|Scheme}}==
<
(import (scheme base)
(scheme inexact)
Line 5,466 ⟶ 6,196:
(loop-j (+ 1 j))))
(loop-i (+ 1 i))))
</syntaxhighlight>
{{out}}
Line 5,479 ⟶ 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}}==
<
n.sigma - n
}
Line 5,488 ⟶ 6,246:
var j = propdivsum(i)
say "#{i} #{j}" if (j>i && i==propdivsum(j))
}</
{{out}}
<pre>
Line 5,502 ⟶ 6,260:
=={{header|Swift}}==
<
func sqrt(x:Int) -> Int { return Int(sqrt(Double(x))) }
Line 5,555 ⟶ 6,313:
}
}
}</
===Alternative===
about 800 times faster.<
func sqrt(x:Int) -> Int { return Int(sqrt(Double(x))) }
Line 5,600 ⟶ 6,358:
}
amicables(20_000)</
{{out}}
<pre>(220, 284)
Line 5,613 ⟶ 6,371:
=={{header|tbas}}==
<syntaxhighlight lang="vb">
dim sums(20000)
Line 5,639 ⟶ 6,397:
next
next
</syntaxhighlight>
<pre>
>tbas amicable_pairs.bas
Line 5,653 ⟶ 6,411:
=={{header|Tcl}}==
<
if {$n == 1} return
set divs 1
Line 5,693 ⟶ 6,451:
puts "\t$m : $md"
puts "\t$n : $nd"
}</
{{out}}
<pre>
Line 5,723 ⟶ 6,481:
=={{header|Transd}}==
<
#lang transd
Line 5,742 ⟶ 6,500:
(textout (+ @idx 1) ", " i "\n")
)))))
}</
<pre>
284, 220
Line 5,755 ⟶ 6,513:
=={{header|uBasic/4tH}}==
<syntaxhighlight lang="text">Input "Limit: ";l
Print "Amicable pairs < ";l
Line 5,803 ⟶ 6,561:
If (b@ > 1) c@ = c@ * (b@+1)
Return (c@)</
{{Out}}
<pre>Limit: 20000
Line 5,819 ⟶ 6,577:
=={{header|UTFool}}==
<syntaxhighlight lang="utfool">
···
http://rosettacode.org/wiki/Amicable_pairs
Line 5,838 ⟶ 6,596:
m +: n \ i = 0 ? i + (i = n / i ? 0 ! n / i) ! 0
⏎ m
</syntaxhighlight>
=={{header|VBA}}==
<
Public Sub AmicablePairs()
Line 5,878 ⟶ 6,636:
If n Mod j = 0 Then S = j + S
Next
End Function</
{{out}}
<pre>Execution Time : 7,95703125 seconds.
Line 5,893 ⟶ 6,651:
=={{header|VBScript}}==
Not at all optimal. :-(
<
Set nlookup = CreateObject("Scripting.Dictionary")
Set uniquepair = CreateObject("Scripting.Dictionary")
Line 5,928 ⟶ 6,686:
Next
WScript.Echo "Execution Time: " & DateDiff("s",Start,Now) & " seconds"</
{{out}}
<pre>220:284
Line 5,940 ⟶ 6,698:
Execution Time: 162 seconds</pre>
=={{header|V (Vlang)}}==
{{trans|Go}}
<syntaxhighlight lang="Go">
fn pfac_sum(i int) int {
mut sum := 0
for p := 1; p <= i / 2; p++{
if i % p == 0 {
sum += p
}
Line 5,961 ⟶ 6,720:
}
}
}
</syntaxhighlight>
{{output}}
Line 5,974 ⟶ 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}}
<
import "./math" for Int, Nums
var a = List.filled(20000, 0)
Line 5,990 ⟶ 6,782:
var m = a[n]
if (m > n && m < 20000 && n == a[m]) {
}
}</
{{out}}
Line 6,008 ⟶ 6,800:
=={{header|XPL0}}==
<
int Num, Div, Sum, Quot;
[Div:= 2;
Line 6,034 ⟶ 6,826:
];
];
]</
{{out}}
Line 6,050 ⟶ 6,842:
=={{header|Yabasic}}==
{{trans|Lua}}
<
local sum, d
Line 6,071 ⟶ 6,863:
next
print : print peek("millisrunning"), " ms"</
=={{header|Zig}}==
<
// Fill up a given array with arr[n] = sum(propDivs(n))
Line 6,117 ⟶ 6,898:
}
}
}</
{{out}}
<pre>220, 284
Line 6,127 ⟶ 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}}==
{{trans|AWK}}
<
20 PRINT "Amicable pairs < ";limit
30 FOR n=1 TO limit
Line 6,148 ⟶ 6,940:
1070 IF num/root=INT (num/root) THEN LET sum=sum+root
1080 LET num=sum
1090 RETURN</
{{out}}
<pre>Amicable pairs < 20000
|