Function Repository Resource:

ReasonableRuler

Source Notebook

Find a near-minimal set of marks for an integer length ruler so that all smaller integer distances are measurable

Contributed by: Ed Pegg Jr

ResourceFunction["ReasonableRuler"][length]

finds a set of integers with differences giving all values up to length using a compact form.

ResourceFunction["ReasonableRuler"][length,"Full"]

finds a reasonable ruler for given length, showing the full set of values.

Details and Options

The "Full" calculation requires significant memory for large length values.

Examples

Basic Examples (2)

Marks for a sparse ruler of length 57:

In[1]:=

Out[1]=

Check that all differences are covered:

In[2]:=

Out[2]=

Show spaces between marks in a the full form of a length-396 ruler:

In[3]:=

Out[3]=

Split the Difference:

In[4]:=

Out[4]=

Make a series of lists from the compact form of a length-396 ruler:

In[5]:=

Out[5]=

Show the compact form:

In[6]:=

Out[6]=

Verify the above shortened form has length 396:

In[7]:=

Out[7]=

Show the full form for a length-396 ruler:

In[8]:=

Out[8]=

Scope (4)

Count the number of marks on a length-58 ruler:

In[9]:=

Out[9]=

The excess of a ruler with length L and M marks is :

In[10]:=

Out[10]=

A reasonable ruler has an excess of 0 or 1:

In[11]:=

length = 999;
ruler = ResourceFunction["ReasonableRuler"][length];
marks = Total[Last[ruler]] + 1;
excess = marks - Round[Sqrt[3 length + 9/4]];
Column[{{excess, marks, length}, Grid[ruler, Frame -> All]}, Alignment -> Center]

Out[15]=

A list of some rulers with a single mark less than those generated by this function:

In[16]:=

Show the length-999 ruler with one fewer marks:

In[17]:=

ruler = betterRulers[[208]];
length = Dot @@ ruler;
marks = Total[Last[ruler]] + 1;
excess = marks - Round[Sqrt[3 length + 9/4]];
Column[{{excess, marks, length}, Grid[ruler, Frame -> All]}, Alignment -> Center]

Out[21]=

Show how the John Leech upper bound for the number of marks in a complete ruler compares to function-generated rulers:

In[22]:=

Out[22]=

Generate rulers of length n! and plot the number of marks:

In[23]:=

Out[23]=

Options (2)

Show the marks for the first 51 rulers:

In[24]:=

Out[24]=

Show the excess values for the first 51 rulers:

In[25]:=

Out[25]=

Possible Issues (2)

Show the default shortened form for a length-googol ruler:

In[26]:=

Out[26]=

Show the number of marks in a length-googol ruler:

In[27]:=

Out[27]=

Showing the full form of a googol-length ruler isn’t recommended.

Neat Examples (3)

Generate reasonable rulers for various integer powers and calculate their excess:

In[28]:=

$Text@Grid[Flatten[Table[Transpose[Prepend[ Table[{base^ToString[n], Total[ResourceFunction["ReasonableRuler"][base^n][[2]]] + 1 - Round[Sqrt[3 base^n + 9/4]]}, {n, 3, 15}], {"length", "excess"}]], {base, 2, 11}], 1], Dividers -> {True, {{True, False}}}]$

Out[28]=

All rulers to length 213 are minimal. Show a pixel representation of these sparse rulers:

In[29]:=

ArrayPlot[Table[PadRight[ReplacePart[Table[0, {n + 1}],
({# + 1} & /@ ResourceFunction["ReasonableRuler"][n, "Full"]) -> 1], 215], {n, 1, 213}], PixelConstrained -> 2, Frame -> False]

Out[29]=

The maximal length for a given number of marks is usually a Wichmann value:

In[30]:=

$WichmannValues = Table[(n^2 - (Mod[n, 6] - 3)^2)/3 + n, {n, 1, 30}]$

Out[30]=

Arrange lengths in columns ending in Wichmann values and bold the lengths with excess 1:

In[31]:=

Grid[Append[
Transpose[
Table[PadLeft[
Take[Style[
If[Length[ResourceFunction["ReasonableRuler"][#, "Full"]] - Round[Sqrt[3 # + 9/4]] == 1, Style[#, Black, Bold, 16], Style[#, Gray, 14]]] & /@ Range[213],
{WichmannValues[[n]] + 1, WichmannValues[[n + 1]]}], 15, ""], {n, 24 - 1}]], Range[3, 25]], Spacings -> {.2, .2}, Dividers -> {False, -2 -> Blue}]

Out[31]=

Related Links

Version History

1.0.0 – 21 October 2019

Author Notes

No sparse ruler is known with an excess less than 0.

This function has not been tested for values past 20 million.

License Information

This work is licensed under a Creative Commons Attribution 4.0 International License