Collatz Conjecture

The trick is that the problem asks for any possible initial value. That word “any” is doing a lot of work here.

We are given the value after $k$ Collatz operations, and we need to output some number that could have started the process.

The operation is:

• if $x$ is even, $x \gets \frac{x}{2}$
• if $x$ is odd, $x \gets 3x+1$

So instead of trying to simulate forward from some mystery number, reverse the process.

One reverse step

Suppose the current known value is $x$. What number could have appeared immediately before it?

The easiest answer is always:

$$2x$$

Why? Because $2x$ is even, and one Collatz operation on it gives:

$$\frac{2x}{2}=x$$

So $2x$ is guaranteed to be a valid predecessor of $x$.

There might also be an odd predecessor if $x = 3y+1$ for some odd $y$, but we do not care. Chasing that path is extra work for zero gain. The boring even predecessor works every single time.

Doing $k$ reverse steps

If one reverse step changes $x$ into $2x$, then doing $k$ reverse steps changes it into:

$$x \cdot 2^k$$

Now check it forward:

Starting from $x\cdot 2^k$, the number is even. After one operation it becomes $x\cdot 2^{k-1}$. After another, $x\cdot 2^{k-2}$, and so on.

After exactly $k$ operations, it becomes:

$$x\cdot 2^0=x$$

So $x\cdot 2^k$ is always a valid initial value.

Bounds

Here $k,x\le 20$, so the largest answer from this construction is:

$$20\cdot 2^{20}=20{,}971{,}520$$

That easily fits in a 32-bit integer, though using long long is the usual no-drama choice.

Algorithm

For each test case:

1. Read $k$ and $x$.
2. Multiply $x$ by $2$, exactly $k$ times.
3. Print the result.

Time complexity: $O(k)$ per test case, which is tiny.

You can also compute $x \ll k$, but repeated multiplication is clearer and still instant.