Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

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>