Add 1 Or Multiply By 3

Relevant wiki: Number Base - Problem Solving

If you think in base $3$ , then multiplying by $3$ is shifting the numbers to the left and adding a zero on the end.

So, these rules become much simpler, and I'll attempt to show below that $112222_3$ is the smallest number that will take at least $15$ moves, requiring, in this case, $5$ shifts, and $10$ " $+1$ "s.

To construct a number, for each digit $n$ from left to right you need to "add $n$ times and then shift once" and then repeat for all digits (not shifting after the last one of course). So, for example (all in base $3$ ), to make $112222_3$ , you would need to do this: $+1 \rightarrow \times 3 \rightarrow+1 \rightarrow \times 3 \rightarrow +1 \rightarrow +1 \rightarrow\times3\rightarrow +1 \rightarrow +1 \rightarrow\times3\rightarrow +1 \rightarrow +1 \rightarrow\times3\rightarrow +1 \rightarrow +1$

That's 15 moves.

I convinced myself that this is the smallest because if you go with $22222_3$ (the largest $5$ digit base $3$ number) you have $14$ moves, which isn't enough. So you need to go with six digits. So that's $5$ shifts, and the digits need to add up to $10$ , so 4 of them need to be $2$ 's. The smallest of these will be with the 1's at the far left, or $112222_3$ .

$112222_3 = \boxed{404_{10}}$

Make sense?

This proof with python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

"Add 1 Or Multiply By 3"

lst = [set([0])]

for k in range(15):
    lst.append(set([x +1 for x in lst[k]] + [3*x for x in lst[k] if x != 0]))

s = set()

for k in range(15):
    s = s.union(lst[k])

res = lst[15].difference(s)

print(min(res))

Output

1

404