# Why does Solve lock up when trying to solve the quadratic equation with large integers?

Why does Solve lock up when trying to solve the equation

Solve[(x^2+y^2)+(x+y)==2^511 && x>0 && y>0,{x,y},Integers]


It works up 2^185, but at higher powers of 2, it seems to stop processing. The program says it's running, but there is no solution after running overnight. Running Mathematica 11.3 on Windows 32-bit OS.

• You can format inline code and code blocks by selecting the code and clicking the {} button above the edit window. The edit window help button ? is useful for learning how to format your questions and answers. You may also find this meta Q&A helpful – Michael E2 Mar 10 '19 at 18:27
• I quickly get solutions for 2^257 (V11.3.0, macos). – Michael E2 Mar 10 '19 at 18:29
• Sorry, there was a typo - it should be 2^511 – user63373 Mar 10 '19 at 19:21
• Probably it's combinatorial blowup. n = 185 gives 32 solutions but n = 257 already gives 1024. Might be more work and memory to store the symbolics than your CPU can handle. – b3m2a1 Mar 10 '19 at 19:38
• @b3m2a1 I think the reasons probably have to do with number theory. n = 323 produces 8192 solutions in 2.3s and n = 325 produces only 128 solutions in 500s. The memory growth is quite low. I think for n = 511, you just have to wait long enough, and I can't predict how long that is. – Michael E2 Mar 10 '19 at 19:57

Here's a guess: The Diophantine problem $$x^2+y^2+x+y=a$$ is equivalent, via $$u=2x+1,v=2y+1$$ to finding the odd solutions to $$u^2+v^2=2+4a \,.$$ Whether Solve makes this transformation or not, solving the Pythagorean equation can be done from the prime factorization of $$2+4a$$. How long Solve takes thus might depend on how long it takes to factor $$2+4a$$.

This is not hard to verify:

Block[{FactorInteger = (Print["FactorInteger"[##]]; Abort[]) &},
PrintTemporary@Dynamic@Clock@Infinity;
Print[2 + 4 2^325];
Solve[(x^2 + y^2) + (x + y) == 2^325 && x > 0 && y > 0, {x, y}, Integers] // AbsoluteTiming
]

  2734063405978764905465627783897026706691461788616515545532213258012441248999219\
90402939147127881730

FactorInteger[
2734063405978764905465627783897026706691461788616515545532213258012441248999219\
90402939147127881730]

\$Aborted


Well, it turns out it takes about 500 sec. to factor 2 + 4 * 2^325, which is about how long it takes the Solve above to run.

• Thank you very much. This seems to be exactly what is happening. Much appreciated. – user63373 Mar 10 '19 at 21:19
• @user63373 You're welcome. :) – Michael E2 Mar 10 '19 at 22:10