[math-fun] Sparse rulers proof
TLDR version: ||||.......................|....|...|...|...|...|...|..|..| Sparse rulers allow the measuring of all distances up to length n (58) with a minimal number of marks M (13). The author believes B. Wichmann almost completely solved the problem in 1963. From Wichmann's sparse ruler recipe, M_n - ⌈√(3 n+9/4)⌋ can be shown to usually be 0 or 1 (the excess). The length 58 ruler at the start of this paragraph is conjectured to be the longest sparse ruler with fewer marks than a Wichmann construction, but no proof is known. Adding a single mark to the end of Wichmann's construction allows the building of excess-01 rulers for all lengths over 257992. The author's code found solutions for hundreds of difficult smaller lengths such as 1792, 5657 and 16617 to establish that excess-01 rulers always exist. The optimality of excess 1 solutions for lengths 474, 501, 582, 609, 669, 792, 793, ... may be doubtful since they break the excess pattern. The OEIS version is https://oeis.org/A326499 https://blog.wolfram.com/2020/02/12/hitting-all-the-marks-exploring-new-boun... --Ed Pegg Jr
participants (1)
-
ed pegg