A weird pocket calculator

Question

A weird pocket calculator has a numerical display (for digits 0-9) and only two buttons, inscripted $\boxed{D+}$ and $\boxed{D-}$. The first button doubles the displayed number and then adds 1. The second button doubles the displayed number and then subtracts 1. For example, if the display shows 6, then pressing $\boxed{D+}$ produces 13; if the display shows 6 and we press $\boxed{D-}$, we get 11.

Suppose that the initially displayed number is 1, and that we then perform exactly 22 button presses. How many different numbers that can possibly result from this?

Answer 1

4,194,304 (2²²) possible results

Why such a straightforward number?

Each press doubles the number of possible sequences and no two sequences can produce the same result.

Why not?

Each press redoubles the additive/subtractive effect of all previous presses, which have already been redoubled by any intervening presses. (The first press's effect has been doubled the most often.) After that, the new +1 or -1 will only make half the difference of the immediately preceding press. This is equivalent to a 22-digit binary number.

The exact final result, $V\!$, equals a 23-bit binary number built from the intermediate results $A$,$B$,...,$U$ of button presses $a$,$b$,...,$u$, followed by one last button press, $v$.

\begin{array}{lrrllll} \rm\llap{1st} ~press& a \;{=}\;{\pm}\!\: 1 & ~A ~~\rlap{=} ~& 2(1) + a & ~~\llap{=}~~~ \phantom{ 2( 2( } 2{+}a & ~~\llap{=}~~~ 2 + ~ a \\ \rm\llap{2st} ~press& b \;{=}\;{\pm}\!\: 1 & ~B ~~\rlap{=} ~&~ 2A ~ + b & ~~\llap{=}~~~ \phantom{ 2( } 2( 2{+}a )+b & ~~\llap{=}~~~ 4 + 2 a + ~ b \\ \rm\llap{3st} ~press& c \;{=}\;{\pm}\!\: 1 & ~C ~~\rlap{=} ~&~ 2B ~ + c & ~~\llap{=}~~~ 2( 2( 2{+}a )+b)+c & ~~\llap{=}~~~ 8 + 4 a + 2 b + c \\[-1ex] \quad\vdots \\[-1ex] \rm\llap{22nd}~press& v \;{=}\;{\pm}\!\: 1 & ~V ~~\rlap{=} ~&~ 2U ~ + v & ~~\llap{=}~~~ \rlap{ 2 ( \cdots 2 ( 2{+}a ) + \cdots ) + v } \\[1ex] & & \rlap{=} ~&~ \rlap{ 2^{22} + 2^{21} a + 2^{20} b + \cdots + 2^0 v } \\[1ex] & & \rlap{=} ~&~ \rlap{ 2^{22} \bigl( \frac12 {+} \frac a2 \bigr) + \, 2^{21} \bigl( \frac12 {+} \frac b2 \bigr) + \cdots + \, 2^1 \bigl( \frac12 {+} \frac v2 \bigr) + \, 2^0 ( 1 ) } \\[1ex] & & \rlap{=} ~&~ \rlap{ 23 \;\!\textrm{-bit binary number} ~\mathit{abcdefghijklmnopqrstuv} \!\: 1_{\!\:2} } \\[-.5ex] & & &~ \rlap{ \textrm{where the}~{-}\!\textrm{1s of}~ a,b,\dots,v ~\textrm{are replaced by 0}\!\:\textrm{s} } \end{array}

Each of the 4,194,304 ($2^{22}$) possible sequences of 22 button presses has a unique combination of values for $a$,$b$,$c$,...,$v$, which produces a unique value for $V\!$ and happens to cover all of the 4,194,304 odd numbers from 1 through 8,388,607 ($2^{23}{-}1$).

Sure enough, if every press were $\boxed{D-}$ then $V \! = 000\textrm{...}001_2 = 1$, the same as doubling the original 1 and diminishing that by 1 — producing no net change — 22 times. And if every press were $\boxed{D+}$ then $V \! = 11111111111111111111111_2$, which amounts to $2{\times}1111111111111111111111_2 + 1$, the same calculation as the 22nd and last repeated step of doubling an intermediate result and adding 1 before the next step.

Answer 2

The answer is:

4194304

Uhm... As someone pointed out this question has a no computer tag that I did not originally see. Please ignore my answer, I'll just leave it here to avoid the same mistake to others

Solved by simulation (the tree has 2^23 nodes, can do):

Set<Integer> values(int depth, Set<Integer> state) {
    if (depth >= 22) return state;
    else {
        Set<Integer> dPlus = state.stream().map(i -> i * 2 + 1).collect(Collectors.toSet());
        Set<Integer> dMinus = state.stream().map(i -> i * 2 - 1).collect(Collectors.toSet());
        Set<Integer> nextPlus = values(depth+1, dPlus);
        Set<Integer> nextMinus = values(depth+1, dMinus);
        nextPlus.addAll(nextMinus);
        return nextPlus;
    }
}

void run(String[] args) {
    System.out.println(values(0, new HashSet<>(Arrays.asList(new Integer[]{1}))).size());
}

Answer 3

hmmn's answer is certainly correct, here is, I believe, a more formal approach.

A number, $x_0=1$, is displayed.

• we may press $D-$ and produce $2x_0-1=1$, or
• we may press $D+$ and produce $2x_0+1=3$.

These are both odd integers, and odd integers may always be expressed as $2a+1$ where $a$ is an integer.

Fairly obviously, as soon as we press $D+$ we escape from $1$ and may never not increase the number displayed.

Thus the only way to achieve a specific number with a specific quantity of button presses is to reach it with the final button press (e.g. $1$ only results from a sequence entirely of $D-$ and $3$ from a sequence of all $D-$ and a final $D+$).

If $x_n$ is $2a+1$ then $x_{n+1}$ is either

• $2(2a+1)-1$, or
• $2(2a+1)+1$.

Two different odd integers from which we may branch again, $D+$ producing the bigger of the two.

The biggest number we may achieve with $m$ presses would be

$$1 +\sum_{i=1}^{m}{2^i}=2^{m+1}-1$$ by only pressing $D+$.

Thus with $m$ presses we may yield $2^m$ odd integers between $1$ and $2^{m+1}-1$ inclusive.

There are exactly $\frac{2^{m+1}-1+1}{2}=\frac{2^{m+1}}{2}=2^m$ odd integers in this range, thus all such integers may be yielded.

Here $m = 22$ so we may produce any of the odd integers from $1$ through $2^{22+1}-1=8,388,607$

There are $2^{22}=4,194,304$ such numbers.