Integers less than $7000$ achievable by starting with $x=0$ and applying $x\to\lceil x^2/2\rceil$, $x\to\lfloor x/3\rfloor$, $x\to9x+2$

Question

Problem

Robert is playing a game with numbers. If he has the number $x$, then in the next move, he can do one of the following:

• Replace $x$ by $\lceil{\frac{x^2}{2}}\rceil$
• Replace $x$ by $\lfloor{\frac{x}{3}}\rfloor$
• Replace $x$ by $9x+2$

He starts with the number $0$. How many integers less than or equal to $7000$ can he achieve using the above functions?

[It is permitted to use a number greater than $7000$ in the way of achieving the desired numbers.]

My Approach

Call the functions $f_1,f_2,f_3$ respectively. $2$ is easily achievable from $0$ (using $f_3$). I've found that all the integers from $0$ to $10$ are achievable (Though we achieve them in a long way). The numbers get messy when we get ahead further. I can't prove that any number is unachievable. I've noticed that base-$3$ numbers can help for $f_2$ and $f_3$.

---

How to get ahead further?

Update: Mr. Mike showed that all integers are achievable by this process through codes. Mr. Calvin also gave a partial proof for that. So, a complete proof is needed currently.

Answer 1

Too long for a comment, but with the help of a computer, I found that all numbers in $\{1,\dots,7000\}$ are indeed reachable. I verified this with the following Python code, which uses a priority queue to find reachable numbers. The best priority ordering I found was to try the $\lfloor x/3\rfloor$ operation first, then to try the $\lceil x^2/2\rceil$ operation, and resorting to $9x+2$ last.

Try it online!

from heapq import heappush, heappop

targets = set(range(1, 7001))
num_targets_left = 7000

seen = set([0])
Q = [(0,0)]

while num_targets_left > 0:
    current = heappop(Q)[1]
    to_add = [(0,current//3), (1,(current**2 + 1)//2), (2,9*current + 2)]
    for (priority_level, num) in to_add:
        if num not in seen:
            seen.add(num)
            heappush(Q, (priority_level, num))
            if num <= 7000: 
                targets.remove(num)
                num_targets_left -= 1

print('All numbers in {1,...,7000} are reachable.')

I found the the hardest number was $6121$. The path that led to it below. Here, third x 7 means you do this $\lfloor x/3\rfloor$ operation $7$ times.

Number          Next operation(s)
----------------------------------
0               9x + 2
2               9x + 2
20              half-square
200             third x 3
7               half-square
25              third x 1
8               half-square
32              third x 1
10              half-square
50              third x 1
16              half-square
128             third x 2
14              half-square
98              half-square
4802            third x 5
19              half-square
181             half-square
16381           third x 4
202             half-square
20402           third x 4
251             half-square
31501           third x 4
388             half-square
75272           third x 6
103             half-square
5305            third x 3
196             half-square
19208           third x 2
2134            half-square
2276978         third x 5
9370            half-square
43898450        third x 9
2230            half-square
2486450         third x 6
3410            half-square
5814050         third x 6
7975            half-square
31800313        third x 7
14540           half-square
105705800       third x 8
16111           half-square
129782161       third x 9
6593            half-square
21733825        third x 7
9937            half-square
49371985        third x 8
7525            half-square
28312813        third x 8
4315            half-square
9309613         third x 6
12770           half-square
81536450        third x 8
12427           half-square
77215165        third x 8
11768           half-square
69242912        third x 8
10553           half-square
55682905        third x 7
25460           half-square
324105800       third x 9
16466           half-square
135564578       third x 8
20662           half-square
213459122       third x 8
32534           half-square
529230578       third x 9
26887           half-square
361455385       third x 10
6121            

Answer 2

This is not a valid solution.
Ravi pointed out that there is an error.

---

Claim: For any integer $n$, there exists integers $K , L \geq 0$ such that $$ n\times 3^K \leq 2 \times 10 ^{2^L} \leq (n+1) \times 3^K.$$

Proof: Working mod $\log 3$, we want to show that there exists a $L > 0$ such that

$$ \frac{\log n - \log 2}{\log 10} \leq 2^L \leq \frac{\log (n+1) - \log 2}{\log 10} \quad \pmod{ \log 3}$$

(I am unable to complete this proof. It requires us to show that $\frac{1}{ \log 3} $ in base 2 has all finite binary strings.)

Corollary: $ b^K a^{L-1} c^2 (0) = n$, where

• $a(x) = \lceil \frac{ x^2 }{ 2 } \rceil $
• $b(x) = \lfloor \frac{x}{3} \rfloor $
• $c(x) = 9x+2$.

---

Notes

• As conjectured and established via computer by Steven and Mike respectively, after using $ c(0) = 2, c(2) = 20$, it seems like we don't need the $c(x)$ function anymore.
• In addition, since $ab(x) \approx b^2a(x) \approx \frac{x^2}{18}$ (but the floor and ceiling functions could get in the way of equality), if there was a sequence to get to $n$ using just $a(x), b(x)$, then it might be reasonable that we could collate $a(x), b(x)$ separately.
• The above 2 comments could motivate the given solution. However, that's not how I came up with it.
• Working in base 3 is suggested by functions $b(x), c(x)$, and $bbc(x) = x$.
• (for me at least) Viewing $b(x)$ as truncating in base 3 and $c(x)$ as appending 02 in base 3, made it much easier to think about these function.
• Based on initial iterations (esp because I avoided $a(x)$ as that made numbers huge), my guesses for achievable numbers were like A) $6k, 6k+2$, B) $2k$, C) Trenary numbers involving only 0 and 2 (maybe with additional conditions).
• It is clear that if we only used $b(x), c(x)$, then the base 3 representations are limited to digits of 0 and 2 (and in fact, 2's must be separated by 0's). The followup question is "Can we introduce a digit of 1 in base 3 using $a(x)$"?
• We could do that with $ a(20) = 200 = 21102_3$, and so I thought that the set of achievable numbers were Numbers in base 3 whose starting digit was 2.
• Looking at $a^2 (20) = 20000 = 1000102202_3$, I realized that would give us $1$ (and $10_3, 100_3, \ldots)$.
• With that realization, we simply want the inequality in the claim.
• Of course, there could be other ways of reaching $n$. One possible approach could be to show that we can reach all even numbers, and then by applying $b(x)$ we can reach all numbers.