The function $y = {x^2 + x \over 2} \mod 2^n$ is defined for integers in $[0, 2^n)$. This function is a permutation of the set $[0, 2^n)$. Given y, is there a better way to find x than brute-forcing every possible x value?
I tried something on Desmos but didn't get anywhere. The inverse function only works for very few (x, y) values.
Given $y$, one can find the value of $x$ as follows: define a sequence $(z_k)_k$ by $z_0=0$ and $$z_k = (z_{k-1}+1)^2-1-2y \pmod{2^{k+1}},$$ with $z_k$ chosen in $[0, 2^{k+1})$. Then $x = \min(z_n, 2^{n+1}-z_n-1)$.
[The construction is motivated by Hensel's Lemma https://en.wikipedia.org/wiki/Hensel%27s_lemma]