Rulers HomeRulez - 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}.
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 | - | - |
Download
The executable Java jar file can be downloaded here. And
here is the source code.
Rulers Home