Re: Solving Diophantine Equations

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

```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.
>
>
> (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

```

• Prev by Date: DSolve and matrix form of system of equations
• Next by Date: Re: Solving Diophantine Equations
• Previous by thread: Re: Solving Diophantine Equations
• Next by thread: Re: Solving Diophantine Equations