The Keys problem

Question

Another challenge: A calculator has two special keys:

• A key transforms a number x in the number 2x.
• B key transforms a number x in the number 2x - 1.

Is it true that if you start with any positive integer, it is possible to press a special key sequence in such a way as to obtain finally the fifth power of an integer?

By simple inspection one realizes that the powers of 2 greater than 1 you can get a fifth power using the A key, but will be possible with other numbers?

Answer 1

If the question is of the form suggested by Scaramouche's comment, then the answer is no. Both keys are permutations on $\mathbb Z/9$, so any key sequence is also a permutation, and therefore there is some starting $x$ which gets sent to $3$. But $3$ is not a fifth power in $\mathbb Z/9$.

Answer 2

In this post, I shall interpret the problem as follows. For any positive integer $n$, if we start with $n$ and perform some sequence of the keystrokes $A,B$, we will reach a fifth power of a positive integer. It should be noted that Chris Culter resolved the interpretation with quantifiers reversed in another answer.

Hold $n$ fixed throughout.

Lemma 1. For any nonnegative integer $k$ and any integer $x$ in the interval $[2^kn-2^k+1,2^kn]$, there is a sequence of keystrokes which results in $x$ starting at $n$.
Proof. We induct on $k$. If $k=0$, then the interval is just $\{n\}$ consisting of only our starting value. Thus, assume $k>0$ and the inductive hypothesis for $k-1$. $$2^kn-2^k+1\le x\le 2^kn\implies 2^{k-1}n-2^{k-1}+1\le\left\lceil\frac x2\right\rceil\le 2^{k-1}n$$This means $\left\lceil\frac x2\right\rceil$ is the result of a sequence of keystrokes starting at $n$. If $x$ is even, $2\left\lceil\frac x2\right\rceil=2\frac x2=x$. If $x$ is odd, $2\left\lceil\frac x2\right\rceil-1=\frac{2(x+1)}2-1=x$.$\space\square$

Lemma 2. There exists an integer $k\ge 0$ such that for any positive integer $x$ satisfying $x^5\le 2^kn$, $$(x+1)^5-x^5\le 2^k-1.$$
Proof. First $(x+1)^5-x^5=1+5x+10x^2+10x^3+5x^4\le 31x^4\le 31\left(\sqrt[5]{2^kn}\right)^4$. Since $31x^4$ is an integer, we only need to find $k$ large enough that $\lfloor31(2^kn)^{4/5}\rfloor\le 2^k-1$ holds.

However, if $k>5\log_2(31n^{4/5})$, then $$31(2^kn)^{4/5}=2^{(4/5)k}(31n^{4/5})<2^{(4/5)k+(1/5)k}=2^k,$$ using $2^{(1/5)k}>31n^{4/5}$. It follows that $$(x+1)^5-x^5\le\lfloor31(2^kn)^{4/5}\rfloor\le 2^k-1.\space\square$$

Theorem. There is a positive integer $x$ such that $x^5$ can be reached by a sequence of keystrokes starting at $n$.
Proof. Let $k$ be as in Lemma 2. It suffices, by Lemma 1, to show that there is a fifth power in the interval $[2^kn-2^k+1,2^kn]$. There is a greatest integer $x$ such that $x^5<2^kn-2^k+1$. Then, $(x+1)^5-x^5\le2^k-1$, so $$(x+1)^5=(x+1)^5-x^5+x^5<2^k-1+2^kn-2^k+1=2^kn.$$ Hence, $(x+1)^5$ must be within the interval $[2^kn-2k+1,2^kn]$.$\space\square$

Answer 3

First, we characterize the space we're working with.

Let $X_n$ denote the set of $n$-tuples with entries in $\{A,B\}$ and consider the sets $$G_k=\bigcup_{j=1}^k\left\{\left(\prod_{i=1}^jx_k\right)m:x\in X_n\right\}\subseteq \mathbb{Z}[m]$$ Now let's form $\bar G=\bigcup_{k=1}^\infty G_k$.

Claim. $$\bar G = \bigcup_j\left\{2^jm-2^{j}+1,\ldots, 2^jm\right\}.$$

Proof. We'll prove this by induction. Write $L_j=\left\{2^jm-i:i=\{0,\ldots,2^j-1\}\right\}$. The base case is trivial. Now, $$\begin{eqnarray*}A L_n&=&\left\{2\times (2^nm-i):i\in\{0,\ldots,2^n-1\}\right\}\\&=&\left\{2^{n+1}m-i:i\in\{0,2,\ldots,2^{n+1}-2\}\right\}\end{eqnarray*}$$ and $$\begin{eqnarray*}B L_n&=&AL_n-1\\&=&\left\{2^{n+1}m-i:i\in\{1,3,\ldots,2^{n+1}-1\}\right\}\end{eqnarray*}$$ so $$L_{n+1}=AL_n\cup BL_n.$$

If we define $\varphi_n:\bar G \rightarrow \mathbb{Z}$ by $\varphi_n(f)=f(n)$ and $g(x)=x^5$, we want to prove that, for every $n\in \mathbb{N}$, $$\varphi_n[\bar G]\cap g[\mathbb{Z}]\ne\emptyset.$$ Our strategy will be to find a big enough $j$ so that $\varphi_n[L_j]$ is large enough that it must contain a fifth root (so that $g^{-1}(x)$ is an integer for some $x\in L_j$). Of course we can find such a number so long as $$f_m(j)= g^{-1}\left(2^jm\right)-g^{-1}\left(2^j(m-1)+1\right)\geq 1$$ which, by some relatively messy calculations, is true when $g(x)=x^5$. I've left $g$ arbitrary to make the point that not just fifth roots, but in fact any roots suffice, as well as any increasing polynomial function.