7
\$\begingroup\$

Two numbers are said to be 'amicable' or 'friends' if the sum of the proper divisors of the first is equal to the second, and viceversa. For example, the proper divisors of 220 are: 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 which sum up to 284. 284's proper divisors are 1, 2, 4, 71 and 142, which sum to 220, thus 220 and 284 are friends. Write a function which returns true if and only if a number is a friend of some other number.

Examples:

friend(220) ==> true

friend(7) ==> false

friend(284) ==> true

Function with least number of chars wins.

NOTE: I just found out that there is a similar question, but I believe this one is simpler and perhaps more general.

\$\endgroup\$
  • \$\begingroup\$ You are missing some divisors, namely: N is a divisor of N. \$\endgroup\$ – Thomas Eding Jul 19 '11 at 20:06
  • \$\begingroup\$ that is true. I need to indicate that N is not included in its divisors.. \$\endgroup\$ – leonardo Jul 19 '11 at 21:01
  • 2
    \$\begingroup\$ You should also indicate the expected return value of friend(6). As of this writing, the winning solution returns true for 6, but 6 is not actually an amicable number (it's perfect). \$\endgroup\$ – Quuxplusone Jul 8 '14 at 20:07

14 Answers 14

4
\$\begingroup\$

Python, 67

a=lambda x:sum(i for i in range(1,x)if x%i<1)
b=lambda x:x==a(a(x))
\$\endgroup\$
  • 2
    \$\begingroup\$ Suggestion xrange(1,x) => range(x) and not x%i to x%i<1 \$\endgroup\$ – Charles Beattie Jul 9 '11 at 14:41
  • \$\begingroup\$ just xrange to range %0 causes an error \$\endgroup\$ – Charles Beattie Jul 9 '11 at 15:10
  • \$\begingroup\$ good tips Charles! \$\endgroup\$ – leonardo Jul 11 '11 at 18:18
  • \$\begingroup\$ Save a char by using a Boolean multiplier in place of the condition: sum(i*(x%i<1)for i in range(1,x)). \$\endgroup\$ – xnor Jul 8 '14 at 23:36
4
\$\begingroup\$

Haskell, 47

o m=sum[x|x<-[1..m-1],m`mod`x<1]
f m=(o.o)m==m

Call the f function (for "friend").
Didn't provide a main because nobody else is doing so.

\$\endgroup\$
  • 1
    \$\begingroup\$ (m-1) -> m-1 \$\endgroup\$ – Thomas Eding Jul 19 '11 at 20:04
  • \$\begingroup\$ @trinithis: thanks \$\endgroup\$ – marinus Jul 20 '11 at 12:02
  • \$\begingroup\$ Haskell was made for problems like this. \$\endgroup\$ – eternalmatt Jul 21 '11 at 1:14
2
\$\begingroup\$

eTeX, 177 (yes, that language is too verbose)

\let~\ifnum\let\c\newcount\c\X\c\D\c\R\def\!{\advance\D1 ~\D<\X~\X=\numexpr\D*\numexpr
\X/\D\advance\R\D\fi\!\fi}\def\a#1{\X#1 \!\X\R\D0\R0 \!\message{~#1=\R YES\else NO\fi}\end}

Used as etex filename.tex "\a{220}".

\$\endgroup\$
  • \$\begingroup\$ nice. i did not know that language exists... \$\endgroup\$ – leonardo Jul 11 '11 at 18:18
  • \$\begingroup\$ It is an extension of {TeX, written by D. E. Knuth}, written by many people, including P. Breitenlohner. (EDIT: added braces to help parse the sentence) \$\endgroup\$ – Bruno Le Floch Jul 11 '11 at 22:06
  • \$\begingroup\$ I think you can trim it down some more by doing something like \let\n\numexpr and \let\v\advance. Also, it seems like everyone else is just implementing a function that returns a boolean; you might be able to save some more characters by converting it to setting a \newif instead of printing a \message. \$\endgroup\$ – ESultanik Jul 20 '11 at 13:30
  • \$\begingroup\$ @ESultanik: when a primitive is used only twice, it is typically not worth doing \let\x\primitive: this uses 10 chars (\let\x and twice \x) plus the length of the primitive instead of twice the length of the primitive. Both \advance and \numexpr take 8 characters, so it's better here to stick with those. \$\endgroup\$ – Bruno Le Floch Jul 25 '11 at 10:38
  • \$\begingroup\$ @Bruno: Oops! For some reason I thought it would save a character or two; I must have messed up the arithmetic in my head. Sorry about that. \$\endgroup\$ – ESultanik Jul 25 '11 at 12:22
1
\$\begingroup\$

Scala, 67

def d(n:Int)=(1 to n-1).filter(n%_==0).sum
def f(n:Int)=d(d(n))==n
\$\endgroup\$
1
\$\begingroup\$

Ruby, 95

l=lambda{|n|(1..n-1).select{|e|n.modulo(e)==0}.reduce(:+)}
m=lambda{|n|(l.call(l.call(n))==n)}
\$\endgroup\$
1
\$\begingroup\$

Ruby 1.9, 57 characters

s=->n{eval (1...n).select{|a|n%a<1}*?+}
f=->n{s[s[n]]==n}

Pretty similar to all the other solutions here.

\$\endgroup\$
1
\$\begingroup\$

J, 24 characters

The pure answer is this:

=(+/&(((0:=|~)#])i.))^:2

It's a monad that takes a scalar and returns 0 or 1 if it's a friend or not. Unfortunately J precedence rules make it impossible to use with no separator from its argument. I'm keeping the character count as such because of the way the question is worded. Anyway, here's a demonstration of three possible ways to use it:

   NB. using a named verb
   f =: =(+/&(((0:=|~)#])i.))^:2
   f 220
1
   NB. using parentheses
   (=(+/&(((0:=|~)#])i.))^:2) 7
0
   NB. using verb "Same"
   =(+/&(((0:=|~)#])i.))^:2 [ 284
1

Obligatory J unscrambling:

  • i. 220 returns the list of naturals below 220 (0, 1, 2 to 219)
  • (|~i.) 220 divides them all by 220 and returns the remainder
  • ((0:=|~)i.) 220 compares to 0 (returns boolean as 0 or 1)
  • (((0:=|~)#])i.) 220 returns the natural where the 1s were. In effect: returns the full divisor list.
  • (+/&(((0:=|~)#])i.)) 220 sums them.
  • ((+/&(((0:=|~)#])i.))^:2) 220 performs the operation twice.
  • (=(+/&(((0:=|~)#])i.))^:2) 220 checks we fall back on the initial argument.
\$\endgroup\$
1
\$\begingroup\$

APL (23)

Let me halve my score after 3 years of golfing. :)

This needs the function trains added to Dyalog APL 14, so it doesn't work on earlier versions, which at the moment of writing unfortunately includes the free (unregistered) version. It does work on TryAPL.

f←{+/∆×0=⍵|⍨∆←⍳⍵-1}⍣2=+

Or:

({+/∆×0=⍵|⍨∆←⍳⍵-1}⍣2=+)

(Because it involves a function train, it needs to be either parenthesized or named in order to use it. They both have the same character count, but the first needs to be entered and then called as f 220, the second needs to have its argument added to the right of it.)

Explanation:

  • {...}⍣2=+: compare the argument to the result of running the function twice on the argument, return 1 if true and 0 if false
    • ∆←⍳⍵-1: get all the numbers from 1 to ⍵-1 and store them in ∆.
    • 0=⍵|⍨∆: get a binary vector which is 1 where ⍵ mod ∆ is 0 and 0 elsewhere
    • +/∆×: multiply ∆ by it and return the sum
\$\endgroup\$
1
\$\begingroup\$

Brachylog, 11 bytes

fk+Xfk+?;X≠

Try it online!

Takes input through the input variable and outputs through success or failure.

fk+            The proper divisor sum of
               the input
   X           is X,
    fk+        and its proper divisor sum
       ?       is the input,
        ;X≠    which is not equal to X.
\$\endgroup\$
0
\$\begingroup\$

Q, 42 33

{x={0+/a(&)0=x mod a:(!)6h$(1+x%2)}/[2;x]}

shorter by not limiting the check for divisors to enumerations up to n/2 but obviously slower as a result:

{x={0+/a(&)0=x mod a:(!)x}/[2;x]}

timing

q)\t {x={0+/a(&)0=x mod a:(!)x}/[2;x]} 2200000
289
q)\t {x={0+/a(&)0=x mod a:(!)6h$(1+x%2)}/[2;x]} 2200000
124
\$\endgroup\$
0
\$\begingroup\$

JavaScript (E6) 57

F=n=>(S=n=>{for(t=d=1;++d<n;)n%d||(t+=d)},S(n),S(t),t==n)
\$\endgroup\$
0
\$\begingroup\$

Pyth, 22 characters

DAdRsf!%dTr1dDMkRqkAAk

Explanation:

DAd          def A(d):
Rs           return sum(
f!%dT        filter on condition (not d%T)
r1d          for T in range(1,T)
DMk          def M(k):
R            return
qkAAk        k==A(A(k))
\$\endgroup\$
0
\$\begingroup\$

05AB1E, 7 bytes

ѨOѨOQ

Try it online!

Pretty straightforward. Ѩ takes the list of divisors without the element itself, O sums these up. Q checks if after two iterations the result and the input are equal.

Returns 1 if the number is amicable, else 0.

\$\endgroup\$
-2
\$\begingroup\$

GolfScript (25 chars)

{.{:a,(\{.a\%!*+}/}2*=}:f

a can, of course, be replaced by the name of any other variable whose contents you don't care about.

\$\endgroup\$

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.