# FindInstance with a Diophantine equation seems to go on forever

I tried to find a non-trivial integer solution to the equation
$$2012^2=a^2+b^2+c^2+d^2+e^2$$ with Mathematica but the computation takes minutes; I might be doing something wrong.

FindInstance[2012^2 == a^2 + b^2 + c^2 + d^2 + e^2
&& a > 0 && b > 0 && c > 0 && d > 0 && e > 0, {a, b, c, d, e}, Integers]


But when I try

FindInstance[2012^1 == a^2 + b^2 + c^2 + d^2 + e^2
&& a > 0 && b > 0 && c > 0 && d > 0 && e > 0, {a, b, c, d, e}, Integers]


I get an immediate result.

-
@kguler the change was from 2012^2 to 2012^1, I think they are both meant to be from the Integers. –  JxB Mar 27 '12 at 4:38
Thank you @JxB. –  kguler Mar 27 '12 at 4:43

It does not seem surprising that a search space 2000 times larger results in a substantially longer computation time.

Here is a much more direct way to find a solution:

Sqrt @ IntegerPartitions[2012^2, {5}, Range[2012]^2, 1]

{{2011, 63, 7, 2, 1}}

-
+1 for the clean approach. Though all odd (small enough) powers of 2012 work fast. Try this FindInstance[2012^13 == a^2 + b^2 + c^2 + d^2 + e^2, {a, b, c, d, e}, Integers] On the other hand even powers work slow. I am not sure if it is exactly larger computational space issue. –  Vitaliy Kaurov Mar 27 '12 at 6:01
@Vitaliy that's an interesting observation. I don't feel qualified to analyze the reason. –  Mr.Wizard Mar 27 '12 at 6:06
Mathematica seems to pick the wrong approach, i tried replacing 2012^n with other values and in most of them i ran out of memory, even if the number is very small like 864 –  Zero Mar 27 '12 at 18:29

Here is a way to make FindInstance work and give you a a few random solutions quickly:

Flatten /@ ({a -> #, FindInstance[2012^2 == #^2 + b^2 + c^2 + d^2 + e^2,
{b, c, d, e}, Integers]} & /@ RandomInteger[2011, 10]) // Column


Your equation can be solved for any Abs[a] <= 2012. Here is an app that let's you browse random solutions for any such fixed a

Manipulate[FindInstance[2012^2 == a^2 + b^2 + c^2 + d^2 + e^2,
{b, c, d, e}, Integers, RandomSeed -> s], {{s, 300, "sample"}, 1,
1000, 1}, {{a, 345}, 1, 2012, 1, Appearance -> "Labeled"}]


-
@Mr.Wizard Do you mean higher even powers by "more general"? If yes, the above approach works with any even power. –  Vitaliy Kaurov Mar 27 '12 at 6:24

As it happens, I wrote code for this sort of thing a couple of months ago. Am hoping to put it into Wolfram|Alpha some day.

sumOfPowers[n_, pow_, use_, exactly_: False] :=
sumOfPowers[n, pow, use, n + 1, exactly]
sumOfPowers[n_, pow_, use_, min_, exactly_: False] := Catch[Module[
{n1 = min, nminus, res},
If[use == 1 && ! IntegerQ[n^(1/pow)], Throw[$Failed]]; If[n <= min && IntegerQ[n^(1/pow)] && (use == 1 || ! exactly), Throw[{n}]]; While[(n1 = Floor[n1^(1/pow)]^pow) > 0, nminus = n - n1; res = sumOfPowers[nminus, pow, use - 1, Min[nminus, n1] + 1, exactly]; If[res =!=$Failed, Throw[Prepend[res, n1]]];
n1--;
];
\$Failed
]]


In[6]:= sumOfPowers[2012^2, 2, 4, True] // Timing

Out[6]= {0.11, {4040100, 7396, 324, 324}}


To find all such sums, perhaps best would be to use

PowersRepresentations[2012^2, 4, 2]


This might be no faster than what you did, though.

-