稀疏尺(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.