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
>>>>>>
>>>>>
>>>>>
>>>>
>>>
>>>
>>
>>
>