Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2011

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

Search the Archive

Re: question on diophantine equations in Mathematica

  • To: mathgroup at smc.vnet.net
  • Subject: [mg115546] Re: question on diophantine equations in Mathematica
  • From: Adam Strzebonski <adams at wolfram.com>
  • Date: Fri, 14 Jan 2011 06:18:00 -0500 (EST)

I am using a 3 GHz Intel Core i7 CPU with 6 GB of RAM available
for the virtual machine. MaxMemoryUsed[] gives 828 MB, so if your
computer has only 1 GB of RAM it might be swapping memory.

Adam

Ivan Smirnov wrote:
> If so, why then your PC computed it from 1 to 10^10 (in such big 
> interval) with only 269.967 and my is still computing yet, more than 20 
> minutes?
> I asked it only from this point. It can be only from hardware 
> difference. What is your CPU&RAM&bitness, Adam?
> 
> 2011/1/14 Adam Strzebonski <adams at wolfram.com <mailto:adams at wolfram.com>>
> 
>     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> <mailto: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>
>                        <mailto: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>
>                            <mailto: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
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 



  • Prev by Date: Re: question on diophantine equations in Mathematica
  • Next by Date: Re: Interpolation of a tabulated function
  • Previous by thread: Re: question on diophantine equations in Mathematica
  • Next by thread: FindInstance for sum of primes