[seqfan] Re: A true Mac Mahon ruler?

Bob Selcoe rselcoe at entouchonline.net
Thu Jun 27 02:44:32 CEST 2019

Hello Jon, Eric & Seqfans,

Jon said: "the longest known perfect Golomb ruler has length 6."

Is it not proved that 6 is the longest possible perfect Golomb ruler? 
Omitting a few details (and please forgive the informal proof structure):

i.   All such rulers must be of length n = k(k+1)/2 i.e., triangular numbers 
{1,3,6,10,15,21...} with exactly k divisions.
ii.  Distances between divisions (d) must be {1,2,3...k} because if any d>k, 
there would not be enough space for all d <= k.
iii.  Since n is the last division, the first division (f) must be either 1 
or 2.  If f=1, then the ruler contains d = n-2 and not d = n-1; if f=2, then 
the ruler contains d = n-1 and not d = n-2.
iv.  When f=1, d=4 must appear to obtain n-4 because d = {n, n-2, n-4) is 
prohibited;  when f=2, d = n-4 must appear because d={2,4} is prohibited.
v.  Under either of the conditions in iv, distances {n, n-1, n-2, n-3 and 
n-4} have been obtained, and distance n-5 has not.

Obtaining distance n-5:

When f=1:

vi.  To obtain using d=n requires adding d=5 -- prohibited because d=4 
already exists.
vii.  Adding d<=3 or d>n-4 is prohibited due to proximity to other existing 
divisions; adding d = n-5 is prohibited because distance to n-2 = 3 and d = 
{1,4} exists.
viii.  Similar prohibitions apply when trying to obtain distance n-5 when 
ix.  Since n>=10 when k>=4, n-5 cannot be obtained when k>=4; therefore n=6 
is the longest perfect Golomb ruler.

Am I missing something?


From: "Jon Wild" <wild at music.mcgill.ca>
Sent: Tuesday, June 25, 2019 4:21 PM
To: "Sequence Fanatics Discussion list" <seqfan at list.seqfan.eu>
Subject: [seqfan] Re: A true Mac Mahon ruler?

> Hi Eric - is it possible you are thinking of a Golomb ruler instead? A 
> Golomb ruler has the requirement you are interested in, that no distance 
> can be measured in two different ways. Golomb rulers that measure every 
> distance up to n are called *perfect*, and the longest known perfect 
> Golomb ruler has length 6. So you will definitely not find one to measure 
> up to 200!
> A003022 has the list of optimal Golomb rulers.
> Jon
> On Tue, 25 Jun 2019, Éric Angelini wrote:
>> Hello SeqFans, The first 8 terms of A002049 are:
>> 1,3,7,12,20,30,44 and 59.
>> I see that I can measure 29 in two
>> ways with this ruler (I thought only
>> one way was authorized):
>> 30-1=29
>> 59-30=29
>> I am obviously missing smthg as this
>> is an ancient seq. signed by Neil himself.
>> Anyway -- is it possible to build a
>> wooden ruler with as few as possible vertical marks such that all 
>> integers measures between 1 and 200 can
>> be materialized only once?
>> I guess this sort of question is as
>> old as the hat I'm wearing right now to avoid the killer sun we currently 
>> have
>> in Brussels. Forgive me.
>> (and if this seq is already in the OEIS, my shame will
>> be complete).
>> Best,
>> É.
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/
> --
> Seqfan Mailing list - http://list.seqfan.eu/

More information about the SeqFan mailing list