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
- Follow-Ups:
- problem solving polynomial equations
- From: wtplasar@ehu.es
- problem solving polynomial equations