MathGroup Archive 2005

[Date Index] [Thread Index] [Author Index]

Search the Archive

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.


  • Prev by Date: Re: Solving Diophantine Equations
  • Next by Date: Re: Solving Diophantine Equations
  • Previous by thread: Re: Solving Diophantine Equations
  • Next by thread: Re: Solving Diophantine Equations