A calculator only has 2 buttons. The buttons are, however, very powerful: they are programmable buttons, i.e. you can pre-set them to be any function (meaning any map from $\mathbb{Z}$ to $\mathbb{Z}$).
The calculator always starts with $1$. After you pre-set the buttons, a target number will be announced, and you need to get to that number by pressing as few buttons as possible.
Given that the target number is between $1$ and $10000$ (both inclusive), and that you want to minimize the number of button presses in the worst case, what is your strategy of setting the buttons?
Give as answer:
- a description of the button settings;
- a proof of the minimum number of presses needed (or an upper bound of that) with your settings.
In case optimality cannot be proved, the answer with the smallest provable bound wins. If an answer proves that itself is optimal, then of course it automatically wins.