Re: Solving Diophantine Equations
- To: mathgroup at smc.vnet.net
- Subject: [mg61324] Re: Solving Diophantine Equations
- From: "Ray Koopman" <koopman at sfu.ca>
- Date: Fri, 14 Oct 2005 22:23:42 -0400 (EDT)
- References: <32592565.1129236555309.JavaMail.root@elwamui-darkeyed.atl.sa.earthlink.net> <9F2DCCEC-34BF-4F53-9475-F686A911F260@akikoz.net> <E39C9EDB-A88A-42F3-9AD9-7DA09C7D790A@yhc.att.ne.jp> <dio1s4$suo$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
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}}}