## The Ruler-Workbench

Rulez - a program for the fast generation
of perfect and optimal rulers.

Purpose

Generating all perfect or optimal rulers of given length.

A ruler is a strict increasing finite sequence of marks. Rulers are counted with regard to their length L and the number of marks M (or segments S, which is the space between two adjacent marks). Rulers are:

(a) COMPLETE, if all distances d with 1 <= d <= L can be measured with the ruler.

(b) PERFECT,   if there is no complete ruler with the same length which possesses fewer marks.

(c) OPTIMAL,   if there is no perfect ruler with the same number of marks which has a greater length.

Syntax

function(from, to, options) like a function-call with three arguments. function is one out of {perfect, optimal, single}.

• perfect -> generate all perfect rulers with length L
constrained by 1 <= from <= L <= to.

• single -> generate only one perfect ruler with length L
constrained by 1 <= from <= L <= to.

• optimal -> generate all optimal rulers with S segments
constrained by 1 <= from <= S <= to.

Range

The first and the second argument of the calling list indicate the range of the computation. from is the low bound and to is the high bound of the range.

Output-Options

 m Marks: save rulers as a sequence of marks. If two different rulers are mirror-symmetric both will be counted, but only one will be saved. Example [0,1,4,10,16,18,21,23] d Distance: save rulers as distances between marks Example <1,3,6,6,2,3,2>. b Binary: save rulers in binary (symbolic) form. Example ||--|-----|-----|-|--|-|. t Type: save the type of the rulers Example |2^2|3^2|5^2|6^2|17^2|. f Difference: save the difference table of the rulers. c Card: count and display only the number of rulers.

All the above options can be combined in a single string, in other words, options are any substrings of "bcdfmt". However, the option 'c' overrides all other options.

Sample Use

All commands are prefixed by: java -jar ruler.jar

 perfect(23, 44, bd) Will generate all perfect rulers with length 23 <= L <= 44. The rulers will be represented as a list of markers and in symbolic form. Both the ruler and its mirror-symmetric counterpart will be displayed. single(1, 80, b) Will generate a single ruler for each length up to 80 in symbolic form. As a result a nice 'pyramid of rulers' will be created. optimal(1, 14, c) Will generate all optimal rulers, which have 1 <= S <= 14 segments. Only the number of these rulers will be displayed, no rulers will be saved. (A103303 on OEIS) optimal(12, 12, mdbtf) Will generate all optimal rulers with 12 segments. All representations of these rulers will be given.

File

Rulers will be saved to the file 'rulers.txt'.
Subsequent calls append to this file.

Requirement

You need either the Java 2 Standard Edition or the J2SE Development Kit (JDK), version 1.6 or later. Both can be downloaded here: JAVA. We recommend the JDK because it includes the 'server' JVM, which is better suited to our program.

Installation

Windows users might find it convenient to place a batch-file named 'ruler.bat' in the same directory as 'ruler.jar' containing

%javahome%java -jar ruler.jar %1
If you have the JDK installed, then better use
%javahome%java -server -jar ruler.jar %1

Here %javahome% has to be replaced with the appropriate path on your system, for example  'C:\ ProgramFiles\ Java\ jre1.6.0\ bin\'. Open first a console for the command-processor and than type, for example: ruler perfect(1, 50, mb).

Benchmark

On a PC vintage 2005, Java Runtime Environment version 1.6.0_13, a total of 136495 perfect rulers with lengths 1..101 were generated in 6300 seconds = 7/4 hour. Hugo Pfoertner computed with this program the lengths 1..101 in 3221 seconds while some other memory-intensive thread was running (Processor: Intel(R) Core(TM)2 Quad CPU Q9550 @ 2.83GHz, Cores: 4).

 segment 11 12 13 14 15 16 17 18 seconds 1 4 38 198 975 5084 - -