Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I used computer program to generate numbers of this form, then verify if they are amicable. However, it took too long to finish, is there any special technique to verify if a pair is amicable?

One pair that I found is $m = 284 = 2^{2}.71, n = 220 = 2^{2}.5.11$

Thanks,
Chan

share|improve this question
    
Did you read the wikipedia article? There is a method for generating such numbers there. en.wikipedia.org/wiki/Amicable_number –  milcak Feb 21 '11 at 5:01
    
@milcak: Thanks for the link. I created a table of first 10,000 odd primes, but it's not practical. Since C(10000, 3) is a really big number. –  Chan Feb 21 '11 at 5:10
add comment

3 Answers 3

up vote 1 down vote accepted

If you are looking for a nice program for finding amicable pairs, there is a related question on stackoverflow.

Here is a code from this question. Hope that helps.

share|improve this answer
    
Thanks for the link. It did help ;) –  Chan Feb 21 '11 at 23:56
add comment

See also Amicable pairs, a survey http://oai.cwi.nl/oai/asset/4143/04143D.pdf Cheers.

share|improve this answer
add comment

This problem was solved by Euler who generalized a rule of Thabit ibn Kurrah, see Breeding Amicable Pairs in Abundance by Borho and Hoffmann for some history. To compute pairs using Euler's rule, choose an integer $0 < j < k$ and let $g$ be $2^{k-j}+1$ and let $b=2^kg-1$, $c=2^jg-1$ and $a=(b+1)(c+1) - 1$. If $a$,$b$ and $c$ are all prime then $m$ and $n$ form an amicable pair, and all such pairs are of this form.

To derive this you plug $m=2^k a$ and $n=2^k bc$ into the definition of an amicable pair you get three equalities that reduce to a quadratic Diophantine equation (ellipse) in two variables. The problem is solved with somewhat more generality in Amicable numbers and the Bilinear Diophantine Equation by Lee. Many (most?) known amicable pairs were derived by some variation of Lee's method (presumably known to Euler).

For this particular problem we have $$ (2^{k+1}-1)(a+1) = (2^{k+1}-1)(b+1)(c+1) = 2^k(a+bc)$$ so $a=(b+1)(c+1)-1$ Substituting, we get $$(2^{k+1}-1)(b+1)(c+1) = 2^k((b+1)(c+1) + bc -1) $$ after some algebra $$bc - (2^k-1)(b+c) = 2^{k+1}-1$$ or $$(b-(2^k-1))(c-(2^k-1))=2^{k+1}-1 + (2^k-1)^2 = 2^{2k}$$ as both $(b-(2^k-1))$ and $(c-(2^k-1))$ are integers that divide $2^{2k}$ they must be of the form $2^j$ and $2^{2k-j}$. So if $b=2^k+2^j-1$ and $c=2^{2k-j}+2^k-1$ as well as $a=(b+1)(c+1)-1$ are all prime, then $(2^ka,2^kbc)$ is an amicable pair, and all such pairs of this form are found by this method.

Here is some python which solves your problem quickly

import sympy
#for primality test

#test 2^x + 2^y - 1 for primality
def goodpair(x,y):
    return sympy.ntheory.isprime(2**x + 2**y - 1)

# j,k pairs giving prime b
bset=set([])

# j,k pairs giving prime c
cset=set([])

#find primes of the form 2^x + 2^y - 1 and store possibilities for b and c
for x in range(1, 70):
    for y in range(x, 71):
        if goodpair(x, y):
            bset.add((x, y))
            if 2 * x > y:
                cset.add((2*x-y,x))

#for cases where both b and c are prime test a = (b+1)(c+1)-1
# for primality, and output pair
for j,k in bset.intersection(cset):
    b = 2**k + 2**j -1
    c = 2**(2 * k - j) + 2**k - 1
    if sympy.ntheory.isprime((b+1)*(c+1)-1):
        print j,k,2**k*((b+1)*(c+1)-1),2**k*b*c
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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