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 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 ?

Sequence A060968 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.

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

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

This suggests a sieving 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)$.