[Question]
  [
A standard ruler of length *n* has distance marks at positions 0, 1, ..., *n* (in whichever units). A [sparse ruler](https://en.wikipedia.org/wiki/Sparse_ruler) has a subset of those marks. A ruler can measure the distance *k* if it has marks at positions *p* and *q* with *p*−*q*=*k*.
### The challenge
Given a positive integer *n*, output the minimum number of marks required in a sparse ruler of length *n* so that it can measure all distances 1, 2, ..., *n*.
This is [OEIS A046693](https://oeis.org/A046693).
As an example, for input 6 the output is 4. Namely, a ruler with marks at 0, 1, 4, 6 works, as 1−0=1, 6−4=2, 4−1=3, 4−0=4, 6−1=5, and 6−0=6.
### Additional rules
* The algorithm should be valid for arbitrarily large *n*. However, it is acceptable if the program is limited by memory, time or data type restrictions.
* Input/output can be taken/produced by any [reasonable means](https://codegolf.meta.stackexchange.com/questions/2447/default-for-code-golf-input-output-methods).
* [Programs or functions](http://meta.codegolf.stackexchange.com/a/2422/36398) are allowed, in any [programming language](https://codegolf.meta.stackexchange.com/questions/2028/what-are-programming-languages/2073#2073). [Standard loopholes](https://codegolf.meta.stackexchange.com/questions/1061/loopholes-that-are-forbidden-by-default) are forbidden.
* Shortest code in bytes wins.
### Test cases
```
1   ->   2
2   ->   3
3   ->   3
4   ->   4
5   ->   4
6   ->   4
7   ->   5
8   ->   5
9   ->   5
10  ->   6
11  ->   6
12  ->   6
13  ->   6
14  ->   7
15  ->   7
16  ->   7
17  ->   7
18  ->   8
19  ->   8
20  ->   8
21  ->   8
22  ->   8
23  ->   8
24  ->   9
25  ->   9
26  ->   9
27  ->   9
28  ->   9
29  ->   9
30  ->  10
31  ->  10 
32  ->  10
```
  
[Answer]
## [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 65 bytes
```
Tr[1^#]&@@Cases[Subsets[n=0~Range~#],k_/;Union@@Abs[k-#&/@k]==n]&
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78H1CUmVei4KCloPE/pCjaME45Vs3BwTmxOLU4Org0qTi1pDg6z9agLigxLz21TjlWJzte3zo0LzM/z8HBMak4OltXWU3fITvW1jYvVu2/poK@gwJYqYOhyX8A "Wolfram Language (Mathematica) – Try It Online")
[Answer]
# Mathematica, 84 bytes
```
#&@@(l=Length)/@Select[(S=Subsets)@Range[0,d=#],l@Union[Differences/@S[#,{2}]]==d&]&
```
[Try it online!](https://tio.run/##Dcu9CsIwEADghwmEFgL@4Hpwg6ODGJyODDG9tIH0Cs05ic8e/fZvjbrwGrWk2DN0YxGHCjeWWZfxgJ4rJ6XBg3@/Gmsb8RFlZjq6CUxwFZ9SNqFryZl3lsTtn8i4z/kbAsBkg@33vYhiptMl9B8 "Wolfram Language (Mathematica) – Try It Online")
[Answer]
# [Pyth](https://github.com/isaacg1/pyth), 14 bytes
```
lh.Ml{-M^Z2ySh
```
**[Try it here!](https://pyth.herokuapp.com/?code=lh.Ml%7B-M%5EZ2ySh&input=5&test_suite=1&test_suite_input=1%0A2%0A3%0A4%0A5%0A6%0A7%0A8%0A9&debug=0)**
# [Pyth](https://github.com/isaacg1/pyth), ~~21~~ 19 bytes
```
hlMf!-SQmaFd.cT2ySh
```
**[Try it here!](https://pyth.herokuapp.com/?code=hlMf%21-SQmaFd.cT2ySh&input=5&test_suite=1&test_suite_input=1%0A2%0A3%0A4%0A5%0A6%0A7%0A8%0A9&debug=0)**
## How it works
I'll update this after golfing.
```
hSlMfqSQS{maFd.cT2ySh ~ Full program. Q = input.
                   Sh ~ The integer range [1, Q + 1].
                  y   ~ Powerset.
    f                 ~ Filter (uses a variable T).
              .cT2    ~ All two-element combinations of T.
          m           ~ Map.
           aFd        ~ Reduce by absolute difference.
        S{            ~ Deduplicate, sort.
     qSQ              ~ Is equal to the integer range [1, Q]?
  lM                  ~ Map with length.
hS                    ~ Minimum.
```
Thanks to [isaacg](https://codegolf.stackexchange.com/users/20080/isaacg) for saving a byte for my second approach and inspiring me to golf 3 bytes off my current approach!
[Answer]
# [Python 2](https://docs.python.org/2/), ~~129~~ ~~128~~ 126 bytes
*thanks to [totallyhuman](https://codegolf.stackexchange.com/users/68615/totallyhuman) for -1 byte*
```
from itertools import*
r=range(1,input()+2)
[{a-b+1for a in l for b in l}>set(r)>exit(i)for i in r for l in combinations(r,i)]
```
[Try it online!](https://tio.run/##HcoxDsIwDEDRvafwmNAypAsTvQhiSKoULCV25LgSCPXsQen2pP/LV99Mc2ubcAbUKMqcKmAuLHoZ5C6eXtG4Cansauw42@Hx89cwuo0FPCBBgs5w8lhqVCN2iR9Ug7YX7EXOKXWunAOSV2SqRia0z9bc7Q8 "Python 2 – Try It Online")
output is via exit code
[Answer]
# [Husk](https://github.com/barbuz/Husk), ~~20~~ 18 bytes
```
λ▼mLfȯ≡⁰u´×≠tṖ⁰)…0
```
Thanks @H.PWiz for -2 bytes!
[Try it online!](https://tio.run/##AToAxf9odXNr/8K2bVMs4oKB4bij/8674pa8bUxmyK/iiaHigbB1wrTDl@KJoHThuZbigbAp4oCmMP///zEw "Husk – Try It Online")
### Explanation
```
λ               )…0  -- lambda with argument ⁰ as [0..N]
              Ṗ⁰     -- all subsets of [0..N]
             t       -- tail (remove empty subset)
    f(      )        -- filter by following function:
           ≠         --   absolute differences
         ´×          --   of all pairs drawn from itself
        u            --   remove duplicates
      ≡⁰             --   "equal" to [0..N]
  mL                 -- map length
 ▼                   -- minimum
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 17 bytes
```
‘ŒPµạþ`FQḊṫ³µÐfḢL
```
[Try it online!](https://tio.run/##ASwA0/9qZWxsef//4oCYxZJQwrXhuqHDvmBGUeG4iuG5q8KzwrXDkGbhuKJM////NQ "Jelly – Try It Online")
Saved 1 byte thanks to [Jonathan Allan](https://codegolf.stackexchange.com/users/53748/jonathan-allan)!
[Answer]
# Pyth, 15 bytes
```
lhf!-SQ-M^T2yUh
```
[Test suite](https://pyth.herokuapp.com/?code=lhf%21-SQ-M%5ET2yUh&test_suite=1&test_suite_input=1%0A2%0A3%0A4%0A5%0A6%0A7%0A8&debug=0)
## How it works
```
lhf!-SQ-M^T2yUh
             Uh    [0, 1, ... n]
            y      Powerset - all possible rulers
  f                Filer rulers on
         ^T2       All pairs of marks, in both orders
       -M          Differences - (a)
     SQ            [1, ... n], the desired list of differences - (b)
    -              Remove (a) from (b)
   !               Check that there's nothing left.
 h                 The first remaining ruler (powerset is ordered by size)
l                  Length
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 17 bytes
```
_þ`ẎQṢw
‘ŒPçÐfRḢL
```
[Try it online!](https://tio.run/##ASkA1v9qZWxsef//X8O@YOG6jlHhuaJ3CuKAmMWSUMOnw5BmUuG4okz///8xNA "Jelly – Try It Online")
Borrowed a trick from Mr. Xcoder's [answer](https://codegolf.stackexchange.com/a/149146/41024) for -1.  
-1 thanks to [Jonathan Allan](https://codegolf.stackexchange.com/users/53748/jonathan-allan).
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 14 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
ŒcIQL
‘ŒPÇÐṀḢL
```
A monadic link taking and returning non-negative integers.
**[Try it online!](https://tio.run/##ASQA2/9qZWxsef//xZJjSVFMCuKAmMWSUMOHw5DhuYDhuKJM////MTQ "Jelly – Try It Online")** (first 15 values [here](https://tio.run/##ASgA1/9qZWxsef//xZJjSVFMCuKAmMWSUMOHw5DhuYDhuKJM/zE1w4figqz/ "Jelly – Try It Online") - not efficient)
### How?
Finds all the rulers one could make using marks 1 through to n+1 (the power-set of [1,n+1]) ordered by their marking-count, and keeps only those which create maximal measurable distances (the length of the set of differences between all ordered pairs of marks), then returns the length of the first (i.e. [one of] the shortest one[s]).
```
ŒcIQL - Link 1: number of measurable distances: list of numbers, ruler  e.g. [1,2,3,7]
Œc    - all pairs                                [[1,2],[1,3],[1,7],[2,3],[2,7],[3,7]]
  I   - incremental differences                                          [1,2,6,1,5,4]
   Q  - de-duplicate                                                       [1,2,6,5,4]
    L - length                                                                      5
‘ŒPÇÐṀḢL - Main link: number, n              e.g. 4
‘        - increment                              5
 ŒP      - power-set (implicit range of input)   [[],[1],[2],[3],[4],[5],[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[2,5],[3,4],[3,5],[4,5],[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5],[1,2,3,4],[1,2,3,5],[1,2,4,5],[1,3,4,5],[2,3,4,5],[1,2,3,4,5]]
    ÐṀ   - keep those maximal under:
   Ç     -   call the last link (1) as a monad   [[1,2,3,5],[1,2,4,5],[1,3,4,5],[1,2,3,4,5]]
      Ḣ  - head                                  [1,2,3,5]
       L - length                                 4
```
[Answer]
# [Ruby](https://www.ruby-lang.org/), 98 bytes
```
->n{(w=*0..n).find{|x|w.combination(x+1).find{|y|y.product(y).map{|a,b|(b-a).abs}.uniq.size>n}}+1}
```
[Try it online!](https://tio.run/##NcmxDoMgEADQvV/hCFov0l1/pHHgtCQMHlQlihzfTpM2nd7w1oCxmL60AyVx9HUHQBKMpTnxyQdMbkFLereOxNmof0WO4Fc3h2kXUcKifWJ9RxbYagkatwyB7Bs2e70GyrlRufjKPNV4@9L9fKixfAA "Ruby – Try It Online")
]