Amicable pairs: Difference between revisions

 

Two integers <math>N</math> and <math>M</math> are said to be [[wp:Amicable numbers|amicable pairs]] if <math>N \neq M</math> and the sum of the [[Proper divisors|proper divisors]] of <math>N</math> (<math>\mathrm{sum}(\mathrm{propDivs}(N))</math>) <math>= M</math> as well as <math>\mathrm{sum}(\mathrm{propDivs}(M)) = N</math>.

<br><br>

 

 

 

 

FI

OD

{{out}}

<pre>

</pre>

 

 

 

 

{{Trans|JavaScript}}

 

 

-- amicablePairsUpTo :: Int -> Int

end script

end if

{{Out}}

 

=={{header|ATS}}==

(* ****** ****** *)

//

 

(* ****** ****** *)

 

{{out}}

 

=={{header|AutoHotkey}}==

Loop, 20000

{

}

MsgBox % final

{{out}}

<pre>

 

=={{header|AWK}}==

#!/bin/awk -f

function sumprop(num, i,sum,root) {

}

}

{{out}}

<pre>

17296 18416

</pre>

 

=={{header|C}}==

 

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>

 

printf("\nTop %u count : %u\n",top,cnt);

return 0;

{{out}}

<pre>

real 0m16.285s

user 0m16.156s

</pre>

 

=={{header|C++}}==

#include <vector>

#include <unordered_map>

std::cout << count << " amicable pairs discovered" << std::endl;

}

{{out}}

<pre>

[17296, 18416]

8 amicable pairs discovered

</pre>

 

=={{header|Clojure}}==

(ns example

(:gen-class))

(doseq [q find-pairs]

(println q))

{{Out}}

<pre>

#{10744 10856}

</pre>

 

=={{header|Common Lisp}}==

(defun sum-proper-divisors (n)

(or (gethash n cache)

collect (list x sum-divs)))

 

{{out}}

<pre>((220 284) (1184 1210) (2620 2924) (5020 5564) (6232 6368) (10744 10856)

(12285 14595) (17296 18416))</pre>

 

=={{header|Crystal}}==

MX = 524_000_000

N = Math.sqrt(MX).to_u32

end

}

{{out}}

<pre>

=={{header|D}}==

{{trans|Python}}

import std.stdio, std.algorithm, std.range, std.typecons, std.array;

 

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:

[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|EchoLisp}}==

;; using (sum-divisors) from math.lib

 

→ (... (802725 . 863835) (879712 . 901424) (898216 . 980984) (947835 . 1125765) (998104 . 1043096))

 

 

=={{header|Ela}}==

{{trans|Haskell}}

 

divisors n = filter ((0 ==) << (n `mod`)) [1..(n `div` 2)]

pairs = [(n, m) \\ (n, nd) <- divs, (m, md) <- divs | n < m && nd == m && md == n]

 

 

{{out}}

<pre>

[(220,284),(1184,1210),(2620,2924),(5020,5564),(6232,6368),(10744,10856),(12285,14595),(17296,18416)]</pre>

 

=={{header|Elixir}}==

{{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

Enum.filter(map, fn {n,sum} -> map[sum] == n and n < sum end)

|> Enum.sort

 

{{out}}

Very slow solution. Same functions by and large as in proper divisors and co.

 

-module(properdivs).

-export([amicable/1,divs/1,sumdivs/1]).

sumdivs(N) -> lists:sum(divs(N)).

{{out}}

<pre>

[See the talk section &nbsp; '''amicable pairs, out of order''' &nbsp; for this Rosetta Code task.]

 

friendly(Limit) ->

List = [{X,properdivs:sumdivs(X)} || X <- lists:seq(3,Limit)],

io:format("L: ~w~n", [Final]).

 

{{output}}

 

 

We might answer a challenge by saying:

friendly(Limit) ->

List = [{X,properdivs:sumdivs(X)} || X <- lists:seq(3,Limit)],

end.

{{out}}

<pre>

 

=={{header|ERRE}}==

 

CONST LIMIT=20000

IF (N=M2 AND N<M1) THEN PRINT(N,M1)

END FOR

{{out}}

<pre>Amicable pairs < 20000

17296 18416

</pre>

 

=={{header|Fortran}}==

Amicable! 17296 18416

 

MODULE FACTORSTUFF !This protocol evades the need for multiple parameters, or COMMON, or one shapeless main line...

Concocted by R.N.McLean, MMXV.

END DO !On to the next.

END !Done.

 

=={{header|FreeBASIC}}==

===using Mod===

' FreeBASIC v1.05.0 win64

 

Sleep

End

 

{{out}}

</pre>

===using "Sieve of Erathosthenes" style===

' compile with: fbc -s console

' replaced the function with 2 FOR NEXT loops

Print : Print : Print " Hit any key to end program"

Sleep

<pre>

The pairs of amicable numbers below 20,000 are :

12285 and 14595

17296 and 18416</pre>

 

=={{header|Futhark}}==

 

This program is much too parallel and manifests all the pairs, which requires a giant amount of memory.

 

fun divisors(n: int): []int =

filter (fn x => n%x == 0) (map (1+) (iota (n/2)))

let amicable = filter amicable (map (getPair divs) (iota (upper*upper)))

in map (fn (np,mp) => [#1 np, #1 mp]) amicable

 

=={{header|GFA Basic}}==

 

OPENW 1

CLEARW 1

RETURN sum%

ENDFUNC

 

Output is:

-- found all amicable pairs

</pre>

=={{header|Go}}==

import "fmt"

}

<pre>

</pre>

=={{header|Haskell}}==

divisors n = filter ((0 ==) . (n `mod`)) [1 .. (n `div` 2)]

 

pairs = [(n, m) | (n, nd) <- divs, (m, md) <- divs,

n < m, nd == m, md == n]

{{out}}

<pre>[(220,284),(1184,1210),(2620,2924),(5020,5564),(6232,6368),(10744,10856),(12285,14595),(17296,18416)]</pre>

 

 

 

amicablePairsUpTo n =

 

 

main :: IO ()

{{Out}}

<pre>(220,284)

[[Proper divisors#J|Proper Divisor implementation]]:

 

 

Amicable pairs:

 

220 284

1184 1210

10744 10856

12285 14595

 

=={{header|Java}}==

{{works with|Java|8}}

import java.util.function.Function;

import java.util.stream.Collectors;

return LongStream.rangeClosed(1, (n + 1) / 2).filter(i -> n % i == 0).sum();

}

 

<pre>220 284

===ES5===

 

// Proper divisors

) + '\n\n' + JSON.stringify(pairs);

 

{{out}}

|}

 

 

===ES6===

 

 

// amicablePairsUpTo :: Int -> [(Int, Int)]

 

 

 

 

 

 

 

 

 

 

 

{{Out}}

 

=={{header|jq}}==

def proper_divisors:

. as $n

end ;

 

{{out}}

220 and 284 are amicable

1184 and 1210 are amicable

10744 and 10856 are amicable

12285 and 14595 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.

 

function pcontrib(p::Int64, a::Int64)

n = one(p)

dsum -= n

end

 

end

 

{{out}}

<pre>

1 => 220, 284

2 => 1184, 1210

7 => 12285, 14595

8 => 17296, 18416

</pre>

 

=={{header|K}}==

propdivs:{1+&0=x!'1+!x%2}

(8,2)#v@&{(x=+/propdivs[a])&~x=a:+/propdivs[x]}' v:1+!20000

12285 14595

17296 18416)

 

=={{header|Kotlin}}==

 

fun sumProperDivisors(n: Int): Int {

}

}

 

{{out}}

 

=={{header|Lua}}==

local sum = 1

for d = 2, math.sqrt(n) do

if sumDivs(m) == n then print(n, m) end

end

 

{{out}}<pre>

17296 18416

</pre>

 

=={{header|Maple}}==

with(NumberTheory):

pairs:=[];

end do;

pairs;

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

Module[{sum = Total[Most@Divisors@n]},

sum != n && n == Total[Most@Divisors@sum]]

 

 

{{out}}<pre>

17296 18416

</pre>

=={{header|Nim}}==

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.

from math import sqrt

 

if m != 0 and n == sumProperDivisors(m, false):

echo $n, " ", $m

{{out}}

<pre>

Here's a second version that uses a large amount of memory but runs in 2m32seconds.

Again, thanks to the Nim community

from math import sqrt

 

if n < m and n != 0 and m == x[n] + 1:

echo n, " ", m

{{out}}

<pre>

 

=={{header|Oberon-2}}==

MODULE AmicablePairs;

IMPORT

END

END AmicablePairs.

{{Out}}

<pre>

Using properDivs implementation tasks without optimization (calculating proper divisors sum without returning a list for instance) :

 

 

: amicables

| i j |

20000 loop: i [

[ i, j ] over add

 

{{out}}

[[220, 284], [1184, 1210], [2620, 2924], [5020, 5564], [6232, 6368], [10744, 10856], [12285, 14595], [17296, 18416]]

</pre>

 

=={{header|PARI/GP}}==

{{out}}

<pre>220 284

Amicable! 17296,18416,

 

Program SumOfFactors; uses crt; {Perpetrated by R.N.McLean, December MCMXCV}

//{$DEFINE ShowOverflow}

end;

Close (outf);

 

===More expansive.===

a "normal" Version. Nearly fast as perl using nTheory.

{$IFDEF FPC}

{$MODE DELPHI}

// sieve of erathosthenes without multiples of 2

type

var

ESieve : ^tSieve;

writeln('Time to find amicable pairs ',FormatDateTime('HH:NN:SS.ZZZ' ,T2-T1));

{$IFNDEF UNIX} readln;{$ENDIF}

Output

<pre> 1 220 284 ratio 1.2909091

17296 [2^4*23*47*17296]

18416 [2^4*18416]</pre>

===Alternative===

about 25-times faster.

Using "Sieve of Erathosthenes"-style

 

{find amicable pairs in a limited region 2..MAX

beware that >both< numbers must be smaller than MAX

readln;

{$ENDIF}

output

<pre>

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

 

=={{header|Phix}}==

{{out}}

<pre>

{12285,14595}

{17296,18416}

</pre>

 

=={{header|PicoLisp}}==

(if (assoc Key (val Var))

(con @ (inc (cdr @)))

(push Var (cons Key 1)) )

Key )

(de factor-sum (N)

(if (=1 N)

(accud 'R N1)

(for I R

(- S N) ) ) )

(bench

(< I X)

(= I (factor-sum X))

{{output}}

<pre>

12285 14595

17296 18416

</pre>

 

=={{header|PL/I}}==

{{trans|REXX}}

ami: Proc Options(main);

p9a=time();

Return((p9c-p9b)/1000);

End;

{{out}}

<pre> sum(pd) computed in 0.510 seconds elapsed

17296 18416 found after 2.240 seconds

2.250 seconds total search time</pre>

 

=={{header|PowerShell}}==

{{works with|PowerShell|2}}

function Get-ProperDivisorSum ( [int]$N )

{

 

Get-AmicablePairs 20000

{{out}}

<pre>

With some guidance from other solutions here:

 

UpperBound is round(sqrt(N)),

between(1, UpperBound, D),

amicable_pairs_under_20000(Pairs) :-

assoc_num_divsSum_in_range(1,20000, Assoc),

 

Output:

 

 

=={{header|PureBasic}}==

EnableExplicit

 

CloseConsole()

EndIf

 

{{out}}

=={{header|Python}}==

Importing [[Proper_divisors#Python:_From_prime_factors|Proper divisors from prime factors]]:

 

def amicable(rangemax=20000):

for num, divsum in amicable():

print('Amicable pair: %i and %i With proper divisors:\n %r\n %r'

 

{{out}}

[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|Racket}}==

With [[Proper_divisors#Racket]] in place:

(require "proper-divisors.rkt")

(define SCOPE 20000)

EOS

n m n (proper-divisors n) m (proper-divisors m)))

 

{{out}}

17296: divisors: (1 2 4 8 16 23 46 47 92 94 184 188 368 376 752 1081 2162 4324 8648)

 

</pre>

 

=={{header|REXX}}==

Do x=1 To 20000

pd=proper_divisors(x)

sum=sum+word(list,i)

End

{{out}}

<pre>sum(pd) computed in 48.502000 seconds

188.836000 seconds total search time </pre>

 

This REXX version allows the specification of the upper limit (for the searching of amicable pairs).

 

Other optimizations were incorporated which took advantage of several well-known generalizations about amicable pairs.

 

 

@.=. /* [↑] LOW is lowest amicable number. */

end /*k*/ /* [↑] process a range of integers. */

if m==@.n then do /*If equal, might be an amicable number*/

if m==n then iterate /*Is this a perfect number? Then skip.*/

end

end /*m*/

say

exit /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

<pre>

220 and 284 are an amicable pair.

17296 and 18416 are an amicable pair.

 

</pre>

 

This REXX version is optimized to take advantage of the lowest ending-single-digit amicable number, &nbsp; and

<br>also incorporates the search of amicable numbers into the generation of the sigmas of the integers.

 

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*/

@.= /* [↑] LOW is lowest amicable number. */

do k=low for H-low /*generate sigma sums for a range of #s*/

parse var k '' -1 D /*obtain last decimal digit of K. */

if k<$.D then iterate /*if no need to compute, then skip it. */

if k==@._ then do /*is it a possible amicable number ? */

if _==k then iterate /*Is it a perfect number? Then skip it*/

end

end /*k*/ /* [↑] process a range of integers. */

exit /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

do j=2+od by 1+od while j*j<x /*divide by all integers up to the √ x */

end /*j*/ /* [↑] % is REXX integer division. */

 

This REXX version is optimized to use the &nbsp; ''integer square root of X'' &nbsp; in the &nbsp; '''sigma''' &nbsp; function &nbsp; (instead of

<br>computing the square of &nbsp; '''J''' &nbsp; to see if that value exceeds &nbsp; '''X''').

 

parse arg H .; if H=='' | H=="," then H=20000 /*get optional arguments (high limit).*/

@.= /* [↑] LOW is lowest amicable number. */

do k=low for H-low /*generate sigma sums for a range of #s*/

parse var k '' -1 D /*obtain last decimal digit of K. */

if k<$.D then iterate /*if no need to compute, then skip it. */

if k==@._ then do /*is it a possible amicable number ? */

if _==k then iterate /*Is it a perfect number? Then skip it*/

end

end /*k*/ /* [↑] process a range of integers. */

exit /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

do while q>1; q=q%4; _=x-r-q; r=r%2; if _>=0 then do;x=_;r=r+q; end; end

return r

/*──────────────────────────────────────────────────────────────────────────────────────*/

do j=2+od by 1+od to iSqrt(x) /*divide by all integers up to the √ x */

end /*j*/ /* [↑] % is the REXX integer division.*/

 

This REXX version is optimized by bringing the functions in-line &nbsp; (which minimizes the overhead of invoking two

<br>internal functions), &nbsp; and it also pre-computes the powers of four &nbsp; (for the integer square root code).

This method of coding has the disadvantage in that the code (logic) is less idiomatic and therefore less readable.

 

parse arg H .; if H=='' | H=="," then H=20000 /*get optional arguments (high limit).*/

@.= /* [↑] LOW is lowest amicable number. */

parse var k '' -1 D /*obtain last decimal digit of K. */

end

end /*k*/ /* [↑] process a range of integers. */