Re: question on diophantine equations in Mathematica
- To: mathgroup at smc.vnet.net
- Subject: [mg115502] Re: question on diophantine equations in Mathematica
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Thu, 13 Jan 2011 03:24:39 -0500 (EST)
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
>
>