Re: question on diophantine equations in Mathematica

*To*: mathgroup at smc.vnet.net*Subject*: [mg115543] Re: question on diophantine equations in Mathematica*From*: Ivan Smirnov <ivan.e.smirnov at gmail.com>*Date*: Fri, 14 Jan 2011 06:17:27 -0500 (EST)

Am I right that with such constraints Reduce now is many faster than Solve? 2011/1/14 Adam Strzebonski <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> >>>> 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> >>>>> 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 >>>>>> >>>>> >>>>> >>>> >>> >>> >> >> >