# how to find smallest number satisfies having given number of solutions

I want to find the smallest number $$t$$ which satisfies $$t=a^2+b^2$$ ,where there are 12 pairs of $$a$$ and $$b$$ solution.

my first code is very slow

Cases[Table[{t,
Solve[{t == a^2 + b^2, a >= b > 0}, {a, b}, Integers] //
Length}, {t, 100000, 200000}], {_, 12}]


after some search, I find this

NestWhile[# + 1 &, 100000, Length[PowersRepresentations[#, 2, 2]] <= 11 &]


and this

NestWhile[# + 1 &, 100000,  Length[IntegerPartitions[#, {2}, Range[1000]^2]]
<= 11 &]


Someone tell me another way,get this

Cases[Tally@Flatten@Table[i^2 + j^2, {i, 1, 500}, {j, i, 500}], {_, 12}]


after using Outer ,get faster solution.

Cases[Tally[Flatten[Outer[Plus, #, #] &@(Range[500]^2)]], {_, 24}]


Your searches are fast, but you may never know if they are complete. Here is a solution based on Reduce which guarantees you have found all cases.

The number of representations of $$t=a^2+b^2$$ with $$a\ge b>0$$ is $$c=\frac{1}{2}(1+e_1)(1+e_2)...$$, where the $$e_i$$ are exponents of primes $$p\equiv1$$, mod 4, in the prime factorisation of $$n$$. This expression requires even $$c$$, and for your question $$c=12$$.

Use Reduce to find up to 4 exponents $$e_i$$, exponentiate the smallest primes $$p$$ to find candidate $$n$$, and finally choose the smallest $$n$$ of the groups. Testing integers with 5 primes is not required because $$2^5$$ exceeds the required 24.

Block[{s1, s2, s3, s4, e1, e2, e3, e4, p, n1, n2, n3, n4},
s1 = {e1} /. {ToRules[Reduce[{(1 + e1) == 24, e1 > 0}, {e1}, Integers]]};
s2 = {e1,e2} /. {ToRules[
Reduce[{(1 + e1) (1 + e2) == 24, e1 > 0, e2 > 0}, {e1, e2}, Integers]]};
s3 = {e1, e2, e3} /. {ToRules[
Reduce[{(1 + e1) (1 + e2) (1 + e3) == 24, e1 > 0, e2 > 0, e3 > 0},
{e1, e2, e3}, Integers]]};
s4 = {e1, e2, e3, e4} /. {ToRules[
Reduce[{(1 + e1)(1 + e2)(1 + e3)(1 + e4) == 24, e1>0, e2>0, e3>0, e4>0},
{e1, e2, e3, e4}, Integers]]};

p = Pick[#, Mod[#, 4], 1] &[Prime[Range[20]]];

n1 = Times @@@ Map[Take[p, 1]^# &, s1];
n2 = Times @@@ Map[Take[p, 2]^# &, s2];
n3 = Times @@@ Map[Take[p, 3]^# &, s3];
n4 = Times @@@ Map[Take[p, 4]^# &, s4];
Map[Min, {n1, n2, n3, n4}]
]


{11920928955078125, 6865625, 359125, 160225}

The smallest number $$t=a^2+b^2$$ having 12 pairs of solutions is 160225, corresponding to exponents $$\{2,1,1,1\}$$ of primes $$\{5,13,17,29\}$$.

• Please provide a reference for the formula in the second paragraph. Thanks. Jan 31 '20 at 4:16
• I do not have a web or book reference. Only a comment by user MuthuVeerappanR on a Project Euler Forum page. This page is inaccessible unless you have solved the problem. Jan 31 '20 at 23:01