johnf@apollo.uucp (John Francis) (01/18/86)
~~~~~~~~~~~~~~ This Line Intentionally Left Blank ~~~~~~~~~~~~~~~~
Has anyone else out there done any investigation of Golomb Rulers ?
(Briefly, a Golomb Ruler is a ruler of integral length, with marks
at integral intervals such that the distances between any pair of
marks are all different. See the computer recreations section of
the December issue of Scientific American for more details).
I can add the following information to that which is given there:
The lower bound for rulers with 14 marks is 127.
The lower bound for rulers with 15 marks is at least 137.
Both of these values come from an exhaustive search program I wrote
(which is still running). It took twenty hours (on an Apollo DSP160,
which is about a VAX11/780 equivalent) to verify the results given
for rulers of up to 13 marks. I am quite proud of this program, as
the Scientific American article mentioned that the program that was
run to verify that 106 was the lower bound for rulers with 13 marks
took a MONTH of CPU time! However, I would still like to improve
the running time of the program, as the search time gets longer and
longer as the rulers increase in length (for example, it took 41
hours to verify that there were no rulers of length 136 with 15 marks).
In the article mention is made of a formula that gives a lower bound
for the length of a ruler with M marks, but the formula is not given.
[The values quoted for the lower bound for rulers with 14 to 24 marks
are 114,133,154,177,201,227,254,283,314,346 and 380]. If anyone out
there knows what the formula is (and how it is derived) I would like
to hear from them, as a good lower bound formula would enable me to
reduce the running time of the program considerably!
Another snippet of information: If I have a ruler of length L that
has M marks, I can obviously get rulers of length L with any number
of marks less tham M (just delete some of the marks). It is usually
true that if I can find a ruler of length L with M marks then I can
also find rulers of length L+n with M marks for all positive values
of n. So far I have found the following exceptions to this rule:
Marks Minimum L Exceptions
0 - 9 NONE
10 55 56 57
11 72 73
12 85 86 87 88 89
13 106 107 108
14 127 NONE
Hypothesis 1: There exists some value of M, above which there will be
no exception cases.
Hypothesis 2: For arbitrary M there is some function of M which gives
a minimum value of n above which there are no exceptions,
and which is of magnitude o(M). [Little-O, for those of
you reading this on upper-case-only terminals].
Can anybody prove (or disprove) these hypotheses?jr@bbncc5.UUCP (John Robinson) (01/27/86)
Date: Mon, 27 Jan 86 9:52:18 EST From: Ken Sedgwick <ksedgwic@BBN-VAX.ARPA> To: crowther@BBNA.ARPA, goodhue@BBNA.ARPA, beeler@BBNA.ARPA, tene@BBNA.ARPA, milliken@BBNA.ARPA, dm@BBNA.ARPA, tblackadar@BBNA.ARPA, nblase@BBNA.ARPA Subject: Length 14 Exhausted! The shortest ruler with 14 marks has been found by titan. The run lasted 30 hours on 79 processors. -> 5 28 38 41 49 50 68 75 92 107 121 123 127 Ken Sedgwick Titan is a BBN Butterfly multiprocessor, with 128 MC68000 processors. I don't know why Ken used only 79. I believe it found the 13-mark solution in about 20 minutes. /jr
kmw@siemens.UUCP (01/28/86)
Yes, I have done a little investigation of golomb rulers.
I would like to reply to johnf by e-mail, but my unix system
cannot figure out his address ("<2b6665b2" ??).
johnf, please post your address or reply to me.
Klaus Winkelmann, princeton!siemens!kmw, (609)734-3355.