8
$\begingroup$

A calculator only has 3 buttons. The first multiplies the current value by 3, the second adds 2 and the third subtracts 2. The calculator always starts with 0. What is the smallest positive even number that requires at least 10 button presses to make?

Here is the first version of the puzzle: Three button calculator

$\endgroup$
8
$\begingroup$

The smallest number is:

244

Proof:

Let's work backwards. Instead of reaching the number starting at 0, we reduce the number to 0 by undoing the steps, i.e. by adding/subtracting 2 or dividing by 3.

The following statements are true:
Any even number 2 or less can be reduced to 0 in at most 1 step.
Any even number 8 or less can be reduced to 0 in at most 3 steps.
Any even number 26 or less can be reduced to 0 in at most 5 steps.
Any even number 80 or less can be reduced to 0 in at most 7 steps.
Any even number 242 or less can be reduced to 0 in at most 9 steps.

The first statement is trivially true. Each following statement is easy to check given the previous one. For example, given any number of 242 or less, it is either a multiple of 3 or else you can add/subtract 2 to make it so. You can then divide it by 3. In this way you will have reduced it to an even number of 80 or less using at most 2 steps.

So the first even number for which 10 steps might be necessary is 244. It can be done in 10 steps in any of the ways going left to right in this diagram:

 244-246- 82-84-28-30-10-12-4
    \       \     \     \    \
     242-240-80-78-26-24- 8-6-2-0

244 cannot be done in fewer steps because any alternative route will go to the left in the diagram, or takes an even longer off-piste route involving 3 consecutive additions/subtractions to go from one multiple of three to another.

$\endgroup$
  • 1
    $\begingroup$ indeed! oeis.org/A024023 $\endgroup$ – JMP Nov 12 at 6:45
  • $\begingroup$ @JMP All the shortest ways through my diagram are 10 steps. The only places where you can go off that diagram is if from a multiple of 3 you do (((x+2)+2)+2)/3 or (((x-2)-2)-2)/3. Those can be done quicker as (x/3)+2 or (x/3)-2 respectively. $\endgroup$ – Jaap Scherphuis Nov 12 at 8:38
  • $\begingroup$ @JMP Lots of larger numbers can be done much quicker. 244 is the worst case for 10 steps because it needs so many additions/subtractions. $\endgroup$ – Jaap Scherphuis Nov 12 at 9:19
3
$\begingroup$

With a single button press we can get 2.

In two steps we can reach 4 and 6.

From there we can reach three new numbers: 8, 12 and 18 require a minimum of three steps.

Seven additional numbers within reach of four button presses; 10, 14, 16, 20, 24, 36 and 54.

Continuing this enumeration through nine steps, we find that the smallest positive even number not within reach is:

244

$\endgroup$
  • $\begingroup$ Can 244 be reached on the next 10th step though? $\endgroup$ – Dmitry Kamenetsky Nov 12 at 6:11
  • 1
    $\begingroup$ @Dmitry If 244 is the smallest that cannot be reached with nine steps, then 242 can be reached in nine steps, and only one step is needed from there. $\endgroup$ – Daniel Mathias Nov 12 at 6:18
  • $\begingroup$ Ah yes good point! $\endgroup$ – Dmitry Kamenetsky Nov 12 at 6:45
-1
$\begingroup$

By my understanding of the given rules, the smallest number is

2

The calculator starts with 0, so

0 x3x3x3x3x3x3x3x3x3 +2

$\endgroup$
  • 1
    $\begingroup$ Hello Schmeich, and welcome. Actually, your answer can also be reached in 1 step, so 10 steps are not required. The question asked for a number that requires 10 steps or more. $\endgroup$ – Laurent LA RIZZA Nov 12 at 14:28
  • $\begingroup$ Ah, got your point. My bad. $\endgroup$ – Schmeich Nov 12 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.