# For what kind of numbers would $r_2(n^2) = 420$?

I am trying to find all of the answers to $r_2(n^2) = 420$, where $N < 10^{11}$. It is for finding lattice points on a circle with points $(0,0), (N,0), (0,N)$, and $(N,N)$. I am (pretty) sure that all of the following answers work:

359125, 469625, 612625, 718250, 781625, 866125, 933725, 939250, 1047625, 1119625, 1225250, 1288625, 1336625, 1366625

where $r_k(n)$ is the number of different squares $k$ (in this case, the sum of 2 different squares) that add up to $n$. (Source)

I have noticed that all of these are divisible by $5^2$, but I know that the answer to this problem ends in 309.

What kinds of numbers would get me 420 for this?

-
Why do you know the last digits of the answer, where is the problem from? –  Listing Feb 11 '12 at 21:28
This is for a math/programming problem that was given to me. I was given the answer and asked to make a program that gives me that answer for the question. –  Awk34 Feb 11 '12 at 21:30
@Awk: I checked a few, they were OK. The smallest not divisible by $25$ will be $(5)(13^3)(17^2)$. You will have to make sure not to forget, for example, $(5^7)(13^3)$. –  André Nicolas Feb 12 '12 at 18:59
For those interested in the source for this problem, it is Euler Project Problem 233. –  user26300 Mar 5 '12 at 9:22
If, as @user26300 indicated, this question came from Project Euler, this meta discussion would be relevant. –  Willie Wong Mar 5 '12 at 9:54
$\qquad\quad n = 2^{c} p_1^{a_1}\:\cdots\:p_r^{a_r} q_1^{b_1}\:\cdots\:q_s^{b_s}\quad$ where primes $\ p_i \equiv 3,\ q_i \equiv 1\pmod{4}$
$\quad\ \Rightarrow\ {\rm SquaresR}[2,n] = 4\:(b_1+1)\:\cdots\:(b_s+1)\:$ if $a_i$ are all even, else $0$
This was in reply to the first version of your question, which did not have the link. Apply the formula and solve for the $b_i$. –  Math Gems Feb 12 '12 at 0:23