Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
@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
1  
For those interested in the source for this problem, it is Euler Project Problem 233. –  user26300 Mar 5 '12 at 9:22
1  
If, as @user26300 indicated, this question came from Project Euler, this meta discussion would be relevant. –  Willie Wong Mar 5 '12 at 9:54
show 4 more comments

1 Answer

Hint: use the following well-known formula

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

share|improve this answer
    
Sorry, but I already am using that formula. I just wanted to know how I could narrow it down to where my answers would be 420. –  Awk34 Feb 12 '12 at 0:17
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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