2
$\begingroup$

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}]
$\endgroup$
0
3
$\begingroup$

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\}$.

$\endgroup$
2
  • $\begingroup$ Please provide a reference for the formula in the second paragraph. Thanks. $\endgroup$
    – bbgodfrey
    Jan 31 '20 at 4:16
  • $\begingroup$ 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. $\endgroup$ Jan 31 '20 at 23:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.