# Finding a program that can find integer solutions for large values of a variable

I've the following code:

Table[b = (-12 +Sqrt[3] Sqrt[3 (-4 + r)^2 + 12 a^2 (-2 + r) - 4 a (-5 + r) (-2+ r) +4 a^3 (-2 + r)^2] + 3 r)/(6 (-2 + r)) /. r -> 5;
If[IntegerQ[b], {b, a}, Nothing], {a, 1+10^(11), 10^(12)}]


But it gives me the following warning: 'SystemException["MemoryAllocationFailure"]'.

Is there a way to avoid this warning? Maybe I've to edit my code?

• Well, as it is right now, a iterates through $10^{12} - (1 + 10^{11}) = 9 \times 10^{11}$ elements. Do you want to increment a by 1 each time? – That Gravity Guy Nov 16 '19 at 22:04
• I think your table is too large, it takes 7200000000000 bytes of memory assuming 8 bytes per entry., or 7,200 GB RAM if my calculation is right. – Nasser Nov 16 '19 at 22:04
• @ThatGravityGuy Yes I would like to do that – Jan Nov 16 '19 at 22:08
• @Nasser Is there a way to work around the big table? – Jan Nov 16 '19 at 22:08
• Re memory, could use Sow and Reap in a loop instead of Table. – Daniel Lichtblau Nov 17 '19 at 15:57

The approach suggested by yarchik can be accelerated by two orders of magnitude by performing the computations with machine precision numbers instead of exact numbers and then rounding, and by using ParallelDo:

SetSharedVariable[s]
s = {};
ParallelDo[If[IntegerQ[(1 + a*Round[Sqrt[1./(a*a) + 12. (a + 1)], 10^-10])/6],
AppendTo[s, a]], {a, 1, 10^9}] // AbsoluteTiming
s
(* {1795.35, Null} *)
(* 1 *)


The computation for a as large as 10^9 yields the single answer a -> 1 in about 30 minutes. Consequently, the computation for a as large as 10^12 should take about 21 days, a long but not impossibly long time. It seems likely that there are no additional solutions.

Note that there is a tradeoff between increasing the second argument of Round, which reduces runtime but also may yield some false positives. Eliminating the false positives is, of course, straightforward and fast, provided there are not too many.

The corresponding Diophantine equation is a^2 + a^3 + b - 3 b^2 == 0, as can be seen from Simplify[-(6 b - 1)^2 + 1 + 12 a^2 + 12 a^3]. It can be solved by means of Reduce for modest maximum values, amx, of a by

amx = 10^6;
SetSystemOptions["ReduceOptions" -> {"ExhaustiveSearchMaxPoints" -> {100, amx}}];
Reduce[{a^2 + a^3 + b - 3 b^2 == 0, amx > a > 0, b > 0}, {a, b}, Integers]
// AbsoluteTiming
(* {230.319, a == 1 && b == 1} *)


The corresponding run time for the solution by yarchik is 143.7 seconds. For the code given earlier in this answer (but with ParallelDo replaced by Do for consistency) the run time is 4.00122 seconds. Of course, the solution using Reduce and that by yarchik both can be parallelized, reducing run times proportionately.

• Very nice, but can you please show the solution of the Diophantine equation as it would eliminate the need for numerical search. – yarchik Nov 17 '19 at 17:13
• @yarchik Do you mean solving the Diophantine equation by means of Reduce? – bbgodfrey Nov 17 '19 at 17:19
• Yes, I would be very much surprised if Reduce or any other command can provide a solution because it is not a linear nor quadratic equation. I cannot find the equation in this table sites.google.com/site/tpiezas/009 – yarchik Nov 17 '19 at 18:02
• @yarchik Done. The Reduce computation is quite slow, however. – bbgodfrey Nov 17 '19 at 19:01

You can replace Table with Do

Do[If[IntegerQ[1/6 (1 + Sqrt[1 + 12 a^2 + 12 a^3])], Print[a]], {a, 1 + 10^(11), 10^4 + 10^(11)}]


but it is still slow. Try to bring your diophantine equation to some known type.