Re: Solving Diophantine Equations

*To*: mathgroup at smc.vnet.net*Subject*: [mg61262] Re: [mg61185] Solving Diophantine Equations*From*: Andrzej Kozlowski <andrzej at yhc.att.ne.jp>*Date*: Fri, 14 Oct 2005 05:53:55 -0400 (EDT)*References*: <121B726C-F342-49E8-AC5A-028B2431CE24@yhc.att.ne.jp> <D3177184-B465-40C1-B883-22709E67ECA1@yhc.att.ne.jp> <290D85F2-4960-43B5-804A-2EEF6D8E027D@yhc.att.ne.jp>*Reply-to*: Andrzej Kozlowski <andrzej at akikoz.net>*Sender*: owner-wri-mathgroup at wolfram.com

I got a bit interested in this so I tried a quick though not very elegant implementation making use of my boundaries for x in terms of y. g[b1_, b2_] := Module[{y = 2, ls = {}, x, n}, Do[While[(y^n - y^2)/((y - 1)*y) < b1, 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, 5, b2, 2}]; ls] This is now works quite fast but I am unable to find more than a single triple: In[5]:= g[b1_, b2_] := Module[{y = 2, ls = {}, x, n}, Do[While[(y^n - y^2)/((y - 1)*y) < b1, 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, 5, b2, 2}]; ls] g[10^4,10^4]//Timing {4.18727 Second,{{},{5,2,5}}} Andrzej On 13 Oct 2005, at 20:17, Andrzej Kozlowski wrote: > 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 > > > > > Andrzej Kozlowski Tokyo, Japan

**Follow-Ups**:**problem solving polynomial equations***From:*wtplasar@ehu.es