Re: Solving Diophantine Equations

*To*: mathgroup at smc.vnet.net*Subject*: [mg61289] Re: [mg61185] Solving Diophantine Equations*From*: Andrzej Kozlowski <andrzej at yhc.att.ne.jp>*Date*: Fri, 14 Oct 2005 05:56:09 -0400 (EDT)*References*: <32592565.1129236555309.JavaMail.root@elwamui-darkeyed.atl.sa.earthlink.net> <9F2DCCEC-34BF-4F53-9475-F686A911F260@akikoz.net>*Reply-to*: Andrzej Kozlowski <andrzej at akikoz.net>*Sender*: owner-wri-mathgroup at wolfram.com

I only now noticed Mike's post and observed that he found a solution I never managed to notice so far, namely {90, 2, 13}. So I checked my program and sure enough it is wrong: y is incremented but never reset to the original value. Here is the corret version: g[a_, b_, c_:5] := Block[{y = 2, ls = {}, x, n}, Do[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++]; y = 2;, {n, c, b, 2}]; ls] Now it can find the two solutions very fast, e.g. In[44]:= g[10000,30]//Timing Out[44]= {2.64865 Second,{{{},{5,2,5}},{90,2,13}}} but so far I have not found any more (however, I only just corrected the error in the program). Andrzej On 14 Oct 2005, at 06:56, Andrzej Kozlowski wrote: > One more thing. It might be better to change Module in my last code > to Block. Here is a new version: > > g[a_, b_,c_:5] := Block[{y = 2, ls = {}, x, n}, > Do[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] > > For example: > > In[25]:= > g[10^5,10^4]//Timing > > Out[25]= > {47.6935 Second,{{},{5,2,5}}} > > g[10^5,10^4,6]//Timing > > Out[2]= > {109.657 Second,{}} > > and so on. As you see not much progress in terms of results :-( > > Why is block better than Module? Well, suppose you set a to a very > large number. > > g[10^7, 100] // Timing > > This is taking very long but you might like to check the progress. > You can use the Kernel menu and form the Evaluation submenu select > Enter Subsession. Now you can check your progress: > > (Dialog Level 2) In[11]:= > n > > (Dialog Level 2) Out[11]= > 5 > > > (Dialog Level 2) In[12]:= > (y^n-y^2)/((y-1)*y) > > (Dialog Level 2) Out[12]= > 70643 > > Next you can choose Exit Subsession form the Evaluation menu and > continue the computation. Some time later you can again Enter > subsession: > > (Dialog Level 2) In[11]:= > ls > > (Dialog Level 2) Out[11]= > {{},{5,2,5}} > > (Dialog Level 2) In[12]:= > (y^n-y^2)/((y-1)*y) > > (Dialog Level 2) Out[12]= > 160434 > > This will give you a good idea of the progress your computation is > making and of the effect of changing different parameters. However, > I am now pretty pessimistic about finding solutions other than > {5,2,5}. > > Andrzej > > > > > > On 14 Oct 2005, at 05:49, Diana Mecum wrote: > > >> *This message was transferred with a trial version of CommuniGate >> (tm) Pro* >> Andrzej, >> >> Thanks so much for your recommendations. I will take and examine >> them over the weekend, and try to incorporate the ideas for all >> the equations I examine. >> >> Diana M. >> >> -----Original Message----- >> From: Andrzej Kozlowski <andrzej at yhc.att.ne.jp> To: mathgroup at smc.vnet.net >> Sent: Oct 13, 2005 4:17 AM >> To: Diana <diana53 at earthlink.net> >> Cc: mathgroup at smc.vnet.net >> Subject: [mg61289] Re: [mg61185] Solving Diophantine Equations >> >> Sorry, I was wrong last time. This new bound lower bound for x, >> namely y is actually worse than my earlier one, namely y^((n - 1)/ >> 2), except when n<=3. >> >> Let me quickly show how I got that the earlier bound. We look at the >> equation >> >> x^2+x == y^(n-1)+ y^(n-2)+... >> >> If x< y^((n-1)/2) then x^2 < y^(n-1) and x^2+x < y^(n-1)+ y^(n-1)/2 >> which is less then y^(n-1) + y^(n-2)+.... >> >> So actually the best bound I know at this moment is: >> >> y^((n-1)/2) <= x <= y^(n-2)+y^(n-3)+...+y >> >> Andrzej Kozlowski >> >> >> >> >> On 13 Oct 2005, at 19:59, Andrzej Kozlowski wrote: >> >> >> >> >>> Actually it is easy to find a better bound. >>> >>> Consider your equality: >>> >>> (x^3 - 1)/(x - 1)==(y^n - 1)/(y - 1) >>> >>> Assuming that n is a positive integer this can be written in the >>> form: >>> >>> x^2+x == y^(n-1)+ y^(n-2)+... >>> >>> Factorising both sides we get >>> >>> x*(x+1) == y* (y^(n-2)+y^(n-3)+...+1) >>> >>> This means however that we must have >>> >>> x>=y and x+1 <= y^(n-2)+y^(n-3)+...+ 1 >>> >>> because the other case x<y and x+1>y^(n-2)+y^(n-3)+...+ 1 is >>> obviously impossible. So we see that >>> >>> y<=x <= y^(n-2)+y^(n-3)+...+y >>> >>> >>> This is at least better than making searches over independent >>> ranges for x and y. >>> >>> >>> Andrzej Kozlowski >>> >>> >>> >>> On 13 Oct 2005, at 15:58, Andrzej Kozlowski wrote: >>> >>> >>> >>> >>> >>>> >>>> >>>> On 12 Oct 2005, at 14:42, Diana wrote: >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>>> Math group, >>>>> >>>>> I am trying to start doing numerical solving of Diophantine >>>>> Equations. I >>>>> want to do extensive calculations, but the kernel aborts for lack >>>>> of memory. >>>>> >>>>> For example, the following command aborts midstream: >>>>> >>>>> Table[If[(x^3-1)/(x-1)==(y^n-1)/(y-1) && x!=y, >>>>> {{x,y,n},}],{x,2,1000},{y,2,1000},{n,1,1001,2}] >>>>> >>>>> I have tried doing many smaller steps, but then I have a very >>>>> long file of >>>>> multiple commands. >>>>> >>>>> Would you make a suggestion as to how to process these solving >>>>> commands with >>>>> large values of the variables? >>>>> >>>>> Thanks, >>>>> >>>>> Diana >>>>> -- >>>>> ===================================================== >>>>> "God made the integers, all else is the work of man." >>>>> L. Kronecker, Jahresber. DMV 2, S. 19. >>>>> >>>>> >>>>> >>>>> >>>>> >>>>> >>>>> >>>>> >>>> >>>> >>>> I doubt this will be of much help, but there are some obvious >>>> inequalities that must hold between the possible values of x and >>>> y, which can reduce the number of possible cases that need to be >>>> looked at. For example, you must have >>>> >>>> x > y^((n - 1)/2) >>>> >>>> Since if this were not true the LHS of >>>> >>>> (x^3-1)/(x-1)==(y^n-1)/(y-1) >>>> >>>> would be too large. Similarly it is also obvious that, >>>> >>>> x < (n - 1)*(y^(n - 1)/2) >>>> >>>> >>>> These are very rough bounds and as I spent only about 1 minute >>>> looking for them you should be able to work out better ones. In >>>> this way you can at least reduce the number of x's that need to be >>>> looked at for a given y and n. Even so this looks like a pretty >>>> tough task to attempt on a present day computer. >>>> >>>> Andrzej Kozlowski >>>> >>>> >>>> >>>> >>>> Andrzej Kozlowski >>>> Tokyo, Japan >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>> >>> Andrzej Kozlowski >>> Tokyo, Japan >>> >>> >>> >>> >>> >>> >>> >> >> Andrzej Kozlowski >> Tokyo, Japan >> >> >> >> >> >> >> ===================================================== >> "God made the integers, all else is the work of man." >> L. Kronecker, Jahresber. DMV 2, S. 19. >> >> > > Andrzej Kozlowski > Tokyo, Japan > > > > Andrzej Kozlowski Tokyo, Japan