稀疏尺(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以下均被验证为真。 [1]

渐近分析

已隐藏部分未翻译内容,欢迎参与翻译

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, Gal[2] (1948) and continued by Leech[3] (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, Renyi[4] (1949) and then by Leech (1956) and Golay[5] (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 .[6] If the Optimal Ruler Conjecture is true, then for all , leading to the ″dark mills″ pattern when arranged in columns, OEIS A326499.[7] 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.

例子

以下是一些最小稀疏尺的例子。高亮标出了最优尺。如果要列出的内容太多,则不会全部包含在内。不包括镜像。

长度 刻度数 数量 例子
1 2 1 II
2 3 1 III
3 3 1 II.I
4 4 2 III.I

II.II

5 4 2 III..I

II.I.I

6 4 1 II..I.I
7 5 6 IIII...I

III.I..I III..I.I II.I.I.I II.I..II II..II.I

8 5 4 III..I..I

II.I...II II..I.I.I II...II.I

9 5 2 III...I..I

II..I..I.I

10 6 19 IIII..I...I
11 6 15 IIII...I...I
12 6 7 IIII....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.I

13 6 3 III...I...I..I

II..II.....I.I II....I..I.I.I

14 7 65 IIIII....I....I
15 7 40 II.I..I...I...II

II..I..I..I..I.I

16 7 16 IIII....I...I...I
17 7 6 IIII....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.I

18 8 250 II..I..I..I..I..I.I
19 8 163 IIIII....I....I....I
20 8 75 IIIII.....I....I....I
21 8 33 IIIII.....I.....I....I
22 8 9 IIII....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.I

23 8 2 III........I...I..I..I.I

II..I.....I.....I.I..I.I

24 9 472 IIIIII......I.....I.....I
25 9 230 IIIIII......I......I.....I
26 9 83 IIIII.....I....I.....I....I
27 9 28 IIIII.....I.....I.....I....I
28 9 6 III..........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.I

29 9 3 III...........I...I..I..I..I.I

II.I..I......I......I...I...II II..I.....I.....I.....I.I..I.I

35 10 5 III..............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.I

36 10 1 II.I..I......I......I......I...I...II
43 11 1 II.I..I......I......I......I......I...I...II
46 12 342 III..I....I....I..........I.....I.....I.....III
50 12 2 IIII...................I....I...I...I...I...I..I..I

II.I..I......I......I......I......I......I...I...II

57 13 12 III..I....I....I..........I..........I.....I.....I.....III

II.I..I......I......I......I......I......I......I...I...II

58 13 6 IIII.......................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.I

68 14 2 III..I....I....I..........I..........I..........I.....I.....I.....III

III.....I......II.........I.........I.........I.........I..I...I.I..I

79 15 1 III..I....I....I..........I..........I..........I..........I.....I.....I.....III
90 16 1 III..I....I....I..........I..........I..........I..........I..........I.....I.....I.....III
101 17 1 III..I....I....I..........I..........I..........I..........I..........I..........I.....I.....I.....III
112 18 1 III..I....I....I..........I..........I..........I..........I..........I..........I..........I.....I.....I.....III
123 19 2 IIII...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.....III

138 20 1 IIII...I......I......I......I..............I..............I..............I..............I..............I.......I.......I.......I.......IIII

非完全稀疏尺

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

下表列出了一些非完全尺,最多有 13 个刻度。不包括镜像。能够测量的不同长度数量比最优稀疏尺还要多的非完全尺被高亮标出。

刻度数 长度 可测长度 Ruler
7 24 18 {0, 2, 7, 14, 15, 18, 24}
7 25 18 {0, 2, 7, 13, 16, 17, 25}
7 31 18 {0, 5, 7, 13, 16, 17, 31}
7 31 18 {0, 6, 10, 15, 17, 18, 31}
8 39 24 {0, 8, 15, 17, 20, 21, 31, 39}
10 64 37 {0, 7, 22, 27, 28, 31, 39, 41, 57, 64}
10 73 37 {0, 16, 17, 28, 36, 42, 46, 49, 51, 73}
11 68 44 {0, 7, 10, 27, 29, 38, 42, 43, 44, 50, 68}
11 91 45 {0, 18, 19, 22, 31, 42, 48, 56, 58, 63, 91}
12 53 51 {0, 2, 3, 6, 9, 17, 25, 33, 41, 46, 51, 53}
12 60 51 {0, 5, 9, 13, 19, 26, 33, 48, 49, 50, 51, 60}
12 73 51 {0, 2, 3, 10, 17, 23, 35, 42, 46, 47, 51, 73}
12 75 51 {0, 2, 10, 13, 29, 33, 36, 45, 50, 51, 57, 75}
12 82 51 {0, 8, 28, 31, 34, 38, 45, 47, 49, 50, 74, 82}
12 83 51 {0, 2, 10, 24, 25, 29, 36, 42, 45, 73, 75, 83}
12 85 51 {0, 8, 10, 19, 35, 41, 42, 47, 55, 56, 59, 85}
12 87 51 {0, 12, 24, 26, 37, 39, 42, 43, 46, 47, 75, 87}
13 61 59 {0, 2, 3, 6, 9, 17, 25, 33, 41, 49, 54, 59, 61}
13 69 59 {0, 6, 10, 15, 22, 30, 38, 55, 56, 57, 58, 59, 69}
13 69 59 {0, 6, 11, 15, 22, 30, 38, 55, 56, 57, 58, 59, 69}
13 82 59 {0, 4, 5, 9, 25, 27, 39, 42, 50, 53, 56, 63, 82}
13 83 59 {0, 1, 2, 24, 34, 36, 38, 43, 51, 54, 57, 82, 83}
13 88 59 {0, 1, 3, 9, 16, 26, 36, 40, 47, 54, 58, 59, 88}
13 88 59 {0, 1, 5, 29, 34, 36, 47, 48, 50, 56, 58, 73, 88}
13 90 59 {0, 7, 12, 16, 37, 38, 43, 55, 56, 57, 58, 66, 90}
13 91 59 {0, 5, 9, 12, 16, 32, 38, 42, 55, 56, 57, 63, 91}
13 92 59 {0, 6, 10, 13, 25, 34, 39, 54, 55, 56, 57, 65, 92}
13 94 59 {0, 1, 3, 16, 28, 37, 45, 48, 54, 55, 59, 78, 94}
13 95 59 {0, 4, 32, 37, 38, 40, 48, 53, 54, 56, 63, 83, 95}
13 96 59 {0, 3, 7, 27, 37, 39, 50, 55, 56, 58, 72, 81, 96}
13 101 59 {0, 4, 24, 37, 43, 45, 52, 54, 55, 59, 77, 81, 101}
13 108 59 {0, 8, 17, 40, 50, 53, 64, 65, 69, 71, 91, 99, 108}
13 113 61 {0, 6, 22, 36, 45, 47, 57, 60, 64, 65, 91, 97, 113}
13 133 60 {0, 26, 29, 40, 42, 46, 67, 74, 79, 89, 97, 98, 133}

参考资料

  1. ^ 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
  2. ^ Erdö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)
  3. ^ Leech, John. On the representation of   by differences. J. London Math. Soc. 31 (1956), 160--169
  4. ^ Redei, L.; Ren′i, A. On the representation of the numbers   by means of differences. (Russian) Mat. Sbornik N.S. 24(66), (1949). 385--389.
  5. ^ Golay, Marcel J. E. Notes on the representation of   by differences. J. London Math. Soc. (2) 4 (1972), 729--734.
  6. ^ 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/页面存档备份,存于互联网档案馆
  7. ^ Sloane, N.J.A. (编). Sequence A326499. The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.