# Find amicable pair numbers of the from $m = 2^{k}a, n = 2^{k}bc$, where $k < 35$ and a, b, c are odd primes?

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

-
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

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.

-
Thanks for the link. It did help ;) –  Chan Feb 21 '11 at 23:56

-

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):