Amicable pairs: Difference between revisions
(Promote from draft to full task status.) |
(Add ref.) |
||
Line 10: | Line 10: | ||
* [[Proper divisors]] |
* [[Proper divisors]] |
||
* [[Abundant, deficient and perfect number classifications]] |
* [[Abundant, deficient and perfect number classifications]] |
||
* [[Aliquot sequence classifications]] and its amicable ''classification''. |
|||
=={{header|D}}== |
=={{header|D}}== |
Revision as of 09:02, 20 December 2014
You are encouraged to solve this task according to the task description, using any language you may know.
Two integers and are said to be amicable pairs if and the sum of the proper divisors of () as well as .
For example 1184 and 1210 are an amicable pair (with proper divisors 1, 2, 4, 8, 16, 32, 37, 74, 148, 296, 592 and 1, 2, 5, 10, 11, 22, 55, 110, 121, 242, 605 respectively).
- Task
Calculate and show here the Amicable pairs below 20,000; (there are eight).
- Cf.
- Proper divisors
- Abundant, deficient and perfect number classifications
- Aliquot sequence classifications and its amicable classification.
D
<lang d>void main() /*@safe @nogc*/ {
import std.stdio, std.algorithm, std.range, std.typecons, std.array;
immutable properDivs = (in uint n) pure nothrow @safe /*@nogc*/ => iota(1, (n + 1) / 2 + 1).filter!(x => n % x == 0);
enum rangeMax = 20_000; auto n2d = iota(1, rangeMax + 1).map!(n => properDivs(n).sum);
foreach (immutable n, immutable divSum; n2d.enumerate(1)) if (n < divSum && divSum <= rangeMax && n2d[divSum - 1] == n) writefln("Amicable pair: %d and %d with proper divisors:\n %s\n %s", n, divSum, properDivs(n), properDivs(divSum));
}</lang>
- Output:
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]
J
Proper Divisor implementation:
<lang J>factors=: [: /:~@, */&>@{@((^ i.@>:)&.>/)@q:~&__ properDivisors=: factors -. -.&1</lang>
Amicable pairs:
<lang J> 1+0 20000 #:I.,(</~@i.@#*(*|:))(=/ +/@properDivisors@>) 1+i.20000
220 284 1184 1210 2620 2924 5020 5564 6232 6368
10744 10856 12285 14595 17296 18416</lang>
Python
Importing Proper divisors from prime factors: <lang python>from proper_divisors import proper_divs
def amicable(rangemax=20000):
n2divsum = {n: sum(proper_divs(n)) for n in range(1, rangemax + 1)} for num, divsum in n2divsum.items(): if num < divsum and divsum <= rangemax and n2divsum[divsum] == num: yield num, divsum
if __name__ == '__main__':
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))))</lang>
- Output:
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]
Ruby
With proper_divisors#Ruby in place: <lang ruby>h = {} (1..20_000).each{|n| h[n] = n.proper_divisors.inject(:+)} 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 </lang>
- Output:
220 and 284 1184 and 1210 2620 and 2924 5020 and 5564 6232 and 6368 10744 and 10856 12285 and 14595 17296 and 18416
Tcl
<lang tcl>proc properDivisors {n} {
if {$n == 1} return set divs 1 set sum 1 for {set i 2} {$i*$i <= $n} {incr i} {
if {!($n % $i)} { lappend divs $i incr sum $i if {$i*$i < $n} { lappend divs [set d [expr {$n / $i}]] incr sum $d } }
} return [list $sum $divs]
}
proc amicablePairs {limit} {
set result {} set sums [set divs {{}}] for {set n 1} {$n < $limit} {incr n} {
lassign [properDivisors $n] sum d lappend sums $sum lappend divs [lsort -integer $d]
} for {set n 1} {$n < $limit} {incr n} {
set nsum [lindex $sums $n] for {set m 1} {$m < $n} {incr m} { if {$n==[lindex $sums $m] && $m==$nsum} { lappend result $m $n [lindex $divs $m] [lindex $divs $n] } }
} return $result
}
foreach {m n md nd} [amicablePairs 20000] {
puts "$m and $n are an amicable pair with these proper divisors" puts "\t$m : $md" puts "\t$n : $nd"
}</lang>
- Output:
220 and 284 are an amicable pair with these proper divisors 220 : 1 2 4 5 10 11 20 22 44 55 110 284 : 1 2 4 71 142 1184 and 1210 are an amicable pair with these proper divisors 1184 : 1 2 4 8 16 32 37 74 148 296 592 1210 : 1 2 5 10 11 22 55 110 121 242 605 2620 and 2924 are an amicable pair with these proper divisors 2620 : 1 2 4 5 10 20 131 262 524 655 1310 2924 : 1 2 4 17 34 43 68 86 172 731 1462 5020 and 5564 are an amicable pair with these proper divisors 5020 : 1 2 4 5 10 20 251 502 1004 1255 2510 5564 : 1 2 4 13 26 52 107 214 428 1391 2782 6232 and 6368 are an amicable pair with these proper divisors 6232 : 1 2 4 8 19 38 41 76 82 152 164 328 779 1558 3116 6368 : 1 2 4 8 16 32 199 398 796 1592 3184 10744 and 10856 are an amicable pair with these proper divisors 10744 : 1 2 4 8 17 34 68 79 136 158 316 632 1343 2686 5372 10856 : 1 2 4 8 23 46 59 92 118 184 236 472 1357 2714 5428 12285 and 14595 are an amicable pair with these proper divisors 12285 : 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 14595 : 1 3 5 7 15 21 35 105 139 417 695 973 2085 2919 4865 17296 and 18416 are an amicable pair with these proper divisors 17296 : 1 2 4 8 16 23 46 47 92 94 184 188 368 376 752 1081 2162 4324 8648 18416 : 1 2 4 8 16 1151 2302 4604 9208