Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2005
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2005

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

Search the Archive

Re: Solving Diophantine Equations

  • To: mathgroup at smc.vnet.net
  • Subject: [mg61281] Re: [mg61185] Solving Diophantine Equations
  • From: Andrzej Kozlowski <andrzej at akikoz.net>
  • Date: Fri, 14 Oct 2005 05:54:55 -0400 (EDT)
  • References: <32592565.1129236555309.JavaMail.root@elwamui-darkeyed.atl.sa.earthlink.net>
  • Reply-to: Andrzej Kozlowski <andrzej at akikoz.net>
  • Sender: owner-wri-mathgroup at wolfram.com

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 bettere 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: [mg61281] 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




  • Prev by Date: Re: Solving Diophantine Equations
  • Next by Date: Re: Solving Diophantine Equations
  • Previous by thread: Re: Solving Diophantine Equations
  • Next by thread: Re: Solving Diophantine Equations