Shortest Addition Chain

Question

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.

Answer 1

Pyth, 13 bytes

h-DsM^N2/#QyS

Test suite

Gives the lexicographically first shortest chain. It's fairly slow, but not that bad - 19 completes in about 30 seconds using pypy.

Some ideas from @Dennis's solution.

I really like this one - there are a ton of neat tricks involved.

Explanation:

h-DsM^N2/#QyS
h-DsM^N2/#QySQ    Implicit variable introduction
            SQ    Inclusive range, 1 to input.
           y      Subsets - all subsets of the input, sorted by length then lexicographically
                  Only sorted subsets will be generated.
                  Our addition chain will be one of these.
        /#Q       Filter for presence of the input.
  D               Order by
 -                What's left after we remove
     ^N2          All pairs of numbers in the input
   sM             Summed
h                 Output the list that got sorted to the front.

This is still a bit hard to understand, but let me try to explain in a bit more detail.

We start with ySQ, which gives all possible ordered subsets of [1, 2, ... Q], in increasing order of size. The shortest addition chain is definitely one of these, but we need to find it.

The first thing we'll do is filter the list to only keep lists that contain a Q. We do this with /#Q.

Next, we order the list by what's left after we remove the result of a certain function. -D orders by the remainder after removing something.

The thing we remove is sM^N2, where N is the list we're removing things from. ^N2 gives the cartesian product of N with itself, all possible pairs of two elements in N. sM then sums each of the pairs.

What's the smallest possible result, after we do this removal? Well, the smallest element in the input list definitely will remain, because all the numbers are positive, so any sum of two numbers will be greater than the smallest number. And there will be at least one number, because we checked that the input was present in the list. Therefore, the smallest possible result will be when every number except the smallest number is the sum of two other numbers in the list, and the smallest number in the list is 1. In this case, the sorting key will be [1]. These requirements mean that the list must be an addition chain.

So, we sort the addition chains to the front. Remember that y gives its subsets in increasing order of size, so the list which is sorted to the front must be one of the shortest addition chains. h selects that list.

Answer 2

Haskell, 57 bytes

c=[1]:[x++[a+b]|x<-c,a<-x,b<-x]
f n=[x|x<-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<-c,       -- where x is drawn from c,
  a<-x,       -- a is drawn from x and
  b<-x]       -- b is drawn from x.
f n=          -- f on input n is:
 [x           -- take list of those lists x
 |x<-c,       -- where x is drawn from c and
  last x==n]  -- x ends with n,
 !!0          -- return its first element.

Answer 3

Brachylog, 14 bytes

∧≜;1{j⊇Ċ+}ᵃ⁽?∋

Try it online!

A brute-force submission that builds all possible addition chains using iterative deepening, stopping when a chain containing its right argument is found. Unlike most Brachylog submissions, this is a function submission that inputs via its right argument (conventionally called the Output) and outputs via its left argument (conventionally called the Input); doing this is somewhat controversial, but the highest-voted meta answer on the subject says it's legal (and doing so is consistent with our normal I/O defaults for functions). If we used the input and output in a more conventional way, this would be 16 bytes (∧≜;1{j⊇Ċ+}ᵃ⁽.∋?∧), because the right-hand side of the program would not be able to make use of the implicit constraint (thus would need that disabled, and a new explicit constraint given, at a cost of 2 bytes).

Explanation

∧≜;1{j⊇Ċ+}ᵃ⁽?∋
∧               Disable implicit constraint to read the left argument
 ≜;        ⁽    Evaluation order hint: minimize number of iterations
    {    }ᵃ     Repeatedly run the following:
   1      ᵃ       From {1 on the first iteration, results seen so far otherwise}
     j            Make {two} copies of each list element
      ⊇           Find a subset of the elements
       Ċ          which has size 2
        +         and which sums to {the new result for the next iteration}
             ∋    If the list of results seen so far contains {the right argument}
            ?     Output it via the left argument {then terminate}

An interesting subtlety here is what happens on the first iteration, where the input is a number rather than a list like on the other iterations; we start with the number 1, make two copies of every digit (making the number 11), then find a 2-digit subsequence of it (also the number 11). Then we take its digit sum, which is 2, and as such the sequence starts [1,2] like we want. On future iterations, we're starting with a list like [1,2], doubling it to [1,2,1,2], then taking a two-element subsequence ([1,1], [1,2], [2,1], or [2,2]); clearly, the sums of each of these will be valid next elements of the addition chain.

It's a little frustrating here that the evaluation order hint is needed here, especially the ≜ component (it appears that ᵃ takes its evaluation order hint from inside rather than outside by default, thus the rather crude use of ≜ in order to force the issue).

Answer 4

PHP, 195 Bytes

function p($a){global$argn,$r;if(!$r||$a<$r)if(end($a)==$argn)$r=$a;else foreach($a as$x)foreach($a as$y)in_array($w=$x+$y,$a)||$w>$argn||$w<=max($a)?:p(array_merge($a,[$w]));}p([1]);print_r($r);

Try it online!

Answer 5

JavaScript (ES6), 83 86 bytes

Edit: fixed to output the list in non-reverse order

n=>(g=(s,a=[1])=>s-n?s>n||a.map(v=>g(v+=s,a.concat(v))):r=1/r|r[a.length]?a:r)(r=1)&&r

Demo

let f =

n=>(g=(s,a=[1])=>s-n?s>n||a.map(v=>g(v+=s,a.concat(v))):r=1/r|r[a.length]?a:r)(r=1)&&r

for(n = 1; n <= 15; n++) {
  console.log(n, '-->', JSON.stringify(f(n)));
}

Answer 6

Jelly, 17 bytes

’ŒP;€µ+þ;1Fḟ@µÐḟḢ

Outputs the lexicographically first solution in exponential time.

Try it online!

How it works

’ŒP;€µ+þ;1Fḟ@µÐḟḢ  Main link. Argument: n (integer)

’                  Decrement; n-1.
 ŒP                Powerset; generate all subarrays of [1, ..., n-1], sorted first
                   by length, then lexicographically.
   ;€              Append n to all generate subarrays.
     µ       µÐḟ   Filterfalse; keep only subarrays for which the chain between the
                   two chain separators (µ) returns a falsy value.
     µ             Monadic chain. Argument: A (array of integers)
      +þ               Add table; compute the sums of all pairs of elements in x,
                       grouping the results by the right addend.
        ;1             Append 1 to the resulting 2D array.
          F            Flatten the result.
           ḟ@          Filterfalse swapped; remove all elements of A that appear in
                       the result. This yields an empty list for addition chains.
                Ḣ  Head; select the first result.

Answer 7

Mathematica, 140 bytes

t={};s={1};(Do[While[Last@s!=#,s={1};While[Last@s<#,AppendTo[s,RandomChoice@s+Last@s]]];t~AppendTo~s;s={1},10^4];First@SortBy[t,Length@#&])&

.

produces a different shortest addition chain everytime you run it

Try it online
paste the code with ctrl+v, place input i.e [71] at the end of the code and press shift+enter