is there any solution for this problem that is not based on the exhaustive search?

Google aliquot fractions

Yes, there is. I recursively try all denominators <= 100000 walking on primes - this way I automatically get all of its divisors at no cost and then DP in order to sum up to nominator using <20 of denoninator's divisors. Interestingly, the bigger the limit, the faster it performs.

Next reasoning should work:

if (1/(n+1)<A<1/n => A=1/(n+1)+B,
where B<1/(n*(n+1)) and
cannot contain 1/(n+1) again
Thus 1/v1,1/v2,... is basis
that converges to A very quickly
A is rational then
sequence must be finite

It's true, but there exists the limit for a denominator of fractions in this problem. I tried this algo in my first solution, and got WA#3.

Edited by author 01.12.2015 19:01