The pre-alpha calculator

Question

You are given a rudimentary prototype of a calculator with only the following keys:

0 1 2 3 4 5 6 7 8 9 + - × ÷ =

The display has place for 10 digits and is initially showing 0.

Since this is still in a very early development stage, each key can be pressed only once, after which it will stop working.

For the rest, the calculator is already working well and applies the usual operator precedence rules when performing arithmetic calculations.

The result of a calculation is displayed when the = key is pressed. The calculator does not show intermediate results.

---

What is the smallest positive integer that cannot be displayed on the calculator?

Answer 1

Partial, currently uninformative and possibly illegal answer:

I have written some brainless Python code to form numbers in this way.

First I wrote a program that just tries things at random. After (depending on how you count) somewhere around 350 million trials, the first numbers it hasn't found a representation for are: 99109, 99326, 99334, 99590, 99664, 99804.

I also have something that does an actual exhaustive search, trying successively longer strings of keys with (for a given length) successively more operators allowed to be used. It's nice to know that certain things aren't possible in certain ways, but this seems to be somewhat less efficient in numbers found per minute elapsed. I will report on its results when it has any that in some way surpass those of the random searcher.

(Remark: The exhaustive searcher doesn't allow + or - at the start of an expression, nor does it allow things like 3*-4. I don't think this changes the set of numbers it can form.)

[EDITED to add:] Exhaustive searcher has found 77505 = 9*8612-3, 99334 = 610+98724, 99664 = 498320/5. Current earliest gaps are 99109, 99590, 99804, 99851, 99853. Searcher is looking at length-9 expressions.

[EDITED to add:] 99109 = 5+76*1304, 99590 = 198*503-4, 99804 = 6/5*83170, 99851 = 5+27*3698, 99853 = 52/4*7681. After all length-9 2-ops expressions have been processed, the earliest gaps are 99854, 100034, 100090, 100189, 100199, 100202.

[EDITED to add:] And after all length-9 expressions have been done, and also length-10 with at most one operator, the earliest gaps are 100090, 101810, 102010, 103910, 108898, 109100. These are all also achievable using length-10 expressions with two operators; with those all done, the first remaining gaps are at 202220, 221740, 331260, 355600, 388990, 399566.

I'll stop posting updates from this now, because M Oehm has written a faster program (not difficult; mine is simple-minded and written in a language that doesn't naturally tend to go fast) and has an actual answer to the question (he should post an answer!). I remark that his answer seems incompatible with one claimed by another brute-force program, as mentioned at the far end of the link at the end of Jan Ivan's answer.

Answer 2

The general consensus here is to throw some computing power at this problem, so I've written a program that creates permutations of all buttons an avaluates tham in calculator style. (All buttons except the equals sign, that is, because that is supposed to be pressed at the end.) Intermediate states of the permutations, i.e. those permutations that are shorter than 14 characters, are considered as well.

In order to cut the number of possibilities short, the following restrictions apply:

• There can't be zeros at the beginning of a number. Because this restrictions is applied when recursing, that also rules out any expressions with the number 0 in them, but that's find: Addition and subtraction of zero do nothing; multiplication results in zero and effectively resets the calculator and division by zero isn't allowed.
• There are no operators at the beginning or at the end of an expression. The only case where this matters is when there is a minus sign at the beginning. We are looking for positive interegs as results and there is no way to et a negative number except by subtraction, which means that we cannot get a positive number from a negative intermediate result by multiplication with or division by another negative number. Because all permutations are explored the expression −x + y can be ignored, because the equivalent y − x will be considered.
• Divisions are only done when the numerator is evenly divisible by the denominator. That means the expression 143 / 2×8 isn't evaluated, because the intermediate result 143 / 2 isn't an integer. This doesn't matter, because the expression 143×8 / 2 will also be generated and evaluates correctly to 572.

With this program, the first numbers that are unaccounted for are:

  2652250, 3855830, 3866656, 3866698, 3919306, 3995545, 3997291

The program {1} is written in C and takes a bit less than half an hour on an older machine. On one of our newer machines here at work, it takes about 10 minutes to run. Parallelising it with OpenMP {2} will reduce the execution time significantly, it is about 1:20 minutes on the new machine with 16 threads.

There is a similar problem on PSE. It allows each of the decimal digits at most once and up to four uses of the operators (+, −, ×, /), but these operators may be repeated.

I've modified my program {3} to allow any operator, but the lowest gap from the most upvoted answer, 8480902, found without considering division, is only in the 12th or 17th place of the numbers I found with that program, depending on whether I allow division or not. My first gaps are:

  6799999, 7175713, 7327237, 8189263, 8248438, 8296789, 8299073

That means the my program may still have errors and that these errors may also be present in the original program for the present problem, because the (possibly) erroneous program is a modification of it. Perhaps the restrictions I explained above are not sound.

On the other hand, that question allows parentheses, which are ruled out by the calculator rules here. So expressions like

  (123 + 4) × (89 - 7)

are allowed, but they cannot be used on the calculator, because there is no means to store the second intermediate result. That difference may explain the different output between my program and the given answer.

I share the code for my programs via pastebin in order not to make this answer too long.

{1} https://pastebin.com/5DwcxLES — this question, sequential
{2} https://pastebin.com/nby6cEWS — this question, parallelised
{3} https://pastebin.com/KKYckiGi — other question, parallelised

Answer 3

very partial only:

1-9 I just write numbers.
10-99 same except 11,22 .. 99
but there is so far always way:
13-2 = 11
23-1 = 22
34-1 = 33
...
98+1 = 99
now it is starting to be harder:
98 + 2 = 100
98 + 3 = 101
102-109, 120, 123-130
108 + 2= 110
108 + 3 = 111
108 + 4,5,6,7 = 112,113,114,115
109 + 7 = 116
120 - 3 = 117
123 - 5 = 118
124 - 5 = 119
aaaand i give up, bet it can go up to:
987 + 13 = 1000.

btw no computer tag or?

most likely less than 8480902
Source
But I still don't see "logical" or easy-to-proof solution except to try 14! possibilities.

Answer 4

Any number of the form $d_1\dots d_k\pm e_1\dots e_l$ where each $d_i,e_i$ are distinct.

For example $75463-1092=74371$.

Similarly, replace the $\pm$ with $\times$ for more results.