9
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ are we expected to prove it? $\endgroup$ – JMP Apr 4 '17 at 10:18
  • $\begingroup$ The question in Jan Ivan's answer is important: should this have the no-computer tag or not? Because the way I'd approach this if for some reason I actually needed the answer would be: (1) write a program to look for ways to form numbers, and either (2) make it search exhaustively or (3) take candidate "impossible" numbers and try to prove them impossible by hand. $\endgroup$ – Gareth McCaughan Apr 4 '17 at 11:20
  • 2
    $\begingroup$ Oh, what assumptions should we make about non-integer intermediate results? E.g., if we compute (140/3)*9, can we assume the result is exactly 420? If we compute (143/2)*8, can we assume the result is exactly 572? My guess (unless I got the arithmetic wrong) is no and yes, respectively. $\endgroup$ – Gareth McCaughan Apr 4 '17 at 11:22
  • 2
    $\begingroup$ Does the calculator display intermediate results at all? E.g., suppose I enter 1+2=x3-; older/simpler calculators will display 3 when = is pressed, then 9 when - is pressed. Does this calculator have such behaviour, or should we assume that you have to enter a whole expression and then = before it displays anything? $\endgroup$ – Gareth McCaughan Apr 4 '17 at 11:36
  • $\begingroup$ How does overflow work on this calculator? $\endgroup$ – Peter Taylor Apr 5 '17 at 6:34
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 23-8*5167, using calc logic $\endgroup$ – JMP Apr 4 '17 at 12:23
  • $\begingroup$ No, 77505 was in fact an unaccounted-for number. However, @JonMarkPerry, my interpretation of the rules is that we don't use "calc logic" but, I quote, "the usual operator precedence rules". $\endgroup$ – Gareth McCaughan Apr 4 '17 at 12:33
  • $\begingroup$ the UOPR in this case refers to a calculator: 'the calculator is already working well and applies the usual operator precedence rules' $\endgroup$ – JMP Apr 4 '17 at 12:37
  • $\begingroup$ Right. So the calculator won't evaluate 23-8*5167 as 77505. Anyway, I have another random-expression run going and it has clearly found a way to do 77505 (though unfortunately I can't tell you how). The smallest number that could now (for all I know) be unachievable is 78760. Next after that is 88135, then 88259. $\endgroup$ – Gareth McCaughan Apr 4 '17 at 12:48
  • $\begingroup$ Turns out that 78760 = 30*+47256/18 and 88135 = -7140/6+89325 (yeah, both obviously improvable but they happen to be what the program stumbled onto). Next gaps are now 88259, 88349, 99109, 99189. $\endgroup$ – Gareth McCaughan Apr 4 '17 at 12:54
5
$\begingroup$

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 yx 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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I agree that it seems unlikely there's any neat solution to this. My own (slow and stupid) brute-force searcher hasn't got nearly as far as 8480902 yet :-). $\endgroup$ – Gareth McCaughan Apr 4 '17 at 13:50
  • $\begingroup$ It's not $14!$, it's actually $\displaystyle\sum^{13}_{n=0}\frac{14!}{n!}$ because of the possibilities without using all the possible buttons. $\endgroup$ – boboquack Apr 5 '17 at 8:42
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ how does this answer the question? $\endgroup$ – Ivo Beckers Apr 4 '17 at 10:44
  • $\begingroup$ it removes loads of possibilities $\endgroup$ – JMP Apr 4 '17 at 10:44
  • 1
    $\begingroup$ That's the opposite of the answer. $\endgroup$ – boboquack Apr 4 '17 at 10:57
  • $\begingroup$ @boboquack; so is Jan's. we've got to start somewhere otherwise we'll be here forever $\endgroup$ – JMP Apr 4 '17 at 10:59
  • $\begingroup$ I understand that it's a start, but this is almost obvious, IMO. $\endgroup$ – boboquack Apr 4 '17 at 11:02

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.