Let $f(n)$ be the number of points on the unit sphere $x^2 + y^2 + z^2 = 1\; (\mod n)$$x^2 + y^2 + z^2 = 1\; \pmod 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)$$x^2 + y^2 \equiv 1\; \pmod 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)$.
