Let $f(n)$ be the number of points on the unit sphere $x^2 + y^2 + z^2 = 1\; (\mod n)$ with $x,y,z \in \mathbb{Z}/n\mathbb{Z}$  

This is sequence [A087784][1] in the Online Encyclopedia of Integer sequences:

> 1, 4, 6, 24, 30, 24, 42, 96, 54, 120...

There is a (due to Bjorn Poonen) indicating some regularity to the solutions to this congurence

 $$f(n) = n^2* \left\{\begin{array}{cl}3/2&\text{if}\quad\quad 4|n \\
1 &\text{otherwise}
\end{array}\right\}*\prod_{\substack{p|n \\ 1 \mod 4}} \left( 1 + \frac{1}{p}\right)* \prod_{\substack{p|n \\ 3 \mod 4}} \left( 1 - \frac{1}{p}\right)$$

What are some proofs to this identity ?  

<hr>

Sequence [A060968][2] is the number of points on the unit circle $x^2 + y^2  \equiv 1\; (\mod n)$ 

> 1, 2, 4, 8, 4, 8, 8, 16, 12, 8, 12,...

with a similar multiplicative formula:
 $$g(n) = n* \left\{\begin{array}{cl}2&\text{if}\quad\quad 4|n \\
1 &\text{otherwise}
\end{array}\right\}*\prod_{\substack{p|n \\ 1 \mod 4}} \left( 1 + \frac{1}{p}\right)* \prod_{\substack{p|n \\ 3 \mod 4}} \left( 1 - \frac{1}{p}\right)$$


Perhaps there is a tower of such identities.



<hr>

The multiplicative structure of these formulas could have an algorithmic interpretation.  The formula for the [Euler phi function][3]

\\[ \phi(n) =  n \prod_{p|n} \left( 1 - \frac{1}{p} \right) \\]

This suggests a [sieving][4] algorithm to generate the list of numbers relatively prime to n

 - write down the numbers $\{ 1, 2, \dots, n \}$
 - for reach prime $p|n$ cross out multiples

I'd be especially interested if this type of algorithm existed for $f(n), g(n)$.


  [1]: http://oeis.org/A087784
  [2]: http://oeis.org/A060968
  [3]: http://en.wikipedia.org/wiki/Euler%27s_totient_function
  [4]: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes