TOPICS
Search

Wichmann Ruler


A Wichmann ruler is a ruler obtained from one of the Wichmann (1963) constructions below. Its marks lie at integer positions and measure every integer distance up to its length. Such a ruler need not use the minimum possible number of marks, as required of a sparse ruler. Leech (1956) and Wichmann (1963) gave bounds and constructions. Modern computer analyses include Robison (2014) and Pegg (2020), but exact minimum mark counts remain unknown for many lengths.

An example sparse ruler can be given by the marks {0, 1, 2, 3, 27, 32, 36, 40, 44, 48, 52, 55, 58}, with consecutive differences between marks {1, 1, 1, 24, 5, 4, 4, 4, 4, 4, 3, 3}. A difference representation with repeated gaps has a shortened form written as 1^324^15^14^53^2. This notation leads to the major W(r,s) and minor w(r,s) Wichmann constructions, where r and s are nonnegative integers and powers denote repetition of consecutive gaps:

 W(r,s)=1^r,r+1,(2r+1)^r,(4r+3)^s,(2r+2)^(r+1),1^r
 w(r,s)=1^r,r+1,(2r+1)^(r+1),(4r+3)^s,(2r+2)^r,1^r.

The maximal length for a Wichmann ruler with k segments (k+1 marks) is (k^2-(k (mod 6)-3)^2)/3+k for k>=2. For k=2, 3, ..., these have lengths 3, 6, 9, 12, 15, 22, 29, 36, 43, 50, 57, 68, 79, ... (OEIS A289761). An optimal sparse ruler has the greatest length for a given number of marks. Among known greatest lengths, the exceptions to attainment by Wichmann rulers are 1, 13, 17, 23, and 58 (OEIS A349978). This is an existence assertion and does not imply that every optimal sparse ruler is a Wichmann ruler. It is conjectured that for every number of marks greater than 13, a Wichmann ruler attains the greatest possible length (Saarela and Vanhatalo 2024, p. 10).


See also

Dark Satanic Mills on a Cloudy Day, Sparse Ruler

Portions of this entry contributed by Ed Pegg, Jr. (author's link)

Explore with Wolfram|Alpha

References

Leech, J. "On the Representation of 1,2,...,N by Differences." J. London Math. Soc. 31, 160-169, 1956. https://doi.org/10.1112/jlms/s1-31.2.160. Pegg, E. Jr. "Wichmann-Like Rulers." Wolfram Demonstrations Project. 2019. https://demonstrations.wolfram.com/WichmannLikeRulers/. Pegg, E. Jr. "Sparse Rulers." Wolfram Demonstrations Project. 2019. https://demonstrations.wolfram.com/SparseRulers/.Pegg, E. "Hitting All the Marks: Exploring New Bounds for Sparse Rulers and a Wolfram Language Proof." 2020. https://blog.wolfram.com/2020/02/12/hitting-all-the-marks-exploring-new-bounds-for-sparse-rulers-and-a-wolfram-language-proof/. Pegg, E. Jr. "Excess01Ruler." Wolfram Function Repository. https://resources.wolframcloud.com/FunctionRepository/resources/Excess01Ruler/.Robison, A. D. "Parallel Computation of Sparse Rulers." Intel Developer Zone. Jan. 14, 2014. https://web.archive.org/web/20160429004505/http://software.intel.com/articles/parallel-computation-of-sparse-rulers.Saarela, A. and Vanhatalo, A. "A Connection Between Unbordered Partial Words and Sparse Rulers." 29 Aug 2024. https://arxiv.org/abs/2408.16335.Sloane, N. J. A. Sequences A289761, A326499, and A349978 in "The On-Line Encyclopedia of Integer Sequences."Wichmann, B. "A Note on Restricted Difference Bases." J. Lond. Math. Soc. 38, 465-466, 1963. https://doi.org/10.1112/jlms/s1-38.1.465.

Referenced on Wolfram|Alpha

Wichmann Ruler

Cite this as:

Weisstein, Eric W., with contributions by Ed Pegg, Jr.. "Wichmann Ruler." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/WichmannRuler.html

Subject classifications