|
|
back to boardis 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 |
|
|