Rosetta Code

Amicable pairs: Difference between revisions

Page Discussion

Amicable pairs (view source)

Revision as of 16:19, 14 March 2024

4,967 bytes added ,  2 months ago
Add ABC
(→‎{{header|Lua}}: Replaced time with time from TIO.RUN, added alternative version that doesn't use division/modulo)
(Add ABC)
 
(19 intermediate revisions by 11 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 2,071 ⟶ 2,098:
12285, 14595
17296, 18416</pre>
 
=={{header|EasyLang}}==
{{trans|Lua}}
<syntaxhighlight lang="easylang">
func sumdivs n .
sum = 1
for d = 2 to sqrt n
if n mod d = 0
sum += d + n div d
.
.
return sum
.
for n = 1 to 20000
m = sumdivs n
if m > n
if sumdivs m = n
print n & " " & m
.
.
.
</syntaxhighlight>
 
=={{header|EchoLisp}}==
Line 2,111 ⟶ 2,160:
=={{header|Elena}}==
{{trans|C#}}
ELENA 56.0x :
<syntaxhighlight lang="elena">import extensions;
import system'routines;
Line 2,120 ⟶ 2,169:
{
ProperDivisors
= Range.new(1,self / 2).filterBy::(n => self.mod:(n) == 0);
get AmicablePairs()
Line 2,126 ⟶ 2,175:
var divsums := Range
.new(0, self + 1)
.selectBy::(i => i.ProperDivisors.summarize(Integer.new()))
.toArray();
^ 1.repeatTill(divsums.Length)
.filterBy::(i)
{
var ii := i;
Line 2,137 ⟶ 2,186:
^ (i < sum) && (sum < divsums.Length) && (divsums[sum] == i)
}
.selectBy::(i => new { Item1 = i; Item2 = divsums[i]; })
}
}
Line 2,143 ⟶ 2,192:
public program()
{
N.AmicablePairs.forEach::(pair)
{
console.printLine(pair.Item1, " ", pair.Item2)
Line 2,169 ⟶ 2,218:
{
Enumerator<int> ProperDivisors
= new Range(1,self / 2).filterBy::(int n => self.mod:(n) == 0);
get AmicablePairs()
Line 2,175 ⟶ 2,224:
auto divsums := new List<int>(
cast Enumerator<int>(
new Range(0, self).selectBy::(int i => i.ProperDivisors.summarize(0))));
^ new Range(0, divsums.Length)
.filterBy::(int i)
{
auto sum := divsums[i];
^ (i < sum) && (sum < divsums.Length) && (divsums[sum] == i)
}
.selectBy::(int i => new Tuple<int,int>(i,divsums[i]));
}
}
Line 2,189 ⟶ 2,238:
public program()
{
N.AmicablePairs.forEach::(var Tuple<int,int> pair)
{
console.printLine(pair.Item1, " ", pair.Item2)
}
}</syntaxhighlight>
 
=== Alternative variant using yield enumerator ===
<syntaxhighlight lang="elena">import extensions;
Line 2,204 ⟶ 2,254:
{
Enumerator<int> function(int number)
= Range.new(1, number / 2).filterBy::(int n => number.mod:(n) == 0);
}
Line 2,218 ⟶ 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,235 ⟶ 2,285:
{
auto e := new AmicablePairs(Limit);
for(auto pair := e.next(),; pair != nil)
{
console.printLine(pair.Item1, " ", pair.Item2)
Line 5,852 ⟶ 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,898 ⟶ 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,913 ⟶ 5,989:
}
}</syntaxhighlight>
 
{{out}}
<pre>
Line 5,923 ⟶ 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,931 ⟶ 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 6,057 ⟶ 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,520 ⟶ 6,700:
=={{header|V (Vlang)}}==
{{trans|Go}}
<syntaxhighlight lang="goGo">fn pfac_sum(i int) int {
fn pfac_sum(i int) int {
mut sum := 0
for p := 1; p <= i / 2; p++{
if i % p == 0 {
sum += p
}
Line 6,539 ⟶ 6,720:
}
}
}
}</syntaxhighlight>
</syntaxhighlight>
 
{{output}}
Line 6,552 ⟶ 6,734:
12285 and 14595
17296 and 18416
 
</pre>
 
Line 6,592 ⟶ 6,773:
{{libheader|Wren-fmt}}
{{libheader|Wren-math}}
<syntaxhighlight lang="ecmascriptwren">import "./fmt" for Fmt
import "./math" for Int, Nums
 
var a = List.filled(20000, 0)
Line 6,601 ⟶ 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,683 ⟶ 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,738 ⟶ 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/346918...361892"