Can the robot reach the target? A robot is located on an infinite plane. At the beginning, the robot starts at the coordinates $(0, 0)$. The robot can then make several steps. The steps are numbered starting from $0$. 
In each step, robot must choose one of two directions : right ($x$ coordinate increases) or up ($y$ coordinate increases). In step $k$, the robot will move $3^k$ units in the chosen direction. It is not allowed to skip a step.  You are given integers $x$ and $y$. I want to know if it is possible to go to that location or not by returning $1$ for yes and $0$ for no.
 A: First check: $x+y$ should be a $\sum_{i=0}^k 3^i=\frac{3^{k+1}-1}{2}$ for some $k$. Deeper check: the powers should be distributed nicely between $x$ and $y$. Fortunately, $3^k>\sum_{i=0}^{k-1}3^i$, so that the following algorithm works:


*

*Let $s\leftarrow 2(x+y)+1$. 

*If $x<y$ swap $x\leftrightarrow y$. [Swapping does not affect solvability, but simplifies treatment]

*If $y<0$ terminate with "no". [Points with negative coordinates cannot be reached]

*If $s=1$, terminate with "yes". [Implies $x=y=0$ and that point can be reeached with no step at all]

*If $s$ is not divisible by $3$, terminate with "no". [Because all powers of $3$ except $3^0$ are multiples of $3$]

*Let $s\leftarrow \frac s3$. [That is, the previous power of $3$, also the top summand in $\sum 3^i$]

*Let $x\leftarrow x-s$ and go to step 2. [By the observation above, the top summand must have been the last step for the bigger coordinate; steps 6 and 7 effectively undo the last step]
A: Let $R$ the the set of pairs $(x,y)$ that can be reached.
Write $x,y$ as  $x=\sum_{k=0}^n x_k 3^k$, $y=\sum_{k=0}^n y_k 3^k$, with $n = \lfloor \log_3 \max(x,y)\rfloor+1$.
(This is just the base 3 expansion of the integers $x,y$.)
Then $(x,y) \in R$ iff $x_k+y_k = 1$ for $k=0,...,n$.
Aside: Note that this is different than finding the base 3 expansion of $x+y$. For example, $(x,y) = (2,2)$ is not in $R$, but $(x+y)_3 =11_3$. 
Algorithm:


*

*Write $x = 3 n_x+r_x$, $y = 3 n_y + r_y$

*If $r_x+r_y \neq 1$ return $(x,y) \notin R$

*If $n_x=0$ and $n_y=0$ return $(x,y) \in R$

*$x \leftarrow n_x$, $y \leftarrow n_y$

*goto Step 1

