There is an ordered set $M$ with $N$ numbers in it (and $M\_n$ is the $n$-th number in $M$). Let $L\_k$ be the sum of the first $k$ numbers in $M$.


Consider equation $\sum\_{k=0}^{N-1} 3^k 2^{-L\_{k+1}} \equiv 1 \bmod 3^N$


For example, if $N=1 \Rightarrow 3^0 2^{-L\_1} \equiv 1 \bmod 3^1$ or $2^{-L\_1}\equiv 1 \bmod 3$, which is only possible if $-L\_1\equiv 0 \bmod 2 \Rightarrow M\_1 \equiv 0 \bmod 2$ (which is to say, "if $M$ contains $1$ number and solves the equation above, the number that $M$ contains must be even")


Is there a general way we can use to find all "modular restrictions" for all numbers in $M$ for any given size ($N$) of $M$? It gets really hard brute forcing even for $N=4$.



Is there a general way to solve this modular equation?
There seems to be no simple formula for the solutions to the given congruence. Still, they can be computed iteratively as follows.


First, we notice that $2^m = (3-1)^m \equiv (-1)^m \sum\_{i=0}^{N-1} \binom{m}{i} (-3)^i \pmod{3^N}$. Then the left-hand side of the congruence in question can be rewritten as
$$\sum\_{k=0}^{N-1} 3^k (-1)^{L\_{k+1}} \sum\_{i=0}^{N-1} \binom{- L\_{k+1}}{i} (-3)^i \equiv \sum\_{m=0}^{N-1} 3^m \sum\_{k=0}^m (-1)^{L\_{k+1}+m-k} \binom{- L\_{k+1}}{m-k} \pmod{3^N}$$


Next, we fix the parities of $L\_1,\dots,L\_N$, where $L\_1\equiv 0\pmod{2}$ and the others can be arbitrary. Then, we compute iteratively $L\_2,\dots,L\_{N-1}$ in parametric form by considering the above congruence modulo $3^l$ for $l=2,\dots,N$, dividing it by $3^{l-1}$, and solving the resulting linear congruence with respect to $L\_{l-1}$.


Finally, we obtain $M\_k = L\_k - L\_{k-1}$.


Hence, this approach constructs a complete solution as the union of $2^{N-1}$ parametric ones.




---


**Example for $N=4$.** Let's fix the parities as $(L\_1,L\_2,L\_3,L\_4)\equiv (0,1,0,1)\pmod{2}$. Then for $l=2$, have a congruence:
$$3^0\cdot (-1)^{L\_1+0-0} \binom{-L\_1}{0-0} + 3^1\cdot \big( (-1)^{L\_1+1-0} \binom{-L\_1}{1-0} + (-1)^{L\_2+1-1} \binom{- L\_2}{1-1}\big)\equiv 1\pmod{3^2},$$
that is
$$L\_1 - 1\equiv 0\pmod{3},$$
and thus $L\_1 = 4+6t$, where $t$ is an integer parameter.


Using the above result, we can simplify the congruence for $l=3$ to
$$\frac{L\_1 - 1}3 + (-1)^{L\_1+2-0} \binom{-L\_1}{2-0} + (-1)^{L\_2+2-1} \binom{- L\_2}{2-1} + (-1)^{L\_3+2-2} \binom{- L\_3}{2-2} \equiv 0\pmod{3}$$
that is
$$2t - L\_2 \equiv 0\pmod{3},$$
implying $L\_2 = 3 + 2t + 6s$, where $s$ is an integer parameter.


Next the congruence for $l=4$ simplifies to
$$t^2 + t + s + 1 + L\_3 \equiv 0\pmod{3},$$
implying $L\_3 = 2(t^2 + t + s + 1) + 6z$, where $z$ is an integer parameter.


Therefore, for the chosen parities, the solutions are described parametrically by
$$\begin{cases}
L\_1 = 4+6t, \\
L\_2 = 3 + 2t + 6s,\\
L\_3 \equiv 2(t^2 + t + s + 1) + 6z,\\
L\_4 \equiv 1+2w,
\end{cases}$$
and correspondingly
$$\begin{cases}
M\_1 = 4+6t, \\
M\_2 = 6s - 4t - 1,\\
M\_3 \equiv 6z + 2t^2 - 4s - 1,\\
M\_4 \equiv 2w - 2t^2 - 2t - 2s - 6z - 1,
\end{cases}$$
where $t,s,z,w$ are arbitrary integers.


The other $2^3-1 = 7$ parametric solutions (for the other parity choices) are constructed similarly.


