Re: Solving Diophantine Equations
- To: mathgroup at smc.vnet.net
- Subject: [mg61251] Re: [mg61185] Solving Diophantine Equations
- From: Andrzej Kozlowski <andrzej at yhc.att.ne.jp>
- Date: Fri, 14 Oct 2005 05:53:37 -0400 (EDT)
- References: <121B726C-F342-49E8-AC5A-028B2431CE24@yhc.att.ne.jp>
- Reply-to: Andrzej Kozlowski <andrzej at akikoz.net>
- Sender: owner-wri-mathgroup at wolfram.com
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