Determine whether there exist a positive integer $n<10^9$, such that $n$ can be expressed as a sum of three squares of positive integers by more than $1000$ distinct ways?
Problem
Source:
Tags: combinatorics
22.06.2017 22:12
Answer: yes, there indeed does. Look at all numbers of the form $N=a^2+b^2+c^2$ where $1 \le \min(a,b,c) \le \max(a, b, c)<10^4\sqrt{3},$ then there are at most $9 \cdot 10^8$ such numbers. However, there are $3\sqrt{3} \cdot 10^{12}$ such triples $(a, b, c)$ so, by PHP, some number has at least $10^{3}$ triples assigned to it, as desired. EDIT: we can improve the estimate as suggested by @below. Indeed, there are $$10^{12}\left(\sqrt{\frac{10}{3}}\right)^3>6 \cdot 10^{12},$$triples (there's a nifty floor function part on LHS, but it doesn't change the estimate). With $10^9$ numbers, the PHP does work.
22.06.2017 23:14
@above I think, order $a,b,c$ is not important, so every triple is counted $6$ times. So we need to set borders more accurately. Let $m=[10^4 \sqrt{\frac{10}{3}}]$ and $a,b,c \leq m$ Then $a^2+b^2+c^2$ can take values not more as $10^9$ and there are $m^3$ such triples. $m^3>(10^4 \sqrt{\frac{10}{3}}-1)^3 > 10^{12} \sqrt{\frac{1000}{27}}- 10^9>10^{12} \sqrt{37}-10^9 >6*10^{12}$