稀疏尺

稀疏尺（Sparse ruler）指的是去掉了一些刻度的尺子。抽象來說，一個長度為${\displaystyle L}$，有${\displaystyle m}$個刻度的稀疏尺可以被記為整數序列${\displaystyle a_{1},a_{2},...,a_{m}}$(${\displaystyle 0=a_{1}<a_{2}<...<a_{m}=L}$)。刻度${\displaystyle a_{1}}$和${\displaystyle a_{m}}$對應尺子的首尾。為了能夠測量長度${\displaystyle K}$（${\displaystyle 0\leq K\leq L}$），我們需要存在刻度${\displaystyle a_{i}}$,${\displaystyle a_{j}}$使得${\displaystyle a_{j}-a_{i}=K}$ 。

如果一個稀疏尺能夠測量不超過它的長度的任意整數長度，稱這個稀疏尺是完全的。對於一個完全稀疏尺，如果不存在另一個長度相同但刻度數量更少的完全稀疏尺，則稱它是最小稀疏尺。類似的，如果不存在另一個刻度數量相同但長度更大的稀疏尺，則稱它是最大稀疏尺。如果一個稀疏尺既是最大稀疏尺，又是最小稀疏尺，則稱它是最優稀疏尺。

對於${\displaystyle m}$個刻度，不同的刻度組合共有${\displaystyle m(m-1)/2}$ 種，因此這是長度${\displaystyle L}$的理論上界。事實上，只有在2、3或4個刻度的情況下可以取到該上界。對於更多的刻度數量，最優長度和理論上界的差距非均勻地逐漸增大。

例如，對於 6 個刻度的稀疏尺，理論上界為 15，但實際上的最大長度為 13。長度為13，刻度數為6的稀疏尺有三種可能的刻度選擇。其中之一是是 {0, 1, 2, 6, 10, 13}。例如，要測量7的長度，可以使用這把尺子的刻度6和13。

格倫布尺是一種要求所有的${\displaystyle a_{j}-a_{i}}$都不相等的稀疏尺。通常，${\displaystyle m}$個刻度的格倫布尺將比${\displaystyle m}$個刻度的最佳稀疏尺長得多，因為${\displaystyle m(m-1)/2}$是格倫布尺長度的下界。比較長的格倫布尺可能有間隙，換句話說，它可能有無法測量的距離。例如，最優格倫布尺 {0, 1, 4, 10, 12, 17} 的長度為 17，但它無法測量長度 14 或 15。

威希曼尺

許多最優尺符合以下形式：

${\displaystyle W(r,s)=1^{r},r+1,(2r+1)^{r},(4r+3)^{s},(2r+2)^{(r+1)},1^{r},}$

${\displaystyle a^{b}}$代表${\displaystyle b}$段長度為${\displaystyle a}$的間隔。因此，如果${\displaystyle r=1}$，${\displaystyle s=2}$ ，則${\displaystyle W(1,2)}$有（按順序）：

1段長度為1的間隔，

1段長度為2的間隔，

1段長度為3的間隔，

2段長度為7的間隔，

2段長度為4的間隔，

1段長度為1的間隔。

對應稀疏尺 {0, 1, 3, 6, 13, 20, 24, 28, 29}。威希曼尺的長度為${\displaystyle 4r(r+s+2)+3(s+1)}$，刻度數為${\displaystyle 4r+s+3}$ 。需要注意的是，並非所有 威希曼尺都是最優稀疏尺，且並非所有最優稀疏尺都可以通過這種方式得到。長度為 1、13、17、23 和 58 的最優稀疏尺均不符合該形式。如果 Peter Luschny 的最優尺猜想為真，則最長的不符合該形式的最優稀疏尺長度為58。目前為止，該猜想在長度為 213以下均被驗證為真。 ^[1]

漸近分析

已隱藏部分未翻譯內容，歡迎參與翻譯。

For every ${\displaystyle n}$ let ${\displaystyle l(n)}$ be the smallest number of marks for a ruler of length ${\displaystyle n}$. For example, ${\displaystyle l(6)=4}$. The asymptotic of the function ${\displaystyle l(n)}$ was studied by Erdos, Gal^[2] (1948) and continued by Leech^[3] (1956) who proved that the limit ${\displaystyle \lim _{n\to \infty }{l(n)^{2}}/n}$ exists and is lower and upper bounded by
${\displaystyle 2+{\tfrac {4}{3\pi }}=2.424...<2.434...=\max _{0<\theta <2\pi }2(1-{\tfrac {\sin(\theta )}{\theta }})\leq \lim _{n\to \infty }{\frac {l(n)^{2}}{n}}\leq {\frac {375}{112}}=3.348...}$

Much better upper bounds exist for ${\displaystyle n}$-perfect rulers. Those are subsets ${\displaystyle A}$ of ${\displaystyle \mathbb {N} }$ such that each positive number ${\displaystyle k\leq n}$ can be written as a difference ${\displaystyle k=a-b}$ for some ${\displaystyle a,b\in A}$. For every number ${\displaystyle n}$ let ${\displaystyle k(n)}$ be the smallest cardinality of an ${\displaystyle n}$-perfect ruler. It is clear that ${\displaystyle k(n)\leq l(n)}$. The asymptotics of the sequence ${\displaystyle k(n)}$ 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:
${\displaystyle \max _{0<\theta <2\pi }2(1-{\tfrac {\sin(\theta )}{\theta }})\leq \lim _{n\to \infty }{\frac {k(n)^{2}}{n}}=\inf _{n\in \mathbb {N} }{\frac {k(n)^{2}}{n}}\leq {\frac {128^{2}}{6166}}=2.6571...<{\frac {8}{3}}.}$

Define the excess as ${\displaystyle E(n)=l(n)-\lceil {\sqrt {3n+{\tfrac {9}{4}}}}\rfloor }$. In 2020, Pegg proved by construction that ${\displaystyle E(n)}$ ≤ 1 for all lengths ${\displaystyle n}$.^[6] If the Optimal Ruler Conjecture is true, then ${\displaystyle E(n)=0|1}$ for all ${\displaystyle n}$, leading to the ″dark mills″ pattern when arranged in columns, OEIS A326499.^[7] None of the best known sparse rulers ${\displaystyle n>213}$ are proven minimal as of Sep 2020. Many of the current best known ${\displaystyle E=1}$ constructions for ${\displaystyle n>213}$ are believed to non-minimal, especially the "cloud" values.

• 
  Fig 1. Light numbers +0, dark numbers +1 for the minimal mark excess pattern in a sparse ruler. All minimal values to length 213 are proven.
• 
  Fig 2. "Dark mills on a cloudy day" -- N. J. A. Sloane. Excess pattern for sparse rulers, best known values for L>213.

例子

以下是一些最小稀疏尺的例子。高亮標出了最優尺。如果要列出的內容太多，則不會全部包含在內。不包括鏡像。

長度	刻度數	數量	例子
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

非完全稀疏尺

有些非完全尺可以完全測量比具有相同標記數量的最優稀疏尺更長的距離。 ${\displaystyle \{0,2,7,14,15,18,24\}}$, ${\displaystyle \{0,2,7,13,16,17,25\}}$, ${\displaystyle \{0,5,7,13,16,17,31\}}$ ， 和${\displaystyle \{0,6,10,15,17,18,31\}}$，這些非完全尺最多可以測量 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 ${\displaystyle 1,2,\cdots ,N}$ by differences. Nederl. Akad. Wetensch., Proc. 51 (1948) 1155--1158 = Indagationes Math. 10, 379--382 (1949)
3. Leech, John. On the representation of ${\displaystyle 1,2,\cdots ,n}$ by differences. J. London Math. Soc. 31 (1956), 160--169
4. Redei, L.; Ren′i, A. On the representation of the numbers ${\displaystyle 1,2,\cdots ,N}$ by means of differences. (Russian) Mat. Sbornik N.S. 24(66), (1949). 385--389.
5. Golay, Marcel J. E. Notes on the representation of ${\displaystyle 1,\,2,\,\ldots ,\,n}$ 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.