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