Given some positive integer
n, design a protractor with the fewest number of marks that lets you measure all angles that are an integral multiple of
2π/n (each in a single measurement).
As an output, you may output a list of integers in the range
n) that represent the position of each mark. Alternatively you can output a string/list of length
n with a
# at the position of each mark and a
_ (underscore) where there is none. (Or two different characters if more convenient.)
n = 5 you need exactly 3 marks to be able to measure all angles
2π/5, 4π/5, 6π/5, 8π/5, 2π by setting (for example) one mark at
0, one mark at
2π/5 and one mark at
6π/5. We can encode this as a list
[0,1,3] or as a string
Note that the outputs are not necessarily unique.
n: output: 1  2 [0,1] 3 [0,1] 4 [0,1,2] 5 [0,1,2] 6 [0,1,3] 7 [0,1,3] 8 [0,1,2,4] 9 [0,1,3,4] 10 [0,1,3,6] 11 [0,1,3,8] 20 [0,1,2,3,6,10]
PS: This is similar to the sparse ruler problem, but instead of a linear scale (with two ends) we consider a circular (angular) scale.
PPS: This script should compute one example of a set of marks for each
n. Try it online!
PPPS: As @ngn pointed out, this problem is equivalent to finding a minimal difference base of a cyclic group of order
n. The minimal orders are listed in http://oeis.org/A283297 and some theoretical bounds are found in https://arxiv.org/pdf/1702.02631.pdf