Re: Very Long Time

*To*: mathgroup at smc.vnet.net*Subject*: [mg93907] Re: Very Long Time*From*: "Max Alekseyev" <maxale at gmail.com>*Date*: Fri, 28 Nov 2008 05:08:31 -0500 (EST)*References*: <200811271034.FAA08892@smc.vnet.net> <492ED29A.5010009@csl.pl>

Solving A*k*m+k+m=B is equivalent to solving (A*k + 1) * (A*m + 1) = A*B + 1 Therefore, the solutions to A*k*m+k+m=B correspond to the factors of A*B + 1 of the form A*n + 1. There seems to be no faster way to find all such factors than through complete factorization of A*B + 1. Regards, Max On Thu, Nov 27, 2008 at 9:02 AM, Artur <grafix at csl.pl> wrote: > Dear Mathematica Gurus, > > Who know how solving some class of Diophantine equatons by Mathematica in > reasonable time. > We have following Diophantine equation: A*k*m+k+m=B > A,B are given naturals, we looking for such naturals k,m that k*m<>0 > how to solve these equation for big B in reasonable time? > > I was try first exaple B=1843857004 A=54 > Timing[FindInstance[ > 54 k m + k + m == 1843857004 && k != 0 && m != 0, {k, m}, Integers]] > {0.016, {{k -> 4864, m -> 7020}}} > > Timing[Reduce[ > 54 k m + k + m == 1843857004 && k != 0 && m != 0 && k != 0 && > m != 0, {k, m}, Integers]] > {0.047, (k == 4864 && m == 7020) || (k == 7020 && m == 4864)} > > Timing[Reduce[ > 54 k m + k + m == ((262657*379081 - 1)/54) && k != 0 && m != 0 && > k != 0 && m != 0 && k > m, {k, m}, Integers]] > {0.062, k == 7020 && m == 4864} > > From above FindInstance is the quickest > > but if we take B= > 736729797087357448184410542139771135990102993313523027084638777\ > 4309538710053853199454401451104774708512884704730299539382767443852673\ > 02777886375263112884026366363884 > > Time isn't reasonable (break after 24 hours) > > good answer is > {k,m}={727895002228489854007832696673503237524097714965167217462016598121576\ > 3162404, 1874328625521180412053722977555618980556822557375169650791105\ > 349846461206264341893746440} > > Mayby is necessary add additional Mathematical rule to algorhitm > > e.g. > A*k*m+k+m=B > let m=k+x > > and we have square equation > > with roots > k1=(-2 - A x + Sqrt[4 + 4 A B + A^2 x^2])/(2 A) > k2=(-2 - A x + Sqrt[4 + 4 A B + A^2 x^2])/(2 A) > > Now necessery condition to k naturals is > 4 + 4 A B + A^2 x^2] have to be square > let > 4 + 4 A B + A^2 x^2=y^2 > Let : > A x=z > 4 + 4 A B =t > and we have diophantine equation with two squares > t + z^2 =y^2 > t=(y-z)(y+z) > > I would like to thank on advance for any help or idea! > > Best wishes > Artur >

**References**:**Numerical General Relativity packages***From:*magma <maderri2@gmail.com>