is there a solution?

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

Re: is there a solution?

Posted by

MikleB 14 Mar 2007 01:35

Google aliquot fractions

Re: is there a solution?

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.

Re: is there a solution?

Posted by

svr 6 Jan 2011 08:49

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

Re: is there a solution?

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*