You start with the number 1. You can create a new number by applying an operation on two existing numbers (can be the same). The operations are +, - and *. What is the fewest number of steps needed to reach the number 2020? Bonus question: can you find multiple solutions?
Good luck!
7 is the minimum number of operations
This should be all of the shortest length solutions, some of these have already been answered, and I'll leave credit to those that found them.
I'm also including the brute force python code that I used to exhaust all the combinations. That's how I was able to arrive at the the answer to the minimum length to be what it is.
Found first by @hexomino
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
5 * 3 = 15
15 * 3 = 45
45 * 45 = 2025
2025 - 5 = 2020
1 + 1 = 2
2 + 2 = 4
4 + 1 = 5
5 + 4 = 9
9 * 5 = 45
45 * 45 = 2025
2025 - 5 = 2020
First found by @Jens
1 + 1 = 2
2 + 2 = 4
4 + 1 = 5
5 * 4 = 20
20 * 5 = 100
100 + 1 = 101
101 * 20 = 2020
Found first by @Benoit Esnard
1 + 1 = 2
2 + 2 = 4
4 + 1 = 5
5 * 4 = 20
20 * 5 = 100
100 * 20 = 2000
2000 + 20 = 2020
1 + 1 = 2
2 + 2 = 4
4 + 1 = 5
5 * 4 = 20
20 * 20 = 400
400 + 4 = 404
404 * 5 = 2020
First found by @hexomino
1 + 1 = 2
2 + 2 = 4
4 + 1 = 5
5 * 4 = 20
20 * 20 = 400
400 * 5 = 2000
2000 + 20 = 2020
First found by @sudhackar
1 + 1 = 2
2 * 2 = 4
4 + 1 = 5
5 + 4 = 9
9 * 5 = 45
45 * 45 = 2025
2025 - 5 = 2020
1 + 1 = 2
2 * 2 = 4
4 + 1 = 5
5 * 4 = 20
20 * 5 = 100
100 + 1 = 101
101 * 20 = 2020
First found by @Teejay
1 + 1 = 2
2 * 2 = 4
4 + 1 = 5
5 * 4 = 20
20 * 5 = 100
100 * 20 = 2000
2000 + 20 = 2020
1 + 1 = 2
2 * 2 = 4
4 + 1 = 5
5 * 4 = 20
20 * 20 = 400
400 + 4 = 404
404 * 5 = 2020
1 + 1 = 2
2 * 2 = 4
4 + 1 = 5
5 * 4 = 20
20 * 20 = 400
400 * 5 = 2000
2000 + 20 = 2020
def mdFormat(nums, ops, ans, sol_no):
#Formatting the solutions for markdown
subheader="Solution %s"%sol_no
subheader_lines='-'*len(subheader)
steps = []
val = nums[0]
ans = ans[1:]
for i, num in enumerate(nums[1:]):
steps.append('>! %s %s %s = %s <br>'%(val, ops[i], num, ans[i]))
val = ans[i]
s = [subheader, subheader_lines]
s.extend(steps)
s.append('\n')
return '\n'.join(s)
def apply_operations(numbers, operations):
#Gives us the new list of number choices
if len(numbers) == 1:
return [numbers[0]]
n_seq = (numbers[0], )
n = numbers[0]
for i, num in enumerate(numbers[1:]):
if operations[i] == '+':
n += num
elif operations[i] == '-':
n -= num
elif operations[i] == '*':
n *= num
n_seq += (n, )
return n_seq
solutions_found = 0
def search_n_operations(n, last_numbers=(1,), last_operations=None, choices=(1, )):
global solutions_found
if n == 0: #we're done with the recursion
return
if last_operations is None:
op_combos = (next_op for next_op in ('+', '-', '*'))
else:
op_combos = (last_operations + (next_op,) for next_op in ('+', '-', '*'))
for operation_seq in op_combos:
num_combos = (last_numbers + (next_val,) for next_val in set(choices))
for number_seq in num_combos:
new_choices = apply_operations(number_seq, operation_seq)
if new_choices[-1] == 2020: #This is an answer!
solutions_found += 1
print mdFormat(number_seq, operation_seq, new_choices, solutions_found)
if last_operations is None:
operation_seq = (operation_seq, )
search_n_operations(n - 1, number_seq, operation_seq, new_choices)
n = 10
search_n_operations(n)
print "A total of %s solutions were found for %s operations"%(solutions_found, n)
Varying the n should illustrate where the minimum bound is.
Outputs for n < 7:
A total of 0 solutions were found for 1 operations
A total of 0 solutions were found for 2 operations
A total of 0 solutions were found for 3 operations
A total of 0 solutions were found for 4 operations
A total of 0 solutions were found for 5 operations
A total of 0 solutions were found for 6 operations
I can do it in 7 steps:
1+1 (2)
2*2 (4)
4+1 (5)
4*5 (20)
20*5 (100)
100+1 (101)
20*101 (2020)
Another solution (changing the last 2 steps):
20*100 (2000)
2000+20 (2020)
Here are a couple of essentially different ways to do it in
$7$ steps
Solution 1
$1+1 = 2$
$1+2 = 3$
$2+3 = 5$
$3 \times 5 = 15$
$3 \times 15 = 45$
$45 \times 45 = 2025$
$2025 - 5 = 2020$
Solution 2
$1+1 = 2$
$2+2 = 4$
$4+1 = 5$
$4 \times 5 = 20$
$20 \times 20 = 400$
$5 \times 400 = 2000$
$2000 + 20 = 2020$
Another solution for
7 steps
Last steps essentially same as @hexonimo, missed by 4 minutes
1+1 = 2
2+2 = 4
4+1 = 5
5+4 = 9
9*5 = 45
45*45 = 2025
2025-5 = 2020
Jay's answer can be improved to 8 in another way
1+1 = 2
2*2 = 4
4*4 = 16
16*2= 32
32*2 = 64
64*32 = 2048
32-4 = 28
2048-28 = 2020
In addition to Jens's, hexomino's and sudhackar's solutions:
$1 + 1 = 2$
$2 + 2 = 4$
$4 + 1 = 5$
$4 \times 5 = 20$
$20 \times 20 = 400$
$400 + 4 = 404$
$404 \times 5 = 2020$
I can do it in 9 steps, and there are multiple solutions.
Example,
1 + 1 (2)
2 * 2 (4)
4 * 4 (16)
16 * 16 (256)
4 + 4 (8)
256 * 8 (2048)
8 - 1 (7)
7 * 4 (28)
2048 - 28 (2020)
or,
1 + 1 (2)
2 + 2 (4)
4 + 4 (8)
8 * 8 (32)
32 * 2 (64)
64 * 32 (2048)
16 + 4 (20)
20 + 8 (28)
2048 - 28 (2020)
PARTIAL. Following the idea of @Engineer Toast, let us concentrate on the optimality part (which is actually the essence of the question: see "fewest").
The lower bound is 6. It's easy to see that the highest obtainable numbers are in decreasing order: 256,81,64,36 after the 4th step. We can't use addition as the 5th operation, nor multiplying since 2020 is not divisble by these numbers, and 36 should be multiplyed again with a higher number than itself. So the remaining question: is 6 operations possible, or not.
Jay's idea can be done slightly more efficiently in 8 steps:
$1 + 1 = 2$
$2 + 2 = 4$
$4 + 4 = 8$
$8 \times 4 = 32$
$32 \times 2 = 64$
$64 \times 32 = 2048$
$2048 - 32 = 2016$
$2016 + 4 = 2020$
7 steps:
$1+1 = 2$
$2\times2 = 4$
$1+4 = 5$
$4\times5 = 20$
$20\times20 = 400$
$400\times5 = 2000$
$2000+20 = 2020$
The one above was already posted. This one should be new:
$1+1 = 2$
$2\times2 = 4$
$1+4 = 5$
$4\times5 = 20$
$5\times20 = 100$
$20\times100 = 2000$
$2000+20 = 2020$
2*2 instead of 2+2 but they are basically the same :)
$\endgroup$
1+1=2
2^2=4
2*4=8
4^4=256
256-4=252
252*8=2016
2016+4=2020
1. Where would these "existing numbers" come from? $\endgroup$