$f(n)=n$ if $\exists x$ s.t. $x^2-n\mid 4096,$ or $0$ otherwise. Find $\sum_{i=1}^{4095} f(i) \mod 4096$.
So this problem is from chmmc and the given answer is 1536. I tried to rewrite $f(n) =n$ if $\exists a$ s.t. $\sqrt{n+4096a} \in \Bbb{Z}$ but could not proceed from there. Any help is appreciated.
I was also wondering if this can be generalized to $f(n)=n$ if $\exists x$ s.t. $x^2-n\mid 2^k, 0$ otherwise. Find $\sum_{i=1}^{2^k-1} f(i) \mod 2^k$.
We have $$\sum_{i=1}^{2^k-1} f(n)=\sum_{n\in 1,2,\cdots , 2^k-1, n=x^2} n\equiv \sum_{n\in 1,2,\cdots , 2^k-1, n=x^2} x^2$$ But $i^2\equiv j^2\Leftrightarrow i=j$ or $i+j=2^k$ or $i=\ell \cdot 2^{k-2}+1, j=\ell \cdot 2^{k-2}-1, \ell=1,3$, so in above expression $x^2$ and $(2^k-x)^2$ only count once, while $(\ell \cdot 2^{k-2}+1)^2$ and $\ell \cdot 2^{k-2}-1$ counts only once too.
So $\sum_{n\in 1,2,\cdots , 2^k-1, n=x^2} x^2\equiv \sum_{x=1}^{2^{k-1}-1}x^2-(2^{k-2}-1)^2\equiv \frac{1}{6}(2^{k-1}-1)2^{k-1}(2^k-1)+2^{k-1}-1 (\mod 2^k)$
And the rest is easy.