Amicable pairs: Difference between revisions
→{{header|Tcl}}: Added zkl |
|||
Line 457: | Line 457: | ||
17296 : 1 2 4 8 16 23 46 47 92 94 184 188 368 376 752 1081 2162 4324 8648 |
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 |
18416 : 1 2 4 8 16 1151 2302 4604 9208 |
||
</pre> |
|||
=={{header|zkl}}== |
|||
Slooooow |
|||
<lang zkl>fcn properDivs(n){ [1.. (n + 1)/2 + 1].filter('wrap(x){ n%x==0 and n!=x }) } |
|||
dns:=[1..20000].pump(Dictionary(20000),fcn(n){ return(n,properDivs(n).sum(0)) }); |
|||
dns.filter('wrap([(k,v)]){ k=k.toInt(); (k<v) and dns.find(v)==k }) |
|||
.apply("apply","toInt").println();</lang> |
|||
Dictionary keys are strings so there are several conversions back to int. |
|||
{{out}} |
|||
<pre> |
|||
L(L(6232,6368),L(220,284),L(17296,18416),L(1184,1210),L(2620,2924),L(5020,5564),L(10744,10856),L(12285,14595)) |
|||
</pre> |
</pre> |
Revision as of 20:22, 26 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.
AutoHotkey
<lang d>SetBatchLines -1 Loop, 20000 { m := A_index
; Getting factors loop % floor(sqrt(m)) { if ( mod(m, A_index) = 0 ) { if ( A_index ** 2 == m ) { sum += A_index continue } else if ( A_index != 1 ) { sum += A_index + m//A_index } else if ( A_index = 1 ) { sum += A_index } } } ; Factors obtained
; Checking factors of sum if ( sum > 1 ) { loop % floor(sqrt(sum)) { if ( mod(sum, A_index) = 0 ) { if ( A_index ** 2 == sum ) { sum2 += A_index continue } else if ( A_index != 1 ) { sum2 += A_index + sum//A_index } else if ( A_index = 1 ) { sum2 += A_index } } } if ( m = sum2 ) && ( m != sum ) && ( m < sum ) final .= m . ":" . sum . "`n" } ; Checked
sum := 0 sum2 := 0 } MsgBox % final ExitApp</lang>
- Output:
220:284 1184:1210 2620:2924 5020:5564 6232:6368 10744:10856 12285:14595 17296:18416
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>
PL/I
<lang pli>*process source xref;
ami: Proc Options(main); p9a=time(); Dcl (p9a,p9b,p9c) Pic'(9)9'; Dcl sumpd(20000) Bin Fixed(31); Dcl pd(300) Bin Fixed(31); Dcl npd Bin Fixed(31); Dcl (x,y) Bin Fixed(31);
Do x=1 To 20000; Call proper_divisors(x,pd,npd); sumpd(x)=sum(pd,npd); End; p9b=time(); Put Edit('sum(pd) computed in',(p9b-p9a)/1000,' seconds elapsed') (Skip,col(7),a,f(6,3),a);
Do x=1 To 20000; Do y=x+1 To 20000; If y=sumpd(x) & x=sumpd(y) Then Put Edit(x,y,' found after ',elapsed(),' seconds') (Skip,2(f(6)),a,f(6,3),a); End; End; Put Edit(elapsed(),' seconds total search time')(Skip,f(6,3),a);
proper_divisors: Proc(n,pd,npd); Dcl (n,pd(300),npd) Bin Fixed(31); Dcl (d,delta) Bin Fixed(31); npd=0; If n>1 Then Do; If mod(n,2)=1 Then /* odd number */ delta=2; Else /* even number */ delta=1; Do d=1 To n/2 By delta; If mod(n,d)=0 Then Do; npd+=1; pd(npd)=d; End; End; End; End;
sum: Proc(pd,npd) Returns(Bin Fixed(31)); Dcl (pd(300),npd) Bin Fixed(31); Dcl sum Bin Fixed(31) Init(0); Dcl i Bin Fixed(31); Do i=1 To npd; sum+=pd(i); End; Return(sum); End;
elapsed: Proc Returns(Dec Fixed(6,3)); p9c=time(); Return((p9c-p9b)/1000); End; End;</lang>
- Output:
sum(pd) computed in 0.510 seconds elapsed 220 284 found after 0.010 seconds 1184 1210 found after 0.060 seconds 2620 2924 found after 0.110 seconds 5020 5564 found after 0.210 seconds 6232 6368 found after 0.260 seconds 10744 10856 found after 2.110 seconds 12285 14595 found after 2.150 seconds 17296 18416 found after 2.240 seconds 2.250 seconds total search time
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]
Racket
With Abundant,_deficient_and_perfect_number_classifications#Racket in place: <lang racket>#lang racket (require "sum-of-divisors.rkt") (define SCOPE 20000)
- returns #f if not an amicable number, amicable pairing otherwise
(define (amicable? n)
(define m (P n)) (define m-sod (P m)) (and (= m-sod n) (< m n) ; each pair exactly once, also eliminates perfect numbers m))
(void (amicable? SCOPE)) ; prime the memoisation
(for* ((n (in-range 1 (add1 SCOPE)))
(m (in-value (amicable? n))) #:when m) (printf #<<EOS
amicable pair: ~a, ~a
~a: divisors: ~a ~a: divisors: ~a
EOS
n m n (proper-divisors n) m (proper-divisors m)))
</lang>
- Output:
amicable pair: 284, 220 284: divisors: (1 2 4 71 142) 220: divisors: (1 2 4 5 10 11 20 22 44 55 110) amicable pair: 1210, 1184 1210: divisors: (1 2 5 10 11 22 55 110 121 242 605) 1184: divisors: (1 2 4 8 16 32 37 74 148 296 592) amicable pair: 2924, 2620 2924: divisors: (1 2 4 17 34 43 68 86 172 731 1462) 2620: divisors: (1 2 4 5 10 20 131 262 524 655 1310) amicable pair: 5564, 5020 5564: divisors: (1 2 4 13 26 52 107 214 428 1391 2782) 5020: divisors: (1 2 4 5 10 20 251 502 1004 1255 2510) amicable pair: 6368, 6232 6368: divisors: (1 2 4 8 16 32 199 398 796 1592 3184) 6232: divisors: (1 2 4 8 19 38 41 76 82 152 164 328 779 1558 3116) amicable pair: 10856, 10744 10856: divisors: (1 2 4 8 23 46 59 92 118 184 236 472 1357 2714 5428) 10744: divisors: (1 2 4 8 17 34 68 79 136 158 316 632 1343 2686 5372) amicable pair: 14595, 12285 14595: divisors: (1 3 5 7 15 21 35 105 139 417 695 973 2085 2919 4865) 12285: 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) amicable pair: 18416, 17296 18416: divisors: (1 2 4 8 16 1151 2302 4604 9208) 17296: divisors: (1 2 4 8 16 23 46 47 92 94 184 188 368 376 752 1081 2162 4324 8648)
REXX
<lang rexx>Call time 'R' Do x=1 To 20000
pd=proper_divisors(x) sumpd.x=sum(pd) End
Say 'sum(pd) computed in' time('E') 'seconds' Call time 'R' Do x=1 To 20000
/* If x//1000=0 Then Say x time() */ Do y=x+1 To 20000 If y=sumpd.x &, x=sumpd.y Then Say x y 'found after' time('E') 'seconds' End End
Say time('E') 'seconds total search time' Exit
proper_divisors: Procedure Parse Arg n Pd= If n=1 Then Return If n//2=1 Then /* odd number */
delta=2
Else /* even number */
delta=1
Do d=1 To n%2 By delta
If n//d=0 Then pd=pd d End
Return space(pd)
sum: Procedure Parse Arg list sum=0 Do i=1 To words(list)
sum=sum+word(list,i) End
Return sum</lang>
- Output:
sum(pd) computed in 48.502000 seconds 220 284 found after 3.775000 seconds 1184 1210 found after 21.611000 seconds 2620 2924 found after 46.817000 seconds 5020 5564 found after 84.296000 seconds 6232 6368 found after 100.918000 seconds 10744 10856 found after 150.126000 seconds 12285 14595 found after 162.124000 seconds 17296 18416 found after 185.600000 seconds 188.836000 seconds total search time
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
zkl
Slooooow <lang zkl>fcn properDivs(n){ [1.. (n + 1)/2 + 1].filter('wrap(x){ n%x==0 and n!=x }) } dns:=[1..20000].pump(Dictionary(20000),fcn(n){ return(n,properDivs(n).sum(0)) }); dns.filter('wrap([(k,v)]){ k=k.toInt(); (k<v) and dns.find(v)==k })
.apply("apply","toInt").println();</lang>
Dictionary keys are strings so there are several conversions back to int.
- Output:
L(L(6232,6368),L(220,284),L(17296,18416),L(1184,1210),L(2620,2924),L(5020,5564),L(10744,10856),L(12285,14595))