MathGroup Archive 2005

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

Search the Archive

Re: Solving Diophantine Equations

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

I got a bit interested in this so I tried a quick though not very  
elegant implementation making use of my boundaries for x in terms of y.


g[b1_, b2_] := Module[{y = 2, ls = {}, x, n},
    Do[While[(y^n - y^2)/((y - 1)*y) < b1,
       Do[If[(x^3 - 1)/(x - 1) == (y^n - 1)/(y - 1) &&
           x != y, ls = {ls, {x, y, n}}],
         {x, y^((n - 1)/2), (y^n - y^2)/((y - 1)*y)}];
        y++], {n, 5, b2, 2}]; ls]


This is now works quite fast but I am unable to find more than a  
single triple:

In[5]:=
g[b1_, b2_] := Module[{y = 2, ls = {}, x, n},
    Do[While[(y^n - y^2)/((y - 1)*y) < b1,
       Do[If[(x^3 - 1)/(x - 1) == (y^n - 1)/(y - 1) &&
           x != y, ls = {ls, {x, y, n}}],
         {x, y^((n - 1)/2), (y^n - y^2)/((y - 1)*y)}];
        y++], {n, 5, b2, 2}]; ls]


g[10^4,10^4]//Timing


{4.18727 Second,{{},{5,2,5}}}


Andrzej



On 13 Oct 2005, at 20:17, Andrzej Kozlowski wrote:

> 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
>
>
>
>
>

Andrzej Kozlowski
Tokyo, Japan




  • Prev by Date: Re: Solving Diophantine Equations
  • Next by Date: Re: Solving Diophantine Equations
  • Previous by thread: Re: Solving Diophantine Equations
  • Next by thread: problem solving polynomial equations