Call an integer lucky if it is a sum of positive integers (not necessarily distinct) whose reciprocals sum to 1. For example, 4 and 11 are lucky: 4=2+2 and 1/2+1/2=1, and 11=2+3+6 and 1/2+1/3+1/6=1. But 2, 3, and 5 are unlucky. How many unlucky positive integers are there?

To start off, realize that half of the total can be taken away, with successive powers of two removed from the "goal integer". For example, 10 is lucky because 1/2 + 1/4 + 1/4 = 1.

 To reach a fraction 1/n using two fractions, it takes 1/a + (a-n)/(na). In terms of the amount needed from the goal integer, it's a + (na)/(a-n) or (a^2 -  an + na)/(a-n) which equals just (a^2)/(a-n)

If a=2n, then one way to get 1/n is to simply use 1/(n+1) and 1/n(n+1). To generalize, the only way (a^2) will be divisible by (a-n) is if na/(a-n) is an integer.

Starting with 1, the only way a/(a-1) could be an integer is if a = 2. So all sequences adding up to 1 will begin with 1/2.

Then, 2a/(a-2) can only be an integer if a=3, 4, or 6, which shows the next possible fractions. Proceeding to the third step gives these possible solutions: (Notice that the last value in each sequence becomes the n value for the sequences with one more fraction.)

1/2, 1/2

1/2, 1/3, 1/6
1/2, 1/4, 1/4
1/2, 1/6, 1/3

1/2, 1/3, 1/12, 1/12
1/2, 1/3, 1/24, 1/8

1/2, 1/4, 1/8, 1/8
1/2, 1/4, 1/12, 1/6
1/2, 1/4, 1/20, 1/5

1/2, 1/6, 1/6, 1/6
1/2, 1/6, 1/12, 1/4

Posted by Gamer on 2005-02-21 02:53:01