Amicable pairs: Difference between revisions

 

=={{header|11l}}==

R I n < 2 {0} E sum((1 .. n I/ 2).filter(it -> (@n % it) == 0))

 

 

=={{header|8080 Assembly}}==

;;; Calculate proper divisors of 2..20000

lxi h,pdiv + 4 ; 2 bytes per entry

 

=={{header|8086 Assembly}}==

cpu 8086

org 100h

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits <br> or android 64 bits with application Termux }}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program amicable64.s */

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)

[[http://rosettacode.org/wiki/Proper_divisors#Ada]].

 

procedure Amicable_Pairs is

=={{header|ALGOL 60}}==

{{works with|A60}}

begin

 

 

=={{header|ALGOL 68}}==

# if n = 1, 0 or -1, we return 0 #

PROC sum proper divisors = ( INT n )INT:

{{Trans|GFA Basic}}

 

110 CLEAR

120 !

{{Trans|JavaScript}}

 

 

-- amicablePairsUpTo :: Int -> Int

end mReturn</syntaxhighlight>

{{Out}}

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

/* ARM assembly Raspberry PI or android with termux */

/* program amicable.s */

</pre>

=={{header|Arturo}}==

(factors x) -- x

 

 

=={{header|ATS}}==

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

//

 

=={{header|AutoHotkey}}==

Loop, 20000

{

 

=={{header|AWK}}==

#!/bin/awk -f

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

=={{header|BASIC256}}==

{{trans|FreeBASIC}}

if number < 2 then return 0

sum = 0

 

=={{header|BCPL}}==

 

manifest $(

=={{header|Befunge}}==

 

1>$$:28*:*:*%\28*:*:*/`06p28*:*:*/\2v %%^:*:<>*v

+|!:-1g60/*:*:*82::+**:*:<<>:#**#8:#<*^>.28*^8 :

 

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>

 

 

=={{header|C sharp|C#}}==

using System.Collections.Generic;

using System.Linq;

 

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

#include <vector>

#include <unordered_map>

 

=={{header|Clojure}}==

(ns example

(:gen-class))

 

=={{header|CLU}}==

proper_divisors = proc (max: int) returns (array[int])

divs: array[int] := array[int]$fill(1, max, 0)

 

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

(defun sum-proper-divisors (n)

(or (gethash n cache)

 

=={{header|Cowgol}}==

 

const LIMIT := 20000;

 

=={{header|Crystal}}==

MX = 524_000_000

N = Math.sqrt(MX).to_u32

=={{header|D}}==

{{trans|Python}}

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

 

 

=={{header|Draco}}==

* P[n] is the sum of proper divisors of N */

proc nonrec propdivs([*] word p) void:

 

=={{header|EchoLisp}}==

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

 

=={{header|Ela}}==

{{trans|Haskell}}

 

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

{{trans|C#}}

ELENA 5.0 :

import system'routines;

</pre>

=== Alternative variant using strong-typed closures ===

import system'routines'stex;

import system'collections;

}</syntaxhighlight>

=== Alternative variant using yield enumerator ===

import system'routines'stex;

import system'collections;

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

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

 

-module(properdivs).

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

[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)],

 

We might answer a challenge by saying:

friendly(Limit) ->

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

 

=={{header|ERRE}}==

 

CONST LIMIT=20000

 

=={{header|F_Sharp|F#}}==

[2..20000 - 1]

|> List.map (fun n-> n, ([1..n/2] |> List.filter (fun x->n % x = 0) |> List.sum))

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.

 

USING: grouping math.primes.factors math.ranges ;

 

Calculate many times the divisors.

 

dup 2 / 1+ 1 ?do

dup i mod 0= if i swap then

Use memory to store sum of divisors, a little quicker.

 

 

: proper-divisors ( n -- 1..n )

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.

=={{header|FreeBASIC}}==

===using Mod===

' FreeBASIC v1.05.0 win64

 

</pre>

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

' compile with: fbc -s console

' replaced the function with 2 FOR NEXT loops

=={{header|Frink}}==

This example uses Frink's built-in efficient factorization algorithms. It can work for arbitrarily large numbers.

n = 1

seen = new set

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

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

 

OPENW 1

CLEARW 1

 

=={{header|Go}}==

 

import "fmt"

 

=={{header|Haskell}}==

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

 

Or, deriving proper divisors above the square root as cofactors (for better performance)

 

 

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

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

 

properDivisors=: factors -. -.&1</syntaxhighlight>

 

Amicable pairs:

 

220 284

1184 1210

=={{header|Java}}==

{{works with|Java|8}}

import java.util.function.Function;

import java.util.stream.Collectors;

===ES5===

 

// Proper divisors

|}

 

[6232,6368],[10744,10856],[12285,14595],[17296,18416]]</syntaxhighlight>

 

===ES6===

 

'use strict';

 

 

=={{header|jq}}==

def proper_divisors:

. as $n

task(20000)</syntaxhighlight>

{{out}}

220 and 284 are amicable

1184 and 1210 are amicable

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)

 

=={{header|K}}==

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

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

 

=={{header|Kotlin}}==

 

fun sumProperDivisors(n: Int): Int {

0.02 of a second in 16 lines of code.

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)!

local sum = 1

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

=={{header|MAD}}==

 

DIMENSION DIVS(20000)

PRINT COMMENT $ AMICABLE PAIRS$

{{output?}}

 

with(NumberTheory):

pairs:=[];

 

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

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

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

 

=={{header|MATLAB}}==

tic

N=2:1:20000; aN=[];

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

 

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

 

 

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

MODULE AmicablePairs;

IMPORT

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

 

 

Integer method: properDivs -- []

 

=={{header|OCaml}}==

if n = 1 then 1

else let _n = isqrt (n - 1) in

 

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

{{out}}

<pre>220 284

Amicable! 17296,18416,

 

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

//{$DEFINE ShowOverflow}

===More expansive.===

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

{$IFDEF FPC}

{$MODE DELPHI}

Using "Sieve of Erathosthenes"-style

 

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

beware that >both< numbers must be smaller than MAX

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;

 

=={{header|Phix}}==

<span style="color: #004080;">integer</span> <span style="color: #000000;">n</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>

 

=={{header|Phixmonti}}==

var n

1 var sum n sqrt

=={{header|PHP}}==

 

 

function sumDivs ($n) {

 

Also, the calculation of the sum of divisors is tabled (the table is cleared between each run).

N = 20000,

 

 

=={{header|PicoLisp}}==

(if (assoc Key (val Var))

(con @ (inc (cdr @)))

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

{{trans|REXX}}

ami: Proc Options(main);

p9a=time();

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

Rather than populating an array with the sum of the proper divisors and then searching, the approach here performs an direct test, saving memory, and at a minimal penalty in execution speed, even though about 25% more calls are made to sumf() than would be required simply to initialize an array.

amicable: procedure options (main);

 

 

=={{header|PL/M}}==

/* CP/M CALLS */

BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS;

=={{header|PowerShell}}==

{{works with|PowerShell|2}}

function Get-ProperDivisorSum ( [int]$N )

{

With some guidance from other solutions here:

 

UpperBound is round(sqrt(N)),

between(1, UpperBound, D),

Output:

 

R = [220-284, 1184-1210, 2620-2924, 5020-5564, 6232-6368, 10744-10856, 12285-14595, 17296-18416].</syntaxhighlight>

 

=={{header|PureBasic}}==

EnableExplicit

 

=={{header|Python}}==

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

 

def amicable(rangemax=20000):

Or, supplying our own '''properDivisors''' function, and defining the harvest in terms of a generic '''concatMap''':

 

 

from itertools import chain

<code>properdivisors</code> is defined at [[Proper divisors#Quackery]].

 

dup size 0 = iff

[ drop 0 ] done

=={{header|R}}==

 

divisors <- function (n) {

Filter( function (m) 0 == n %% m, 1:(n/2) )

=={{header|Racket}}==

With [[Proper_divisors#Racket]] in place:

(require "proper-divisors.rkt")

(define SCOPE 20000)

(formerly Perl 6)

{{Works with|Rakudo|2019.03.1}}

my @l = 1 if x > 1;

(2 .. x.sqrt.floor).map: -> \d {

 

=={{header|REBOL}}==

 

sum-of-divisors: func[n /local sum][

 

=={{header|ReScript}}==

Belt.Float.toInt(

sqrt(Belt.Int.toFloat(v)))

=={{header|REXX}}==

===version 1, with factoring===

/*REXX*/

 

 

CPU time consumption note: &nbsp; for every doubling of &nbsp; '''H''' &nbsp; (the upper limit for searches), &nbsp; 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*/

 

The optimization makes it about <u>another</u> &nbsp; '''30%''' &nbsp; 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*/

 

The optimization makes it about <u>another</u> &nbsp; '''20%''' &nbsp; 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*/

 

The optimization makes it about <u>another</u> &nbsp; '''15%''' &nbsp; 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*/

 

=={{header|Ring}}==

size = 18500

for n = 1 to size

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

 

=={{header|Run BASIC}}==

for n = 1 to size

m = amicable(n)

=={{header|Rust}}==

 

(1..val/2+1).filter(|n| val % n == 0)

.fold(0, |sum, n| sum + n)

 

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

=={{header|Scheme}}==

 

(import (scheme base)

(scheme inexact)

 

=={{header|Sidef}}==

n.sigma - n

}

 

=={{header|Swift}}==

 

func sqrt(x:Int) -> Int { return Int(sqrt(Double(x))) }

}</syntaxhighlight>

===Alternative===

 

func sqrt(x:Int) -> Int { return Int(sqrt(Double(x))) }

 

=={{header|tbas}}==

dim sums(20000)

 

 

=={{header|Tcl}}==

if {$n == 1} return

set divs 1

 

=={{header|Transd}}==

#lang transd

 

 

=={{header|uBasic/4tH}}==

Print "Amicable pairs < ";l

 

 

=={{header|UTFool}}==

···

http://rosettacode.org/wiki/Amicable_pairs

 

=={{header|VBA}}==

Public Sub AmicablePairs()

=={{header|VBScript}}==

Not at all optimal. :-(

Set nlookup = CreateObject("Scripting.Dictionary")

Set uniquepair = CreateObject("Scripting.Dictionary")

=={{header|Vlang}}==

{{trans|Go}}

mut sum := 0

for p := 1;p <= i/2;p++{

{{libheader|Wren-fmt}}

{{libheader|Wren-math}}

import "/math" for Int, Nums

 

 

=={{header|XPL0}}==

int Num, Div, Sum, Quot;

[Div:= 2;

=={{header|Yabasic}}==

{{trans|Lua}}

local sum, d

=={{header|zkl}}==

Slooooow

const N=20000;

sums:=[1..N].pump(T(-1),fcn(n){ properDivs(n).sum(0) });

 

=={{header|Zig}}==

 

// Fill up a given array with arr[n] = sum(propDivs(n))

=={{header|ZX Spectrum Basic}}==

{{trans|AWK}}

20 PRINT "Amicable pairs < ";limit

30 FOR n=1 TO limit