Re: Solving Diophantine Equations
- To: mathgroup at smc.vnet.net
- Subject: [mg61293] Re: [mg61185] Solving Diophantine Equations
- From: Andrzej Kozlowski <andrzej at yhc.att.ne.jp>
- Date: Fri, 14 Oct 2005 05:56:14 -0400 (EDT)
- References: <32592565.1129236555309.JavaMail.root@elwamui-darkeyed.atl.sa.earthlink.net> <9F2DCCEC-34BF-4F53-9475-F686A911F260@akikoz.net> <E39C9EDB-A88A-42F3-9AD9-7DA09C7D790A@yhc.att.ne.jp>
- Reply-to: Andrzej Kozlowski <andrzej at akikoz.net>
- Sender: owner-wri-mathgroup at wolfram.com
That was wrong again! Trying to write these loops is so frustrating,
perhaps I should go back to functional programming... Anyway, I think
and hope this is now right at last:
g[a_, b_, c_:5] := Block[{y, ls = {}, x, n},
Do[ y = 2; 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]
It is certainly not easy to find solutions, though, pretty big
searches so far have yielded just two, e.g.
In[69]:=
g[100000,30]//Timing
Out[69]=
{58.0157 Second,{{{},{5,2,5}},{90,2,13}}}
Andrzej
On 14 Oct 2005, at 10:59, Andrzej Kozlowski wrote:
> 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: [mg61293] 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
>
>
>
>
Andrzej Kozlowski
Tokyo, Japan