# 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:

1. $$n+7$$ ;
2. $$n*2$$;
3. $$n/3$$ (if divisible).

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

## 2 Answers

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).

• I think you meant "remainder" instead of reminder. Did you may also mean remainders of numbers divided by 3 instead of 7? Commented Jun 5, 2019 at 22:15
• I mean 7. Does 3 work for you? Commented Jun 6, 2019 at 4:07
• Probably I need to clarify the question. All this operations should be done on number derived from initial number. 2019 - 1 level. 2019+7=2026, 2019*2=4038, 2019/3=673 - 2 level. Then we break 2026 from 2 level again 2026+7=2033, 2026*2=4052, 2026/3=with remainder (we don't need it anymore). And so for every integer that we meet executing this 3 operations.Next will be 4038 ... Commented Jun 6, 2019 at 6:52
• $2019+7=2026$. Then $2026+7=2033$. Then $2033+7=2040$. Then $2040+7=2047$. Then $2047+7=2054$. Then $\cdots$ (many steps of adding 7). Then $4238+7=4245$. Commented Jun 6, 2019 at 8:07
• @cs_student You mean, that we have a additional rule? Here, we have to (1.): add 7; then (2.) multiply with 2 and last (3.) divide by 3 if possible, otherwise start from step 1 again? Then this problem is way more easier. I asked my algorithmics professor and he immediately conjected that this problem would be $NP-complete$ or even $EXPTIME$-hard if we can arbitrarely shuffle the composition of functions since they dont form a composition ring. . Commented Jun 7, 2019 at 9:41

Define $$f(x) = x/3, g(x) = 2x, h(x) = x+7$$ and $$D = \mathbb{N}$$ for the functions $$f,g,h$$. I presume that the question is the following:
Given $$x,y \in \mathbb{N}$$ is there a transformation sequence $$s_{(n)}:= (f \circ g \circ h) ^{n}$$ such that $$(f \circ g \circ h) ^{n}(x) = y)$$ with the restriction that always $$3 | (g\circ h)(f \circ g \circ h) ^{n-1}(x)$$ ?

Now write $$s_{(n)}$$ as a direct expression depending only on $$x,n$$. Lets call this $$c(x,n)$$. Here $$c(x,n) = \frac{2^nx+14(2^n-1)}{3^n}$$ For simplicity we write also $$c(x,n):=\frac{num(x,n)}{3^n}$$

Given $$x,y$$, then $$y$$ can be derived from $$x$$ iff $$c(x,n)=y$$ has a has at least one natural solution for $$n$$ and $$3^i | num(x,i)$$ for all $$i \leq n, i \in \mathbb{N}$$.

Applied this result to the conrete numbers, we see that the positive $$n \approx 0.166$$ and hence 1889 can not be derived from 2019.

If there are no restrictions on the composition of the function, this problem is (according to my professor) at least $$NP$$-complete. A formal proof would be nice, until now I didnt find a suitable Problem for a sharp reduction.