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}}}