Function Repository Resource:

# Excess01Ruler

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]:=
 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]:=
 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]:=
 Out[22]=

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

 In[23]:=
 Out[23]=

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

 In[24]:=
 Out[24]=

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

 In[25]:=
 Out[25]=

## Version History

• 1.0.0 – 04 November 2019

## 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.