I wanted to prove that the equation below is right for all positive integers x, but it just seems I can't get a solid prove. I tried to do it by induction and started with the lowest possible value of x: $x=1$ , but I just can't go further with $x+1$.
Is there even any possibility to do so? Or am I completely on the wrong track? $$\left(\frac{x(x+1)}{2}-\sum_{i=1}^{\left\lfloor \log_3(x) \right\rfloor} {{\left\lfloor \frac{x}{3^i} \right\rfloor}\cdot{\left\lfloor \frac{x}{3^i}+1 \right\rfloor}}\right) \pmod 3 = \\ \left( \sum_{j=0}^{\left\lfloor \log_3(x) \right\rfloor} \left(\left( \left\lfloor \frac{x}{3^j} \right\rfloor \pmod 3 \right) \pmod 2\right) \right) \pmod 3$$
Edit: I simplified LHS now to: $$\left(-2\cdot\sum_{i=0}^{\left\lfloor \log_3(x) \right\rfloor}{\left\lfloor \frac{x}{3^i} \right\rfloor}+\left\lfloor\log_3(x)\right\rfloor \right)\pmod 3$$
I also wondered if I could use the fact that $\left( a1+a2+…+an\right)\pmod b=\left(a1 \pmod b+a2 \pmod b+…+an \pmod b\right)\pmod b$ to simplify the RHS. But it doesn't work yet because of the $\pmod 2$. What could I do?
Thank you in advance!
Best Answer
$$\left(\frac{x(x+1)}{2}-\sum_{j=1}^{\left\lfloor \log_3(x) \right\rfloor} {{\left\lfloor \frac{x}{3^j} \right\rfloor}\cdot{\left\lfloor \frac{x}{3^j}+1 \right\rfloor}}\right) \bmod 3 = \\ \left( \sum_{j=0}^{\left\lfloor \log_3(x) \right\rfloor} \left( \left\lfloor \frac{x}{3^j} \right\rfloor \bmod 3 \right) \bmod 2\right) \bmod 3$$
is equivalent to
$$\left(\frac{x(x+1)}{2}\right) \bmod 3 = \\ \left(\sum_{j=1}^{\left\lfloor \log_3(x) \right\rfloor} {{\left\lfloor \frac{x}{3^j} \right\rfloor}\cdot{\left\lfloor \frac{x}{3^j}+1 \right\rfloor}} + \sum_{j=0}^{\left\lfloor \log_3(x) \right\rfloor} \left( \left\lfloor \frac{x}{3^j} \right\rfloor \bmod 3 \right) \bmod 2\right) \bmod 3$$
Adding $x(x+1)$ corresponding to the term $j=0$ of the first sum and using that $\left(3 \frac{x(x+1)}{2}\right)\mod 3 = 0$, this is equivalent to
$$\left(\sum_{j=0}^{\left\lfloor \log_3(x) \right\rfloor} \left({{\left\lfloor \frac{x}{3^j} \right\rfloor}\cdot{\left\lfloor \frac{x}{3^j}+1 \right\rfloor}} + \left( \left\lfloor \frac{x}{3^j} \right\rfloor \bmod 3 \right) \bmod 2\right)\right) \bmod 3 = 0$$
We'll see that each term of this sum is $0$ modulo $3$.
More generally, for any integer $n$ we have $n(n+1) + (n \bmod 3)\bmod 2$ is multiple of $3$:
If
$n=3k$ then \begin{align} n(n+1) + (n \bmod 3)\bmod 2 & = 3k(3k+1) + 0 \bmod 2\\ & = 3k(3k+1) + 0\\ & = 3k(3k+1) \end{align}
$n=3k+1$ then \begin{align} n(n+1) + (n \bmod 3)\bmod 2 & = (3k+1)(3k+2) + 1 \bmod 2\\ & = (3k+1)(3k+2) + 1\\ & = 3(3k^2+3k+1) \end{align}
$n=3k+2$ then \begin{align} n(n+1) + (n \bmod 3)\bmod 2 & = (3k+2)(3k+3) + 2 \bmod 2\\ & = (3k+2)(3k+3) + 0\\ & = 3(3k+2)(k+1) \end{align}
Now just take $n = \left\lfloor \dfrac{x}{3^j} \right\rfloor$.