10

Prompted by How to make 21?, I wondered what numbers you can form with the allowed numbers and operations.

Generally, what numbers cannot be formed with a combination of 4 given numbers and the operators +, -, *, /?

More specifically, what is the lowest positive integer that cannot be formed with 1, 5, 6, 7 and the operators +, -, *, /. Parentheses are permitted and each number must be used exactly once.

Edit: Note that concatenation is not permitted. e.g. you cannot get 71 via 76-5*1.

Community
  • 1
frodoskywalker
  • 7,369
  • 1
  • 30
  • 49
  • Please also add a condition that combining is not allowed, if you want it to be – skv Nov 06 '14 at 16:48
  • I'm trying to work out how to best answer this (after being pointed out that I misread it originally). I can say "1" because I can't see how to create one but proving that in the answer seems quite tricky... – Chris Nov 06 '14 at 16:52
  • 6
    @Chris: (7+5)/6-1 gives you 1 ;-) – GOTO 0 Nov 06 '14 at 16:53
  • @GOTO0: Well that answers that. I'm still not sure how you can support any answer you give easily... – Chris Nov 06 '14 at 16:56
  • 1
    @skv thanks, it didn't occur to me to point that out, since I enumerated the allowed operators, but I think it may be necessary. – frodoskywalker Nov 06 '14 at 16:59
  • @Chris Certainly, defending any answer you give will be the hard part. – frodoskywalker Nov 06 '14 at 17:00
  • does 15 qualify... I cant think of any easy combination – skv Nov 06 '14 at 17:15
  • From the answer, I think its worth making this question more generic, so that we dont have repeat questions with other combinations of numbers, since we have code now, any number can be substituted there and solutions can be found – skv Nov 06 '14 at 18:38
  • @skv excellent idea, we don't want a rash of "what's the smallest number that can be made with w x y z?" questions... – frodoskywalker Nov 06 '14 at 18:42
  • @skv: I have wondered if writing programs to brute force it spoils it for others. Is there a policy on this? I enjoy things like this for the fun programming challenge but if others would enjoy trying similar things with different sets of numbers I can see how my program could ruin it for everybody... – Chris Nov 06 '14 at 18:44
  • 1
    Yeah, if they see this question and feel like having fun they can substitute other numbers and do it themselves, however this site is primarily aimed at helping people solve things and your solution is probably the easiest way to prove this question, I see no harm – skv Nov 06 '14 at 18:48
  • 1
    @Chris I see no harm, as skv notes anyone can ignore the code and do it themselves. Also, it would be very difficult to prove without brute forcing. – frodoskywalker Nov 06 '14 at 18:52

5 Answers5

14

16 is the lowest. $$\begin{align} 1 &= \frac{5+7}6-1\\ 2 &= \frac6{7+1-5}\\ 3 &= \frac{1\times 6}{7-5}\\ 4 &= (5-1)\times(7-6)\\ 5 &= 5+1+6-7\\ 6 &= \frac{7-1}6 + 5\\ 7 &= 7+6-1-5\\ 8 &= 7+\frac6{1+5}\\ 9 &= 7+6+1-5\\ 10 &= (7-5)\times(6-1)\\ 11 &= (7-5)\times 6-1\\ 12 &= (7-5)\times 6 \times 1\\ 13 &= (7-5)\times 6+1\\ 14 &= (6+1-5)\times 7\\ 15 &= \frac6{\frac75-1} = \frac6{2/5}\\ \end{align} $$

This was done using a computer program to enumerate all possible numbers achievable and then seeing the results.

For extra credit the largest possible is:

252

The algorithm used to do this was as follows:

Starting with four numbers:

Define an operation as having a left and a right number and an operation. We have four possible left numbers and four possible right numbers but we can't choose the same one twice so we have 12 number combinations.

For each of these apply the operator to get a new number. Take the used numbers out of the set and add in the new number. The new number needn't be an integer.

We now have 48 sets of three numbers. Apply the same principle to find the 1152 (not necessarily unique) sets of two numbers that can be made. Repeat until you have the 9216 possible combinations of numbers and operators.

Then from this set eliminate all the undesirables (ie non integer results). Look at list. Profit.

To see the code go look at http://pastebin.com/HEuKHhsv. Its written in C# and designed to run in Linqpad (for ease of coding). Its not written to be readable necessarily but is written verbosely enough to satisfy myself that it is working as intended. :)

Also for interest the ones under 50 that can't be done are:

16
20
25
26
27
33
39
45
49
50

And there are 181 positive numbers under 252 that cannot be made using this method (I hope or something in my program went wrong).

GentlePurpleRain
  • 25,965
  • 6
  • 93
  • 155
Chris
  • 1,825
  • 1
  • 13
  • 18
  • How are you sure it enumerates all possible numbers? – TheRubberDuck Nov 06 '14 at 18:23
  • @EnvisionAndDevelop: I'll describe the algorithm used but it is exhaustive. – Chris Nov 06 '14 at 18:24
  • @Chris could you copy and paste the code? – kaine Nov 06 '14 at 18:29
  • @kaine: Edited post to include pastebin link (I figured 150 lines of code might overwhelm this answer a little). – Chris Nov 06 '14 at 18:37
  • @Chris just curious, how do you make 252? – Vic Nov 06 '14 at 18:44
  • Explained in other comment (5+1)67 – skv Nov 06 '14 at 18:46
  • @vid: I deliberately didn't say that to let people have a crack and likewise why I just listed the one under 50 that couldn't be done, leaving it as an exercise to others if they want to try to get the ones that can be done. – Chris Nov 06 '14 at 18:47
  • 47 is the largest number, this is against the no concatenation. – warspyking Nov 06 '14 at 20:50
  • @warspyking: I'm failing to parse that comment. 47 is the largest number in what sense? What is against the no concatenation? – Chris Nov 06 '14 at 21:33
  • Yes sorry about that, I misunderstood what he was saying. I thought he meant no brackets. – warspyking Nov 06 '14 at 21:38
  • @warspyking: I did wonder if that was the case but I still couldn't work out what 47 is the largest number. Oh, though that looks like the largest you can make with no brackets and no repeats of symbols maybe... Anyway, no worries. :) – Chris Nov 07 '14 at 09:20
  • 1
    FWIW I had a program to do the same thing (different algorithm) which confirms your result. – David Z Nov 07 '14 at 09:45
  • @Chris Apologies for forgetting to accept this answer until now. – frodoskywalker Nov 07 '14 at 23:39
  • @frodoskywalker: not a problem. Its always nice but I did it for the puzzle, not the rep. ;-) – Chris Nov 08 '14 at 13:34
6

I cannot make 15 using these numbers and the given operations.

Adding all numbers gives 19, since we cannot make 15 by taking away 1, one of the other numbers have to be taken away, so addition cannot do it, subtraction wont work with addition either.

If we go to multiplication, then 5 x 3 is the only way to do it, if we take away 5, then 3 cannot be formed with 6 7 and 1, at least thats what I cannot see, so I will leave it here till someone disproves me (there are technical combinations like 6 x 2.5 etc which I cant seem to find a way to achieve)

skv
  • 4,992
  • 4
  • 29
  • 55
5

I just started finding a solution for each one, 15 is the first one I can't come up with a solution. (followed by 16, 20...

ETA (apparently there is a 15 added it in)

(7+5)/6 - 1 = 1

(7+5)/6 * 1 = 2

(7+5)/6 + 1 = 3

(6+5-7) * 1 = 4

(6+5-7) + 1 = 5

((7*5) + 1)/6 = 6

(6+7-5) - 1 = 7

(6+7-5) * 1 = 8

(6+7-5) + 1 = 9

(7-6+1) * 5 = 10

(7-5) * 6 - 1 = 11

(7-5) * 6 * 1 = 12

(7-5) * 6 + 1 = 13

(6-5+1) * 7 = 14

6/((7/5)-1) = 15



(6+7+5) - 1 = 17

(6+7+5) * 1 = 18

(6+7+5) + 1 = 19


6 / (1-(5/7)) = 21

((6*5)-7) - 1 = 22

((6*5)-7) * 1 = 23

((6*5)-7) + 1 = 24

Edited to add in the solution for 21 and 15

Justin
  • 804
  • 7
  • 15
bowlturner
  • 315
  • 2
  • 4
  • 11
  • 2
    21 is definitely possible; that's what this inspired this question. There's a link in the first sentence: http://puzzling.stackexchange.com/questions/3641/how-to-make-21 – TheRubberDuck Nov 06 '14 at 18:18
0

WITHOUT BRACKETS

Without the use of brackets you can make the following numbers:

-37 -36 -29 -28 -23 -22 4 6 8 23 24 29 30 36 37 38 40 41 46 47

All positive integers are:

4 6 8 23 24 29 30 36 37 38 40 41 46 47

So the lowest positive digit without brackets is 1

Anybody interested in all the possible equations that result in integers (there are 252 of them) can look here:

http://pastebin.com/kvNpuDd6

0 is neither positive nor negative, this is why the answer is 1 not 0

**WITH THE USE OF BRACKETS*

Also note I repeated operators here.

Using brackets you can achieve a wider range of numbers, you can achieve 1 through 15 and many more. Too many to cover a list of equations like the pastebin in the without brackets section.

((7+5)/6)-1=1
6/(1-5+7)=2
(6*1)/(7-5)=3
(7-6)(5-1)=4
(5+1+6-7)=5
(7-1)/(6+5)=6
(6+7-5-1)=7
(6/(1+5))+7=8
(6+7+1-5)=9
(6-1)(7-5)=10
(6-1)*(7-5)=11
(6*1)(7-5)=12
(6+1)(7-5)=13
7*(6+1-5)=14
6/((7/5)-1)=15

16 is impossible to achieve like this. You can continue going up until 252, then it becomes impossible to get a higher numbers.

warspyking
  • 14,500
  • 10
  • 78
  • 144
-4

Possibly:

212, since (5 * 6 * 7) + 1 = 211, which seems to me to be the largest number you can make, so one beyond that would be the smallest number you cannot make.

Roger
  • 1,091
  • 7
  • 9