Re: Solving Diophantine Equations
- To: mathgroup at smc.vnet.net
- Subject: [mg61289] Re: [mg61185] Solving Diophantine Equations
- From: Andrzej Kozlowski <andrzej at yhc.att.ne.jp>
- Date: Fri, 14 Oct 2005 05:56:09 -0400 (EDT)
- References: <32592565.1129236555309.JavaMail.root@elwamui-darkeyed.atl.sa.earthlink.net> <9F2DCCEC-34BF-4F53-9475-F686A911F260@akikoz.net>
- Reply-to: Andrzej Kozlowski <andrzej at akikoz.net>
- Sender: owner-wri-mathgroup at wolfram.com
I only now noticed Mike's post and observed that he found a solution
I never managed to notice so far, namely {90, 2, 13}. So I checked my
program and sure enough it is wrong: y is incremented but never reset
to the original value. Here is the corret version:
g[a_, b_, c_:5] := Block[{y = 2, ls = {}, x, n},
Do[While[(y^n - y^2)/((y - 1)*y) < a,
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++]; y = 2;, {n, c, b, 2}]; ls]
Now it can find the two solutions very fast, e.g.
In[44]:=
g[10000,30]//Timing
Out[44]=
{2.64865 Second,{{{},{5,2,5}},{90,2,13}}}
but so far I have not found any more (however, I only just corrected
the error in the program).
Andrzej
On 14 Oct 2005, at 06:56, Andrzej Kozlowski wrote:
> One more thing. It might be better to change Module in my last code
> to Block. Here is a new version:
>
> g[a_, b_,c_:5] := Block[{y = 2, ls = {}, x, n},
> Do[While[(y^n - y^2)/((y - 1)*y) < a,
> 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, c, b, 2}]; ls]
>
> For example:
>
> In[25]:=
> g[10^5,10^4]//Timing
>
> Out[25]=
> {47.6935 Second,{{},{5,2,5}}}
>
> g[10^5,10^4,6]//Timing
>
> Out[2]=
> {109.657 Second,{}}
>
> and so on. As you see not much progress in terms of results :-(
>
> Why is block better than Module? Well, suppose you set a to a very
> large number.
>
> g[10^7, 100] // Timing
>
> This is taking very long but you might like to check the progress.
> You can use the Kernel menu and form the Evaluation submenu select
> Enter Subsession. Now you can check your progress:
>
> (Dialog Level 2) In[11]:=
> n
>
> (Dialog Level 2) Out[11]=
> 5
>
>
> (Dialog Level 2) In[12]:=
> (y^n-y^2)/((y-1)*y)
>
> (Dialog Level 2) Out[12]=
> 70643
>
> Next you can choose Exit Subsession form the Evaluation menu and
> continue the computation. Some time later you can again Enter
> subsession:
>
> (Dialog Level 2) In[11]:=
> ls
>
> (Dialog Level 2) Out[11]=
> {{},{5,2,5}}
>
> (Dialog Level 2) In[12]:=
> (y^n-y^2)/((y-1)*y)
>
> (Dialog Level 2) Out[12]=
> 160434
>
> This will give you a good idea of the progress your computation is
> making and of the effect of changing different parameters. However,
> I am now pretty pessimistic about finding solutions other than
> {5,2,5}.
>
> Andrzej
>
>
>
>
>
> On 14 Oct 2005, at 05:49, Diana Mecum wrote:
>
>
>> *This message was transferred with a trial version of CommuniGate
>> (tm) Pro*
>> 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
>> Sent: Oct 13, 2005 4:17 AM
>> To: Diana <diana53 at earthlink.net>
>> Cc: mathgroup at smc.vnet.net
>> Subject: [mg61289] 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.
>>
>>
>
> Andrzej Kozlowski
> Tokyo, Japan
>
>
>
>
Andrzej Kozlowski
Tokyo, Japan