Re: Solving Diophantine Equations
- To: mathgroup at smc.vnet.net
- Subject: [mg61345] Re: [mg61185] Solving Diophantine Equations
- From: "Diana Mecum" <diana53 at earthlink.net>
- Date: Sun, 16 Oct 2005 00:18:00 -0400 (EDT)
- Reply-to: <diana53 at earthlink.net>
- Sender: owner-wri-mathgroup at wolfram.com
Andrzej, Once again, thanks so much. I will look into your work tomorrow, and may e-mail you with questions. Diana M. -----Original Message----- From: Andrzej Kozlowski [mailto:andrzej at yhc.att.ne.jp] To: mathgroup at smc.vnet.net Subject: [mg61345] Re: [mg61185] Solving Diophantine Equations 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> >>> Subject: [mg61345] 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