Services & ResourcesWolfram ForumsMathGroup Archive

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

Very Long Time

• To: mathgroup at smc.vnet.net
• Subject: [mg93899] Very Long Time
• From: Artur <grafix at csl.pl>
• Date: Fri, 28 Nov 2008 05:07:04 -0500 (EST)
• References: <200811271034.FAA08892@smc.vnet.net>
• Reply-to: grafix at csl.pl

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>