Shortest Addition Chain An addition chain is a sequence of integers starting with 1, where every integer other than the initial 1 is a sum of two previous integers.

For instance, here's an addition chain:

[1, 2, 3, 4, 7, 8, 16, 32, 39, 71]


Here are the sums that make it an addition chain:

1 + 1 = 2
1 + 2 = 3
1 + 3 = 4
3 + 4 = 7
1 + 7 = 8
8 + 8 = 16
16 + 16 = 32
7 + 32 = 39
32 + 39 = 71


In this challenge, you will be given a positive integer n, and you must output one of the shortest addition chains which ends in n.

Examples - note that there are many possible outputs, all that you are required to find is an addition chain that's just as short:

1: [1]
2: [1, 2]
3: [1, 2, 3]
4: [1, 2, 4]
5: [1, 2, 3, 5]
6: [1, 2, 3, 6]
7: [1, 2, 3, 4, 7]
11: [1, 2, 3, 4, 7, 11]
15: [1, 2, 3, 5, 10, 15]
19: [1, 2, 3, 4, 8, 11, 19]
29: [1, 2, 3, 4, 7, 11, 18, 29]
47: [1, 2, 3, 4, 7, 10, 20, 27, 47]
71: [1, 2, 3, 4, 7, 8, 16, 32, 39, 71]


Standard I/O rules, etc. Standard Loopholes banned. Code golf: Fewest bytes wins.
Haskell, 57 bytes



c=[1]:[x++[a+b]|x&lt;-c,a&lt;-x,b&lt;-x]
f n=[x|x&lt;-c,last x==n]!!0


A brute force solution.
Try it online!

Explanation

The infinite list c contains all addition chains, ordered by length.
It is defined inductively in terms of itself, by taking a list x from c and two elements from x, and appending their sum to x.
The function f finds the first list in c that ends with the desired number.

c=            -- c is the list of lists
 [1]:         -- containing [1] and
 [x           -- each list x
  ++[a+b]     -- extended with a+b
 |x&lt;-c,       -- where x is drawn from c,
  a&lt;-x,       -- a is drawn from x and
  b&lt;-x]       -- b is drawn from x.
f n=          -- f on input n is:
 [x           -- take list of those lists x
 |x&lt;-c,       -- where x is drawn from c and
  last x==n]  -- x ends with n,
 !!0          -- return its first element.