Re: Solving Diophantine Equations
- To: mathgroup at smc.vnet.net
- Subject: [mg61279] Re: [mg61185] Solving Diophantine Equations
- From: Diana Mecum <diana53 at earthlink.net>
- Date: Fri, 14 Oct 2005 05:54:42 -0400 (EDT)
- Reply-to: Diana Mecum <diana53 at earthlink.net>
- Sender: owner-wri-mathgroup at wolfram.com
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
Subject: [mg61279] 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.