[RC5] ogr percentage done - WHY impossible?

Arne 'Timwi' Heizmann ajh65 at hermes.cam.ac.uk
Wed Mar 14 15:10:27 EST 2001


Hi,

> Ok, I believe we have all accepted that d.net cannot calculate the
> number of nodes that have to be tested to solve OGR-25 (etc.). But, I
> suppose it is possible to calculate the number of nodes that do exist
> - when I am rigth this is a quite simple calculation (for OGR-3 for
> example, it should be the nodes 1-2-3, 1-3-2, 2-1-3, 2-3-1, 3-1-2,
> 3-2-1, = 6 nodes). When I am right with this interpretation of the
> OGR-description, the total number of nodes seems to be N! for OGR-N
> ... (1,5e25 for OGR 25)

You don't seem to understand what a Goulomb ruler is. A ruler starting
with 1-2-3 is not a Goulomb ruler for a start. The other five you have
listed are equivalent to this one, so they are not Goulomb rulers, either.
The ticks are always listed in ascending order for uniqueness.

There are of course infinitely many Goulomb 3-rulers: 1-2-4, 1-2-5, 1-2-6,
..., 1-2-1004342758, 1-2-1004342759, ... etc. The shortest possible one is
1-2-4.

The reason why d.net has only a finite supply of Goulomb 25-rulers is
because one 25-ruler has already been found and we are only trying to find
a smaller one. For each given stub, you cannot predict how many nodes (of
which there are infinitely many in total) are smaller than our known upper
bound.

Timwi

--
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