Inspired by Romain

The integer part shall be added in the end, by performing a series of +1s. As for the fractionary part:

We want to approximate a generic decimal base 10 number e.g. 0.15 to 2 decimal places. The minimal set of {+1, /2} operations consists in either finding the exact base 2 number (in case the number, truncated to the wanted Nth decimal digit equals exactly a sum of powers of (1/2)^n or by finding the minimum upper bound in range [0.15,0.16).

My proof follows the lines of:

1) Deal with the integer part (E.g. Calvin Lin's Lemma 1).

This amounts to obviousness. Adding ad even number of ints and dividing by 2 equals wasting moves. By performing /2 when we have an odd integer part, we halve the existing decimal part and add 0.5 to it, but this can be achieved by a shorter set of moves ( e.g. we want to turn 0.125 into 0.625, adding 0.5. in order to achieve 0.125 we previously performed 0.25 /2 , revert that division, add 1, making 1,25 and finally divide, making 0.625). Therefore in our stream of operations our integer part never exceeds 1 until the fractionary part has been correctly approximated)

2) Explain why, for each power of 2, we want it at most once.

This is because binary 0.0000YXXXXX the Y is equal to infinite 1s to its right and therefore skipping this power of (1/2) results into a lower bound.

3) Explain why we always want to take away the largest power of 2 within the given bounds.

In case our approximation is not a perfect sum of powers of (1/2) a defective approximation will not satisfy our problem and an excess approximation adds operations because the bigger the number, the more operations are required to push the binary digit in place. Therefore we perform a logic AND to match the powers of 1/2 that the two numbers (lower and upper bound) have in common, if any and then add to this number the least binary digits that satisfy our approximation. This is exactly one digit or a set of digits, as least right-shifted as they need to be. Voit-lá.

Previous discussion:

I figured out you can find a certain sum of powers of decimal (1/2) and take its leftmost ciphers. For example binary 0.1 is equal to decimal 0.5 or (1/2) . Binary 0.01 (second decimal place) is decimal (1/2)^2 or 1/4 and makes 0.25.
Binary 0.11 is their sum (decimal 0.75). So in order to approximate the decimal part of an integer in binary (the integer part needs to be summed later), we need to try adding an 1 to the right as a new decimal digit.
By adding this 1 to tne binary number, we obtain can convert this number into decimal and compare it to the target number. If the decimal part is greater than the target number, we precede this last 1 with a zero (pushing it to the right).
If it's lesser, we add an 1 to the right, until it's greater, then we precede this last 1 with zeros again until it's less or equal. And so on, until we approximated the exact decimal part up to the Nth cipher we cared about.
As a last step we perform a scroll of this number from right to left. For every 1 we encounter, we perform "+1" and then "/2". For every zero, we perform "/2".
At the end of this step we have 0.xxxxxxxxx
Then we sum the eventual integer part (+1,+1,+1 etc N times as many as the units we want to add to 0.xxxx ) and we are done. Your problem is great because all we have to do is find the binary 0.000001 which is decimal 0.015625 and approximates the number up to the point we care.

First we check if the approximation is already sufficient up to the Nth cipher we wanted and then:

• if the decimal part is greater than the target number, we precede it with a zero

else

• if it's lesser, we add an 1 to the right

• repeat step 1"

I need to demonstrate two things.

1) adding units at the very end, after obtaining the decimal part (0.xxxxxx) is optimal. Rephrasing, the final operations will be a series of +1. This can be proven by absurd. If we perform /2, then in case of an even number as the integer part, we simply halve the integer part, wasting moves. For example we need +1+1 to make 2 but +1+1+1+1/2 wastes 3 moves. If we need to halve the decimal part we can perform /2 and afterwards add the integers. If we halve an odd number we waste moves but add 0.5 to the decimal part, moreover we halve the already present decimal part. But:

• Adding 0.5 can be done by avoiding a /2 (if this was the last operation performed) and then adding 1 and dividing by 2. Example: we have 0.125 and want to turn it to 0.625 (the goal is to add 0.5). 0.125 was obtained by performing 0.25 /2 (otherwise we would have 1.125, contraddicting statement 1). So we revert 1 move and go back to 0.25. we add 1 (1.25) and then divide by 2, resulting in 0.625. We can eventually add 1 afterwards. So this proves adding units at the end is either the optimal strategy or equal in cost with other optimal strategies (e.g. target number 1.5 : +1 +1 +1 /2 equals +1 /2 +1 but this is the best solution).

2) Until the final part, when we perform the final addition of units, it is not optimal (or equivalent to optimal in few cases but never better) to perform more than +1 between /2 s.

Let me make an example. We are still building the decimal part of 0.xxx. Say we got to 0.625 in binary 0.101. +1: 1.101 we can now perform /2 and right shift it: 0.1101, adding information. if we perform +1 instead we get 2.101. /2 makes 1.0101 (waste of move). Because +1 +1 /2 achieved the same result as /2 +1

Suppose +3 (shorthand for +1+1+1) /2 was efficient. we are adding binary 11 and shifting one place to the right. We can achieve the same with +1 /2 +1

Suppose +5 (binary 101) /2 (total 6 moves, turning 0.xxx into 10.1xxx) was efficient. We can achieve the same with +1 /2 +1 +1 (total 4 moves).

And so on.

Any even number wastes moves, an odd number adds 0.5 to the decimal part after halving it, and statement 1) proves there is a more or equally efficient way to do it.

Therefore I proved point 2.

So we know, as the binary representation suggests, that the (or one of the) optimal strategy is to add integer units at the very end and before that, perform a series of /2 with at most one +1 between them.

The most efficient way to represent the numbers after the decimal on Lynn's calculator is to read the binary representation from right to left and use $\boxed{+1}$ , $\boxed{\div 2}$ for each $1$ and $\boxed{\div 2}$ for each $0$ . The question is what is the minimum place value that Lynn can start at and still get $1.0156$ .

Now $\frac{1}{2^1} = 0.5$ , $\frac{1}{2^2} = 0.25$ , $\frac{1}{2^3} = 0.125$ have an affect on the number immediately after the decimal because their decimal representations have a number in the tenth spot, but $\frac{1}{2^4} = 0.0625$ (and all powers of $2$ after this) do not, because $2^3 < 10^1 < 2^4$ . Likewise, exponents $\frac{1}{2^4}$ through $\frac{1}{2^6}$ have a number in the hundredth spot, but $\frac{1}{2^7}$ (and all powers of $2$ after this) do not, because $2^6 < 10^2 < 2^7$ . For a decimal representation to be accurate to $1$ decimal place, in most cases Lynn must be sure that that the $2^{nd}$ number is also accurate to deal with rounding, and so at most $6$ binary decimals are needed, because $2^6 < 10^{1 + 1} < 2^7$ . Using this logic, in general, to be accurate to $n$ decimal places, in most cases at most $\lfloor \frac{n + 1}{\log 2} - 1\rfloor$ binary decimals are needed.

However, the number of binary decimals needed can be shortened if the last few numbers in the $\lfloor \frac{n + 1}{\log 2} - 1\rfloor$ binary decimals are all $0$ s or all $1$ s. If the last few numbers are $0$ s, then the binary representation can be truncated because the $0$ s are unnecessary. If the last few numbers are $1$ s, then $1$ can be added to the $\lfloor \frac{n + 1}{\log 2} - 1\rfloor$ spot without changing the decimal representation value, and the addition will change all the last $1$ s to $0$ s and the last $0$ to $1$ , allowing another truncation because of unnecessary $0$ s.

So for $1.0156$ , accurate to $4$ decimal places, Lynn would at most need $\lfloor \frac{4 + 1}{\log 2} - 1\rfloor = 15$ binary decimals. However, since the first $15$ decimal places of the binary of $1.0156$ is $1.000000111111111$ , which ends in a sequence of $1$ s, Lynn can add $0.000000000000001$ to get a shorter binary of $1.000001$ . Then using the method described above, Lynn can display $1.0156$ on her calculator by entering $\boxed{+1}$ , $\boxed{\div 2}$ , $\boxed{\div 2}$ , $\boxed{\div 2}$ , $\boxed{\div 2}$ , $\boxed{\div 2}$ , $\boxed{\div 2}$ , $\boxed{+1}$ , which is $\boxed{8}$ button presses.

[This is not a complete solution. It is to guide you that the answer is not ~15.]

Hint: We care about getting some number from $1.0156$ to $1.0157^-$ . Working directly with 1.0156 may not be the most appropriate choice.

Hint: To reach exactly the real number $r$ , the binary representation (of the fractional part) allows us to determine the minimum number of steps needed. In particular, if a number has an infinitely long binary representation, then it cannot be reached in finitely many steps.

Hint: There's something special about the binary representation that caused me to choose this number. Think about it.

Here is a sketch of a rigorous solution.

Lemma 1: The minimum number of steps to get any real number $r$ is given by $\lfloor r \rfloor +$ the minimum number of sets to get $\{ r \}$ .
Proof: Obviousness.

Henceforth, I'm restricting to talking about fractional parts $0 \leq r < 1$ .

Lemma 2: For a given binary representation of $0 \leq r < 1$ , $r = 0.\ldots _ 2$ , the minimum number of steps needed to reach exactly that number, is given by the formula that everyone is thinking of.
Proof that this can be achieved - Obviousness.
Proof of no lower value can be achieved - Obviousness.

Lemma 3 : If we want to get the first $x$ digits to look like $0 \leq r < 1$ , then we just need to consider all the binary representations from $r$ to $r + 10^{-x}$ . We have to check where the first $k$ digits of $r_2$ and $( r + 10 { - x } ) _ 2$ agree. That, in turn, gives us the actual binary representation we want to use to arrive at the (globa) minimum.
Proof - Requires a bit of work to understand what I mean by "that, in turn, gives us the actual binary representation". But otherwise, obviousness.