When a positive integer $N$ is fed into a machine, the output is a number calculated according to the rule shown below.

For example, starting with an input of $N=7,$ the machine will output $3 \cdot 7 + 1 = 22.$ Then if the output is repeatedly inserted into the machine five more times, the final output is $26.$ $$\begin{align*} &7 \to 22 \to 11 \to 34 \\ &\to 17 \to 52 \to 26 \end{align*}$$ When the same $6$-step process is applied to a different starting value of $N,$ the final output is $1.$ What is the sum of all such integers $N?$ $$\begin{align*} &N \to \underline{\phantom{00}} \to \underline{\phantom{00}} \to \underline{\phantom{00}}\\ &\to \underline{\phantom{00}} \to \underline{\phantom{00}} \to 1 \end{align*}$$

Answer: E

Concepts:work backwardstree diagram

Difficulty rating: 1670

AMC 8AMC 10AMC 12AIME

Video solution:

Click to load, then click again to play

Written solution:

Work backward from $1.$ A value $m$ can always come from the even input $2m.$ It can also come from the odd input $(m-1)/3$ when that expression is a positive odd integer.

Listing the possible values after each backward step gives $$\begin{aligned} \{1\}&\leftarrow\{2\}\leftarrow\{4\}\leftarrow\{1,8\}\\ &\leftarrow\{2,16\}\leftarrow\{4,5,32\}\\ &\leftarrow\{1,8,10,64\}. \end{aligned}$$ Thus the possible starting values are $1,8,10,64,$ whose sum is $83.$

Thus, the correct answer is E.