6
\$\begingroup\$

Write a program that calculates amicable numbers, starting from [0,0], intil the maximum value for an integer is reached in the language you chose to write it in.

Amicable numbers are two different numbers so related that the sum of the proper divisors of each is equal to the other number. (A proper divisor of a number is a positive integer divisor other than the number itself. For example, the proper divisors of 6 are 1, 2, and 3.) A pair of amicable numbers constitutes an aliquot sequence of period 2. A related concept is that of a perfect number, which is a number which equals the sum of its own proper divisors, in other words a number which forms an aliquot sequence of period 1. Numbers that are members of an aliquot sequence with period greater than 2 are known as sociable numbers.

For example, the smallest pair of amicable numbers is (220, 284); for the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110, of which the sum is 284; and the proper divisors of 284 are 1, 2, 4, 71, and 142, of which the sum is 220.

If you want more information on amicable numbers, here's a link to Wikipedia's entry on the subject.

NOTE: It cannot use pre-determined tables of which are and which are not amicable numbers

EDIT: I suppose I should have said how I will determine the winner:
Your score will be calculated by this formula: Total_characters_of_code / Up_votes = Score
I will select an answer on Sunday, May 1.
The lowest score wins!

\$\endgroup\$
  • \$\begingroup\$ What do you mean "starting from 0,0"? I hope you're not suggesting that 0,0 is a pair of amicable numbers, because if so you're disagreeing with the reference you provided. \$\endgroup\$ – Peter Taylor Apr 27 '11 at 18:36
  • 1
    \$\begingroup\$ 0, 0 are amicable numbers. 0 has no factors, so the sum of both of their factors are 0. \$\endgroup\$ – Ry- Apr 27 '11 at 19:29
  • 5
    \$\begingroup\$ Now to find a language where the maximum integer is very tiny.... ;) \$\endgroup\$ – Casey Apr 27 '11 at 20:24
  • 1
    \$\begingroup\$ In fact, thinking a bit more about 0, I think I have to argue that the aliquot number of 0 is undefined, because every positive integer divides into it without remainder. \$\endgroup\$ – Peter Taylor Apr 28 '11 at 11:00
  • 1
    \$\begingroup\$ You'll select an answer Sunday, March 1? Seeing as it's already Saturday, April 30, I'm not sure if you really mean to wait that long ;) \$\endgroup\$ – Ry- May 1 '11 at 3:08
5
\$\begingroup\$

Golfscript (51 50 chars)

2{.{:a,(\{.a\%!*+}/}:^~1$>{..^^={[..^](\p}*}*).}do

The core is the override of ^ as :a,(\{.a\%!*+}/ which finds the aliquot of the number on the top of the stack (call it n) by the grossly inefficient approach of considering every number from 1 to n-1 to see whether it's a factor.

\$\endgroup\$
  • \$\begingroup\$ Score for this post: 25.5 \$\endgroup\$ – Nate Koppenhaver May 1 '11 at 23:23
  • \$\begingroup\$ Now it's 10, just for the record. \$\endgroup\$ – nyuszika7h Jul 8 '14 at 20:38
3
\$\begingroup\$

C (gcc), 162, 158, 146, 138 chars

s(n){int x=1,i=2;for(;i<=sqrt(n);++i)if(n%i==0)x+=i+n/i;return x;}main(i,a){for(;;)a=s(i),((a>i)?s(a):0)==i++?printf("%d,%d\n",i-1,a):0;}

compile with gcc using gcc amic.c -o amic -lm -include math.h

To shorten it any further I suspect the algorithm would have to change.

Edits:

162->158: Consolidated the variable b into the printf conditional.

158->146: Utilized main to declare a instead of using a global var, also using implicit int of the parameter and return type for the function s(n)

146->138: Add Lowjacker's suggestion of removing the cast to double. Thanks!

\$\endgroup\$
  • 1
    \$\begingroup\$ You can change (a>i)? to a>i? . The operator precedence for ?: is a few rows down from the relational operators. \$\endgroup\$ – Joey Adams Apr 28 '11 at 2:32
  • \$\begingroup\$ Score for this post: 46 \$\endgroup\$ – Nate Koppenhaver May 1 '11 at 23:22
  • \$\begingroup\$ I´m sorry to tell you but your algorithm for s(n) is incorrect. Assume n is a square number, then you would add sqrt(n) to the sum of divisors twice. It´s cool that tried to optimize it, but for golfing purposes, you´d better go for "i<n.... x*=i; Also if you want optimized runtime, i*i<n is the faster choice. \$\endgroup\$ – Moartem Jul 23 '15 at 22:03
2
\$\begingroup\$

Scala (120 chars):

def d(n:Int)=(1 to n-1).filter(n%_==0)
def i(x:Int,y:Int)=x!=y&&d(y).sum==x
(1 to Int.MaxValue).filter(x=>i(x,d(x).sum))
\$\endgroup\$
1
\$\begingroup\$

Ruby 1.9, 126 124

Not quite a serious answer, but it's theoretically correct. If you're really patient, and have lots of RAM, it should eventually print every pair of amicable numbers.

s=->n{eval (1...n).select{|i|n%i==0}*?+}
i=0
loop{Thread.new(i+=1){|j,k=j|loop{s[k+=1]==j&&s[j]==k&&printf("%d,%d\n",j,k)}}}
\$\endgroup\$
  • \$\begingroup\$ Score for this post: 124 \$\endgroup\$ – Nate Koppenhaver May 1 '11 at 23:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.