Function Repository Resource:

Excess01Ruler

Source Notebook

Find a near-minimal set of integer marks so that all integers up to a given length are represented as differences

Contributed by: Ed Pegg Jr

ResourceFunction["Excess01Ruler"][length]

finds a set of integers representing all differences up to length using a compact form for the result.

ResourceFunction["Excess01Ruler"][length,"Full"]

finds a set of integers representing all differences up to length.

Details and Options

An integer length ruler with marks so that all integer differences up to the length are represented is called a complete ruler.

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

For any positive integer length, a complete ruler with excess 0 or 1 can be made, hence these are called excess-01 rulers.

There are no known complete rulers with an excess of -1.

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

Examples

Basic Examples (3)

Find the marks for a sparse ruler of length 9:

In[1]:=

Out[1]=

Check that all differences are covered:

In[2]:=

Out[2]=

Find the marks for a sparse ruler of length 57:

In[3]:=

Out[3]=

Check that the ruler is complete, i.e. that all differences are covered:

In[4]:=

Out[4]=

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

In[5]:=

Out[5]=

Split the differences:

In[6]:=

Out[6]=

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

In[7]:=

Out[7]=

Show the compact form:

In[8]:=

Out[8]=

Verify that the compact form from the previous result has length 396:

In[9]:=

Out[9]=

Show the full form for a length-396 ruler:

In[10]:=

Out[10]=

Scope (6)

Show the marks for the first 51 rulers:

In[11]:=

Out[11]=

Show the excess values for the first 51 rulers:

In[12]:=

Out[12]=

Count the number of marks for a length-58 ruler in full form or compact form:

In[13]:=

Out[13]=

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

In[14]:=

Out[14]=

An excess-01 ruler has an excess of 0 or 1:

In[15]:=

length = 999;
ruler = ResourceFunction["Excess01Ruler"][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 less mark:

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[17]=

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

In[18]:=

Out[18]=

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

In[19]:=

Out[19]=

Possible Issues (2)

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

In[20]:=

Out[20]=

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

In[21]:=

Out[21]=

Showing the full form of a googol-length ruler is not recommended.

Neat Examples (3)

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

In[22]:=

$Text@Grid[Flatten[Table[Transpose[Prepend[ Table[{base^ToString[n], Total[ResourceFunction["Excess01Ruler"][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[22]=

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

In[23]:=

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

Out[23]=

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

In[24]:=

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

Out[24]=

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

In[25]:=

Grid[Append[
Transpose[
Table[PadLeft[
Take[Style[
If[Length[ResourceFunction["Excess01Ruler"][#, "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[25]=

Version History

1.0.0 – 04 November 2019

Related Resources

Author Notes

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

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

License Information

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

Wolfram Function Repository

Excess01Ruler

Details and Options