Proving that a set of operations can't generate one integer from a given one

Given two numbers, $n$ and $m$, are there some mathematical methods of deducing $m$ from $n$ using limited number of elemantary operations?

Example: 335 can be deduced from 2000 using division by 2, addition of 5 and division by 3: $((2000/2)+5)/3) = 335$.

I need to prove that 1889 can't be derived from 2019 using the following 3 operations:

• $n+7$ ;

• $n*2$;

• $n/3$ (if divisible).

All I come up with is some sort of breadth-first search.

If you have implemented breadth first search correctly, you should have found that 1889 can be reached.

$\quad 2019+7\to 2026$

$\quad 2026+7\to 2033$

$\quad\quad\cdots\quad$ (add 7 repeatedly)

$\quad 4238+7\to 4245$

$\quad 4245 \div 3 \to 1415$

$\quad 1415 * 2 \to 2830$

$\quad 2830 * 2 \to 5660$

$\quad 5660 + 7 \to 5667$

$\quad 5667 \div 3 \to 1889$

It is possible that you had been asked to show that 1883 can't be derived from 2019.
A number can be derived from 2019 iff it is a positive integer not divisible by 7

Proof:

"$\Longrightarrow$": If $n$ is not divisible by 7, neither is any of $n+7$, $n*2$ and $n/3$ (when $n$ is divisible by 3). If we start with a number that is not divisible by 7, it will remain not divisible by 7 regardless of how many operations we have applied on it. Since 2019 is not divisible by 7, we cannot derive any number that is divisible by 7.

"$\Longleftarrow$":

In fact, we can derive all positive numbers not divisible by 7 without the operation $n\to n * 2$. For all $k\ge0$,

• $\dfrac{2019 + 7 (((7k+1)3^{6k+7}-2019)/7)}{3^{6k+7}}=7k+1$

• $\dfrac{2019 + 7 (((7k+2)3^{6k+11}-2019)/7)}{3^{6k+11}}=7k+2$

• $\dfrac{2019 + 7 (((7k+3)3^{6k+6}-2019)/7)}{3^{6k+6}}=7k+3$

• $\dfrac{2019 + 7 (((7k+4)3^{6k+9}-2019)/7)}{3^{6k+9}}=7k+4$

• $\dfrac{2019 + 7 (((7k+5)3^{6k+8}-2019)/7)}{3^{6k+8}}=7k+5$

• $\dfrac{2019 + 7 (((7k+6)3^{6k+10}-2019)/7)}{3^{6k+10}}=7k+6$

Exercises

Exercise 1. Assume the same three operations. Let $n$ be a positive number not divisible by 7. Then a number can be derived from $n$ iff it is a positive integer not divisible by 7.

Exercise 2. Assume the same three operations. Let $n$ be a positive number divisible by 7. Then a number can be derived from $n$ iff it is divisible by 7.

Exercise 3. If positive integer $m$ can be derived from positive integer $n$ using the three operations, then $m$ can be derived from $n$ using the first and last operations, namely, $n\to n+7$ and $n\to n/3$ (if divisible).

StackExchange Computer Science Q#110283, answer score: 3