[r-t] FKM

[Mark Davies]

Mike O writes,

> Talking of which, maybe one of the serious mathematicians out there would
> care to provide an efficient algorithm for determining the number of
> pre-necklaces of length n <= (lexicographically) some given pre-necklace.

I think pabs already sent me something like this. Unfortunately due to my
ignorance I couldn't understand a word of it, let alone code it. :-(

I have an interesting search going at the moment - to start with it looked
very small, but I soon discovered it has a Big Deep Hole in it. The
(inaccurate, but generally useful) % complete measure in SMC32 whizzed up
from 1% to 25.798% in half an hour or so. Then it sat on 25.798% for many
days, before grudgingly clocking over to 25.799%, where it remained for
another couple of weeks. It's still only on 25.808%, and I don't know
whether it will climb out of the Big Deep Hole sometime soon and race 
through to the end, or whether that's it now, it's another ten thousand 
centuries or whatever to completion.

> I did try comparing node counts for at least one other length, but didn't
> get precise agreement.  I even started to wonder about your definition of
> Mnode, but that didn't help - I guess it's 1000000 nodes!

Yes, definitely 1,000,000. I'll investigate this a bit further when I have
time Mike - you are right, the discrepancy is disturbing.

MBD