If the number $"1"$ is written at the beginning, at least how many steps should be taken to reach $2^{2018}?$

Question

I have a problem understand this math problem:

Write a number on the board. This number is either multiplied by $2$ or raised to a square. If the number $"1"$ is written at the beginning, at least how many steps should be taken to reach $2^{2018}?$

A) $15$

B) $16$

C) $17$

D) $18$

E) $12$

I can't solve this problem. Because I don't understand the question. Now, I need to understand the question. Then maybe I can.

Is there a problem in the question? The question unclear for me...Can you explain me, what is the meaning of the question?

Answer 1

Since you want to go to $2^{2018}$, it's easier to use exponents: the operations are doubling or adding $1$, start from $0$ and get to $2018$.

The best strategy is going backwards: $$ 2018 \xrightarrow{/2} 1009 \xrightarrow{-1} 1008 \xrightarrow{/2} 504 \xrightarrow{/2} 252 \xrightarrow{/2} 126 \xrightarrow{/2} 63 \xrightarrow{-1} 62 \xrightarrow{/2} 31 \xrightarrow{-1} 30 \xrightarrow{/2} 15 \xrightarrow{-1} 14 \xrightarrow{/2} 7 \xrightarrow{-1} 6 \xrightarrow{/2} 3 \xrightarrow{-1} 2 \xrightarrow{/2} 1 \xrightarrow{-1} 0 $$ Is this the most efficient way?

At odd numbers you have no choice. Suppose the number $n$ is even; if it is a multiple of $4$, $n=4k$, you get at $k$ in two steps and this is obviously the best choice: otherwise you have to subtract $1$ twice, divide by $2$, subtract $1$ and divide again by $2$ just to arrive at $k-1$, five steps against two for a very small gain; in the average, this method is worse. If $n=4k+2$ you can choose between dividing by $2$ and subtracting $1$ or subtracting $1$ twice and dividing by $2$: two steps in the former case, three in the latter.

Answer 2

I think the problem means:

Given the two functions $$ f(x) = 2x \\g(x) = x^2 $$ consider sequences of $f$s and $g$s such that, $$ g(f(g(g(\cdots(g(f(1)))\cdots )))) = 2^{2018} $$ What is the length of the shortest such sequence?

For example, one sequence that qualifies is $$ \underbrace{f\circ f\circ \cdots \circ f \circ f}_{2018\;f\text{s}} $$ But that is not the shortest possible sequence, because $$ g\circ \underbrace{f\circ f\circ \cdots \circ f \circ f}_{1009\;f\text{s}} $$ also works.

Answer 3

You start with $1$. Then you can double that to get $2$, double it again to get $4$, then again to get $8$ and once again to get $16$. It took four steps to get to $16=2^4$.

But I could also have started at 1, then doubled it to $2$, then squared it to $4$, then squared that to get $16$. This way it only took three steps to reach $16=2^4$.

Your problem asks you to get to $2^{2018}$ instead of $2^4$, but the idea is the same. Use these two operations to get there as fast as possible.

Hint: Write everything as powers of $2$, starting with $1=2^0$. That makes all the numbers that appear a lot easier to handle.

Answer 4

It is easy to see that at first we find a way to have $2$ so we multiply by $2$

Now it is obvius that raising to the square is much easier to have a big number if we raise to the square we will have $2^2$ now we will do a string of operations by multiplying or raising to the square $$1 - 2-2^2-2^3-2^6-2^7-2^{14}-2^{15}-2^{30}-2^{31}-2^{62}-2^{63}-2^{126}-2^{252}-2^{504}-2^{1008}-2^{1009}-2^{2018}$$ So the answer is $17$.