MathGroup Archive 2005

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

Search the Archive

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




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