a property of multisets: unit fractions with a twist

[hv at crypt.org]

On Dec 11, 2007 2:19 PM,  <hv at crypt.org> wrote:

> I suspect a bit more work would yield a general approach to finding the
> number of solutions for (1+1/a_1)(1+1/a_2) = x for arbitrary rational x,
> which would at least bring a(7) within range.

The number of solutions to (1+1/a_1)(1+1/a_2) = p/q where p and q are
co-prime integers can be extracted from the prime factorization of N =
p^2 + p*q - q^2. Namely, the number of solutions equals to the number
of divisors of N that are congruent to p modulo q-p.
If we also require that a_1 <= a_2 then we need to restrict our
counting to divisors of N that are <= sqrt(N).

> Reaching a(8) is likely to need something a bit more radical.

Let U be an upper bound for a_8. If U^4 is a reasonable amount of
time/memory then we can apply the classic Meet-In-The-Middle approach.
Namely, we need to generate and store all numbers of the form
(1+1/a_1)(1+1/a_2)(1+1/a_3)(1+1/a_4) where a_i <= U and check whether
there are two such numbers whose product is 2.

Regards,
Max