稀疏尺

稀疏尺（Sparse ruler）指的是去掉了一些刻度的尺子。抽象来说，一个长度为，有个刻度的稀疏尺可以被记为整数序列()。刻度和对应尺子的首尾。为了能够测量长度（），我们需要存在刻度,使得 。

如果一个稀疏尺能够测量不超过它的长度的任意整数长度，称这个稀疏尺是完全的。对于一个完全稀疏尺，如果不存在另一个长度相同但刻度数量更少的完全稀疏尺，则称它是最小稀疏尺。类似的，如果不存在另一个刻度数量相同但长度更大的稀疏尺，则称它是最大稀疏尺。如果一个稀疏尺既是最大稀疏尺，又是最小稀疏尺，则称它是最优稀疏尺。

对于个刻度，不同的刻度组合共有 种，因此这是长度的理论上界。事实上，只有在2、3或4个刻度的情况下可以取到该上界。对于更多的刻度数量，最优长度和理论上界的差距非均匀地逐渐增大。

例如，对于 6 个刻度的稀疏尺，理论上界为 15，但实际上的最大长度为 13。长度为13，刻度数为6的稀疏尺有三种可能的刻度选择。其中之一是是 {0, 1, 2, 6, 10, 13}。例如，要测量7的长度，可以使用这把尺子的刻度6和13。

格伦布尺是一种要求所有的都不相等的稀疏尺。通常，个刻度的格伦布尺将比个刻度的最佳稀疏尺长得多，因为是格伦布尺长度的下界。比较长的格伦布尺可能有间隙，换句话说，它可能有无法测量的距离。例如，最优格伦布尺 {0, 1, 4, 10, 12, 17} 的长度为 17，但它无法测量长度 14 或 15。

 威希曼尺 
许多最优尺符合以下形式：

代表段长度为的间隔。因此，如果， ，则有（按顺序）：

1段长度为1的间隔，

1段长度为2的间隔，

1段长度为3的间隔，

2段长度为7的间隔，

2段长度为4的间隔，

1段长度为1的间隔。

对应稀疏尺 {0, 1, 3, 6, 13, 20, 24, 28, 29}。威希曼尺的长度为，刻度数为 。需要注意的是，并非所有 威希曼尺都是最优稀疏尺，且并非所有最优稀疏尺都可以通过这种方式得到。长度为 1、13、17、23 和 58 的最优稀疏尺均不符合该形式。如果 Peter Luschny 的最优尺猜想为真，则最长的不符合该形式的最优稀疏尺长度为58。目前为止，该猜想在长度为 213以下均被验证为真。 Robison, A. D. Parallel Computation of Sparse Rulers. Intel Developer Zone. https://web.archive.org/web/20210330141047/https://software.intel.com/content/www/us/en/develop/articles/parallel-computation-of-sparse-rulers.html

 渐近分析 

For every  let  be the smallest number of marks for a ruler of length . For example, . The asymptotic of the function  was studied by Erdos, GalErdös, P.; Gál, I. S. On the representation of  by differences. Nederl. Akad. Wetensch., Proc. 51 (1948) 1155--1158 = Indagationes Math. 10, 379--382 (1949) (1948) and continued by LeechLeech, John. On the representation of  by differences. J. London Math. Soc. 31 (1956), 160--169 (1956) who proved that the limit  exists and is lower and upper bounded by 

Much better upper bounds exist for -perfect rulers. Those are subsets  of  such that each positive number  can be written as a difference  for some . For every number  let  be the smallest cardinality of an -perfect ruler. It is clear that . The asymptotics of the sequence  was studied by Redei, RenyiRedei, L.; Ren′i, A. On the representation of the numbers  by means of differences. (Russian) Mat. Sbornik N.S. 24(66), (1949). 385--389. (1949) and then by Leech (1956) and GolayGolay, Marcel J. E. Notes on the representation of  by differences. J. London Math. Soc. (2) 4 (1972), 729--734. (1972). Due to their efforts the following upper and lower bounds were obtained: 

Define the excess as . In 2020, Pegg proved by construction that  ≤ 1 for all lengths .Pegg, E. Hitting All the Marks: Exploring New Bounds for Sparse Rulers and a Wolfram Language Proof. https://blog.wolfram.com/2020/02/12/hitting-all-the-marks-exploring-new-bounds-for-sparse-rulers-and-a-wolfram-language-proof/  If the Optimal Ruler Conjecture is true, then  for all , leading to the ″dark mills″ pattern when arranged in columns, OEIS A326499. None of the best known sparse rulers  are proven minimal as of Sep 2020. Many of the current best known  constructions for  are believed to non-minimal, especially the "cloud" values.

 例子 
以下是一些最小稀疏尺的例子。高亮标出了最优尺。如果要列出的内容太多，则不会全部包含在内。不包括镜像。
长度刻度数数量例子121II231III331II.I442III.I
II.II542III..I
II.I.I641II..I.I756IIII...I
III.I..I
III..I.I
II.I.I.I
II.I..II
II..II.I854III..I..I
II.I...II
II..I.I.I
II...II.I952III...I..I
II..I..I.I10619IIII..I...I11615IIII...I...I1267IIII....I...I
III...I..I..I
II.I.I.....II
II.I...I...II
II..II....I.I
II..I..I..I.I
II.....II.I.I1363III...I...I..I
II..II.....I.I
II....I..I.I.I14765IIIII....I....I15740II.I..I...I...II
II..I..I..I..I.I16716IIII....I...I...I1776IIII....I....I...I
III...I...I...I..I
III.....I...I.I..I
III.....I...I..I.I
II..I.....I.I..I.I
II......I..I.I.I.I188250II..I..I..I..I..I.I198163IIIII....I....I....I20875IIIII.....I....I....I21833IIIII.....I.....I....I2289IIII....I....I....I...I
III.......I....I..I..II
II.I.I........II.....II
II.I..I......I...I...II
II.I.....I.....I...II.I
II..II......I.I.....I.I
II....II..I.......I.I.I
II....I..I......I.I.I.I
II.....II........II.I.I2382III........I...I..I..I.I
II..I.....I.....I.I..I.I249472IIIIII......I.....I.....I259230IIIIII......I......I.....I26983IIIII.....I....I.....I....I27928IIIII.....I.....I.....I....I2896III..........I....I..I..I..II
II.I.I.I..........II.......II
II.I..I..I......I......I...II
II.I.....I.....I.....I...II.I
II.....I...I........I..I.II.I
II.......II..........II.I.I.I2993III...........I...I..I..I..I.I
II.I..I......I......I...I...II
II..I.....I.....I.....I.I..I.I35105III..............I...I..I..I..I..I.I
II.I..I..I......I......I......I...II
II.I..I..I.........I...I......I...II
II..II..........I.I......I.I.....I.I
II..I.....I.....I.....I.....I.I..I.I36101II.I..I......I......I......I...I...II43111II.I..I......I......I......I......I...I...II4612342III..I....I....I..........I.....I.....I.....III50122IIII...................I....I...I...I...I...I..I..I
II.I..I......I......I......I......I......I...I...II571312III..I....I....I..........I..........I.....I.....I.....III
II.I..I......I......I......I......I......I......I...I...II58136IIII.......................I....I...I...I...I...I...I..I..I
III...I.I........I........I........I........I..I......I..II
III.....I......II.........I.........I.........I..I...I.I..I
II.I..I..........I..I......I.......I.........I...I...I...II
II.I..I..........I......I..I..........I......I...I...I...II
II...I..I...I........I........I........I........I....II.I.I68142III..I....I....I..........I..........I..........I.....I.....I.....III
III.....I......II.........I.........I.........I.........I..I...I.I..I79151III..I....I....I..........I..........I..........I..........I.....I.....I.....III90161III..I....I....I..........I..........I..........I..........I..........I.....I.....I.....III101171III..I....I....I..........I..........I..........I..........I..........I..........I.....I.....I.....III112181III..I....I....I..........I..........I..........I..........I..........I..........I..........I.....I.....I.....III123192IIII...I......I......I......I..............I..............I..............I..............I.......I.......I.......I.......IIII
III..I....I....I..........I..........I..........I..........I..........I..........I..........I..........I.....I.....I.....III138201IIII...I......I......I......I..............I..............I..............I..............I..............I.......I.......I.......I.......IIII

 非完全稀疏尺 
有些非完全尺可以完全测量比具有相同标记数量的最优稀疏尺更长的距离。 , ,  ， 和，这些非完全尺最多可以测量 18 个不同的长度，但 7 个刻度的最优稀疏尺最多只能测量 17 个不同长度。

下表列出了一些非完全尺，最多有 13 个刻度。不包括镜像。能够测量的不同长度数量比最优稀疏尺还要多的非完全尺被高亮标出。
刻度数长度可测长度Ruler72418{0, 2, 7, 14, 15, 18, 24}72518{0, 2, 7, 13, 16, 17, 25}73118{0, 5, 7, 13, 16, 17, 31}73118{0, 6, 10, 15, 17, 18, 31}83924{0, 8, 15, 17, 20, 21, 31, 39}106437{0, 7, 22, 27, 28, 31, 39, 41, 57, 64}107337{0, 16, 17, 28, 36, 42, 46, 49, 51, 73}116844{0, 7, 10, 27, 29, 38, 42, 43, 44, 50, 68}119145{0, 18, 19, 22, 31, 42, 48, 56, 58, 63, 91}125351{0, 2, 3, 6, 9, 17, 25, 33, 41, 46, 51, 53}126051{0, 5, 9, 13, 19, 26, 33, 48, 49, 50, 51, 60}127351{0, 2, 3, 10, 17, 23, 35, 42, 46, 47, 51, 73}127551{0, 2, 10, 13, 29, 33, 36, 45, 50, 51, 57, 75}128251{0, 8, 28, 31, 34, 38, 45, 47, 49, 50, 74, 82}128351{0, 2, 10, 24, 25, 29, 36, 42, 45, 73, 75, 83}128551{0, 8, 10, 19, 35, 41, 42, 47, 55, 56, 59, 85}128751{0, 12, 24, 26, 37, 39, 42, 43, 46, 47, 75, 87}136159{0, 2, 3, 6, 9, 17, 25, 33, 41, 49, 54, 59, 61}136959{0, 6, 10, 15, 22, 30, 38, 55, 56, 57, 58, 59, 69}136959{0, 6, 11, 15, 22, 30, 38, 55, 56, 57, 58, 59, 69}138259{0, 4, 5, 9, 25, 27, 39, 42, 50, 53, 56, 63, 82}138359{0, 1, 2, 24, 34, 36, 38, 43, 51, 54, 57, 82, 83}138859{0, 1, 3, 9, 16, 26, 36, 40, 47, 54, 58, 59, 88}138859{0, 1, 5, 29, 34, 36, 47, 48, 50, 56, 58, 73, 88}139059{0, 7, 12, 16, 37, 38, 43, 55, 56, 57, 58, 66, 90}139159{0, 5, 9, 12, 16, 32, 38, 42, 55, 56, 57, 63, 91}139259{0, 6, 10, 13, 25, 34, 39, 54, 55, 56, 57, 65, 92}139459{0, 1, 3, 16, 28, 37, 45, 48, 54, 55, 59, 78, 94}139559{0, 4, 32, 37, 38, 40, 48, 53, 54, 56, 63, 83, 95}139659{0, 3, 7, 27, 37, 39, 50, 55, 56, 58, 72, 81, 96}1310159{0, 4, 24, 37, 43, 45, 52, 54, 55, 59, 77, 81, 101}1310859{0, 8, 17, 40, 50, 53, 64, 65, 69, 71, 91, 99, 108}1311361{0, 6, 22, 36, 45, 47, 57, 60, 64, 65, 91, 97, 113}1313360{0, 26, 29, 40, 42, 46, 67, 74, 79, 89, 97, 98, 133}

参考资料

Category:数论
Category:尺子
Category:组合数学