MathGroup Archive 2005

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

Search the Archive

Re: Solving Diophantine Equations


Andrzej Kozlowski wrote:
> That was wrong again! Trying to write these loops is so frustrating,
> perhaps I should go back to functional programming... Anyway, I think
> and hope this is now right at last:
>
> g[a_, b_, c_:5] := Block[{y, ls = {}, x, n},
>     Do[ y = 2; While[(y^n - y^2)/((y - 1)*y) < a,
>       Do[If[(x^3 - 1)/(x - 1) == (y^n - 1)/(y - 1) &&
>            x != y, ls = {ls, {x, y, n}}],
>          {x, y^((n - 1)/2), (y^n - y^2)/((y - 1)*y)}];
>         y++], {n, c, b, 2}]; ls]
>
>
> It is certainly not easy to find solutions, though, pretty big
> searches so far have yielded just two, e.g.
>
> In[69]:=
> g[100000,30]//Timing
>
> Out[69]=
> {58.0157 Second,{{{},{5,2,5}},{90,2,13}}}
>
> [...]

Procedural code such as this often benefits from the old
standard tricks such as moving computations outside the loop
and replacing division by multiplication.

In[1]:=
g[a_, b_, c_:5] := Block[{y, ls = {}, x, n},
Do[y = 2;
   While[(y^n - y^2)/((y - 1)*y) < a,
         Do[If[(x^3 - 1)/(x - 1) == (y^n - 1)/(y - 1) && x != y,
               ls = {ls, {x, y, n}}],
            {x, y^((n - 1)/2), (y^n - y^2)/((y - 1)*y)}];
         y++],
   {n, c, b, 2}];
ls]

In[2]:=
gg[a_, b_, c_:5] := Block[{y, x, n, r}, Reap[
Do[y = 2;
   While[y^(n-1) - y < (y - 1)a,
         r = (y^n - 1)/(y - 1);
         Do[If[x != y && (x+1)x+1 == r, Sow[{x, y, n}]],
            {x, y^((n-1)/2), (y^(n-1) - y)/(y - 1)}];
         y++],
   {n, c, b, 2}]][[2,1]]]

In[3]:= g[10^5,30]//Timing
       gg[10^5,30]//Timing

Out[3]= {30.28 Second,{{{},{5,2,5}},{90,2,13}}}
Out[4]= {11.09 Second,{{5,2,5},{90,2,13}}}


  • Prev by Date: Re: VECTOR coordinate transformation?
  • Next by Date: Re: Re: Re: Language vs. Library why it matters
  • Previous by thread: Re: Solving Diophantine Equations
  • Next by thread: Re: Solving Diophantine Equations