<s>[INST] Remainder of a summation divided by $2^{12}$ For a positive integer $n$, let $f(n)$ be equal to $n$ if there is an integer $x$ such that $x^2-n$ is divisible by $2^{12}$, and let $f(n)$ be $0$ otherwise. Determine the remainder when $$\sum_{n=0}^{2^{12}-1} f(n)$$ is divided by $2^{12}$. 
Source: Caltech Harvey Mudd Tournament
 [/INST] Basically, all we need is the fact that the squares in $(\mathbb{Z}/2^k\mathbb{Z})^\times$, for $k\geq 3$, are exactly those that are $1 \pmod{8}$.  This follows from the standard fact that $(\mathbb{Z}/2^k\mathbb{Z})^\times \cong Z_2\times Z_{2^{k-2}}$, that all squares are $1 \pmod{8}$, and that there are exactly $2^{k-3}$ elements in the latter, and the same number of squares in the former.
The remaining squares in $\mathbb{Z}/2^n\mathbb{Z}$ are all divisible by $4$, so we can work inductively.  If $F(k) = \sum_{n=0}^{2^k-1} f(n)$ ($k\geq 3$), then: $$F(k) - 4F(k-2) = \sum_{n\equiv 1\pmod{8}} n = \sum_{j=0}^{2^{k-3}-1} (8j+1) = 4\cdot 2^{k-3}(2^{k-3}-1) + 2^{k-3}$$ $$=2^{2k-4} - 2^{k-1} + 2^{k-3}$$
Since $F(2) = 1$, we have $F(12) = 4^5 + \sum_{j=2}^6 4^{6-j}(2^{4j-4} - 2^{2j-1} + 2^{2j-3}) = 1390080$.
Taken modulo $2^{12}$, this gives us $1536$.
</s>