[RC5] ogr percentage done - WHY impossible?

Stephen Garrison garrison at ChE.UDel.Edu
Wed Mar 14 16:58:55 EST 2001


On Wed, 14 Mar 2001, TimO wrote:
> Actually, because there exist an infinite number of stubs (yes, even
> an infinite number of the 6-stubs we start with), I would say that
> we are 0% done and will remain there until (if) we find a shorter
> 25-node ruler.  We may be performing this test on a 200Ghz laptop.

Actually there can't be an infinite number of stubs. Once we find a valid
ruler (whether or not it is of minimum length makes no difference). It
gives us an upper bound on the length of of the ruler. There is a finite
number of cominations of 25 (for OGR-25) integers that will add up to a
number less than our first ruler's length. An extremely rough estimate of
the maximum number of possibly smaller rulers would be N choose 25
(combinatorics), where N is the length of our current upper bound ruler.
An extremely rough estimate of the max number of stubs would be N choose
6. 

Reasoning: Since N is the length of our initial guess, the maximum length
between any two points on any other ruler would be N (otherwise we would
have a length greater than N and therefore be longer than our initial
guess and could not be the optimal ruler) (and actually I guess you could
reduce the max dist. between pts because every other distance must be
atleast 1 unit long). Picking any number between 1 and N twice would mean
we have two ways of measuring the same distance and we would not have a
golomb ruler. Since I don't remember if order matters in OGR it might
actually be the number of permutations of picking 6 (for the stubs)
numbers out of N numbers. However, this still results in a finite (but
large) number of stubs and rulers.

-- 
Stephen Garrison

--
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest



More information about the rc5 mailing list