Re: question on diophantine equations in Mathematica
- To: mathgroup at smc.vnet.net
- Subject: [mg115544] Re: question on diophantine equations in Mathematica
- From: Adam Strzebonski <adams at wolfram.com>
- Date: Fri, 14 Jan 2011 06:17:38 -0500 (EST)
For Diophantine equations Solve and Reduce use the same code, so there should be no speed difference. Best Regards, Adam Strzebonski Wolfram Research Ivan Smirnov wrote: > Am I right that with such constraints Reduce now is many faster than Solve? > > 2011/1/14 Adam Strzebonski <adams at wolfram.com <mailto:adams at wolfram.com>> > > Reduce does a case-by-case search here, but it chooses the variables > with smallest ranges of values for the search. > > In[1]:= form = x^10 + y^10 + z^10 == t^2 && x >= 0 && y >= 1 && > x <= y && y <= z && 1 <= t <= 250000; > > In[2]:= vars = {x, y, z, t}; > > In[3]:= {Ceiling[MinValue[#, form, vars]], > Floor[MaxValue[#, form, vars]]}&/@vars > > Out[3]= {{0, 10}, {1, 11}, {1, 12}, {2, 250000}} > > Reduce does case-by-case search for the first 3 variables, > so the problem reduces to solving > > In[4]:= 11 11 12 > Out[4]= 1452 > > univariate quadratic equations. The most time-consuming part > here is computing the MinValue/MaxValue (8 CAD problems with > 4 variables). > > This method will do exhaustive search on {x, y, z} as long as > the number of possible {x, y, z} values does not exceed 10000. > > If you want it to do larger searches you need to change > the second value of the system option > > In[5]:= "ExhaustiveSearchMaxPoints"/.("ReduceOptions"/.SystemOptions[]) > Out[5]= {1000, 10000} > > This increases the maximum number of search points to 10^6. > > In[6]:= SetSystemOptions["ReduceOptions"->{"ExhaustiveSearchMaxPoints"-> > {1000, 10^6}}]; > > This proves that the problem has no solutions with t <= 10^10 > (a search over 828630 cases). > > In[7]:= Reduce[x^10 + y^10 + z^10 == t^2 && 0 <= x && 0 < y && > x <= y && y <= z && 1 <= t <= 10^10, {x, y, z, t}, Integers] // Timing > > Out[7]= {269.967, False} > > > Best Regards, > > Adam Strzebonski > Wolfram Research > > > > Andrzej Kozlowski wrote: > > Actually Solve (and Reduce) are remarkably efficient at solving > this problem. It is better to reformulate it by requiring that > the two smallest values be larger than 0. This eliminates all > trivial solutions. Solve (and Reduce) then work remarkably fast > for very large numbers t, e.g. > > Solve[ > x^10 + y^10 + z^10 == t^2 && 0 <= x && 0 < y && x <= y && y <= > z && 1 <= t <= 250000, {x, y, z, t}, Integers] // Timing > > {1.80372,{}} > > Now look at this: > > > In[1]:= Solve[ > x^10 + y^10 + z^10 == t^2 && 0 <= x && 0 < y && x <= y && y <= > z && 1 <= t <= 350000, {x, y, z, t}, Integers] // Timing > > Out[1]= {1.90608,{}} > > This is so fast that it almost excludes the possibility of "case > by case" verification. Moreover, solving the problem for t= > 350,000 took only slightly longer than for t= 250,000. > If this is indeed a valid proof (and I think it is - Reduce > gives the same answer) then it looks like Solve is really using > some knowledge of Diophantine equations to solve this. It would > be really interesting to know what is going on. I almost > inclined to believe that Solve is able to prove that there are > no solutions for all t, but running it without a bound on t > produces a useless (in this context) "conditional" answer: > > Solve[x^10+y^10+z^10==t^2&&0<=x&&0<y&&x<=y&&y<=z,{x,y,z,t},Integers] > (Output deleted). > > I do hope we get some insight into what Solve is doing. It is > beginning to look fascinating, although I am probably missing > something simple... > > Andrzej Kozlowski > > On 12 Jan 2011, at 19:41, Andrzej Kozlowski wrote: > > Yes, but I think I unintentionally deceived you (and > myself). Mathematica caches its results and recall that I > tried solving this several times with different numbers > before I run Timing. mathematica obviously remembered all > the answers and when I tried measuring the time taken it was > amazingly fast. I should have found it suspicious but as I > was busy with other things I did not notice anything. > > Now that I tried again with a fresh kernel the results are > much less impressive: in fact much closer to yours. > But note that now it is clear that Solve is very much faster > than PowersRepresentatins (it looked the other way round > before). In fact Solve deals with this impressively fast: > > Timing[ > Select[Table[ > PowersRepresentations[t^2, 3, 10], {t, 1, 90000}], #1 != {} > & ]] > > {641.343049, {{{0, 0, 1}}, {{0, 0, 2}}, {{0, 0, 3}}, {{0, 0, > 4}}, {{0, 0, 5}}, {{0, 0, 6}}, {{0, 0, 7}}, {{0, 0, > 8}}, {{0, 0, 9}}}} > > > Timing[ > Solve[x^10 + y^10 + z^10 == t^2 && 0 <= x && x <= y && y <= > z && 1 <= t <= 90000, {x, y, z, t}, Integers]] > > {1.161798, {{x -> 0, y -> 0, z -> 1, t -> 1}, {x -> 0, y > -> 0, z -> 2, t -> 32}, {x -> 0, y -> 0, z -> 3, t -> > 243}, {x -> 0, y -> 0, z -> 4, t -> 1024}, {x -> 0, y -> > 0, z -> 5, t -> 3125}, {x -> 0, y -> 0, z -> 6, t -> > 7776}, {x -> 0, y -> 0, z -> 7, t -> 16807}, {x -> 0, y > -> 0, z -> 8, t -> 32768}, {x -> 0, y -> 0, z -> 9, t > -> 59049}}} > > This suggests strongly that you should in fact use Solve. > However, you should not try to test for too large a group of > solutions at a time. For example, you can get the next > 10,000 quickly: > > Timing[ > Solve[x^10 + y^10 + z^10 == t^2 && 0 <= x && x <= y && y <= > z && 90000 <= t <= 100000, {x, y, z, t}, Integers]] > > {1.48964,{{x->0,y->0,z->10,t->100000}}} > > But the time for this 10,000 is longer than for the previous > 90,000! > > With best regards > > Andrzej > > > > On 12 Jan 2011, at 16:03, Ivan Smirnov wrote: > > Oh, it's very cool computer. What model of CPU, Intel or > AMD? > I just thought that time was in seconds, but surprised > that it took so few time and asked. > I have only 1.6 Ghz Acer (Intel T5500) with 1 GB Ram, so > for 1..90000 it took 1034 seconds to compute... > > 2011/1/12 Andrzej Kozlowski <akoz at mimuw.edu.pl > <mailto:akoz at mimuw.edu.pl>> > I am using Mathematica 8 on 2.66 Ghz Mac Book Pro with 8 > gigabytes of Ram. The time is measured in seconds. With > Mathematica 8 you can also get the same answer with Solve: > > Timing[ > Solve[x^10 + y^10 + z^10 == t^2 && 0 <= x && x <= y && y > <= z && > 1 <= t <= 90000, {x, y, z, t}, Integers]] > > {1.01969,{{x->0,y->0,z->1,t->1},{x->0,y->0,z->2,t->32},{x->0,y->0,z->3,t->243},{x->0,y->0,z->4,t->1024},{x->0,y->0,z->5,t->3125},{x->0,y->0,z->6,t->7776},{x->0,y->0,z->7,t->16807},{x->0,y->0,z->8,t->32768},{x->0,y->0,z->9,t->59049}}} > > I think for very large numbers PowersRepresentations > will give you more satisfactory answers. For example, > compare the output > > Solve[x^10 + y^10 + z^10 == 10^20 && 0 <= x && x <= y && > y <= z, {x, > y, z, t}] > > with > > PowersRepresentations[10^21, 3, 10^20] > > {} > > Andrzej Kozlowski > > > > > On 12 Jan 2011, at 13:16, Ivan Smirnov wrote: > > Hello, Andrzej. > Many thanks for reply. > What PC do you use (OS, CPU & RAM) and how many > minutes did it take to compute, what is 0.872...? > What is the upper margin for t which can cause overflow? > Do you have any other ideas how to increase > performance for my task? > Will be very glad for help > > 2011/1/12 Andrzej Kozlowski <akoz at mimuw.edu.pl > <mailto:akoz at mimuw.edu.pl>> > This seems to show that there are only trivial > solutions for 1<=t<=90000 > > Timing[ > Select[Table[ > PowersRepresentations[t^2, 3, 10], {t, 1, 90000}], > #1 != {} & ]] > > {0.8722430000000259, {{{0, 0, 1}}, {{0, 0, 2}}, {{0, 0, > 3}}, {{0, 0, 4}}, {{0, 0, 5}}, {{0, 0, 6}}, {{0, 0, > 7}}, > {{0, 0, 8}}, {{0, 0, 9}}}} > > The algorithm basically uses "brute force" so you > will start getting overflows for very large t. > > Andrzej Kozlowski > > > > On 12 Jan 2011, at 01:25, Ivan Smirnov wrote: > > Hi all, > I've installed trial of Mathematica 8. > I would like to search for possible solutions of > diophantine equation > x^10+y^10+z^10=t^2. > How to do this efficiently? > FindInstance seems to be VERY slow! And indeed > it doesn't always find every > solution of diophantine equations. For example > I've tried it with > x^4+y^4+z^4=t^4 and it didn't find anything (but > there are solutions!). > And Solve command just don't want to search! > With some seconds it gives > During evaluation of In[1]:= Solve::svars: > Equations may not give solutions > for all "solve" variables. >> > I will be very glad if someone make INDEED FAST > algorithm for searching. > > Ivan > > > > > > > > >