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