# Minimal sparse rulers

A standard ruler of length n has distance marks at positions 0, 1, ..., n (in whichever units). A 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 pq=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.

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.

### 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


# Jelly, 14 bytes

ŒcIQL
‘ŒPÇÐṀḢL


Try it online! (first 15 values here - 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:
L - length                                 4


## Wolfram Language (Mathematica), 65 bytes

Tr[1^#]&@@Cases[Subsets[n=0~Range~#],k_/;Union@@Abs[k-#&/@k]==n]&


Try it online!

# Mathematica, 84 bytes

#&@@(l=Length)/@Select[(S=Subsets)@Range[0,d=#],l@Union[Differences/@S[#,{2}]]==d&]&


Try it online!

# Pyth, 14 bytes

lh.Ml{-M^Z2ySh


Try it here!

# Pyth, 21 19 bytes

hlMf!-SQmaFd.cT2ySh


Try it here!

## 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 for saving a byte for my second approach and inspiring me to golf 3 bytes off my current approach!

• Since the powerset is ordered by length, the first S is unnecessary. – isaacg Nov 26 '17 at 22:12
• @isaacg Thanks! Your great answer (+1) also inspired me to save 3 bytes off my new approach, making it 14 bytes. – Mr. Xcoder Nov 27 '17 at 5:50

# Python 2, 129128 126 bytes

thanks to 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!

output is via exit code

# Husk, 20 18 bytes

λ▼mLfȯ≡⁰u´×≠tṖ⁰)…0


Thanks @H.PWiz for -2 bytes!

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

• oa- is the same as ≠ – H.PWiz Nov 26 '17 at 21:04
• @H.PWiz it really only matters that their lengths are the same, because there can't be any differences outside the [0..N] range. – Martin Ender Nov 26 '17 at 21:20
• You could probably even use ≈. – Martin Ender Nov 26 '17 at 21:20

# Jelly, 17 bytes

‘ŒPµạþFQḊṫ³µÐfḢL


Try it online!

Saved 1 byte thanks to Jonathan Allan!

• The power-set is sorted from shortest to longest so I think ḢL should be OK.. – Jonathan Allan Nov 26 '17 at 23:02

# Pyth, 15 bytes

lhf!-SQ-M^T2yUh


Test suite

## 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


# Jelly, 17 bytes

_þẎQṢw
‘ŒPçÐfRḢL


Try it online!

Borrowed a trick from Mr. Xcoder's answer for -1.
-1 thanks to Jonathan Allan.

• The power-set is sorted from shortest to longest so I think ḢL should be OK.. – Jonathan Allan Nov 26 '17 at 23:02

# Ruby, 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!