On Mon, 12 Mar 2001, Benjamin J. Tilly wrote:
> >(oh, btw. Ben's version takes over 3 times longer. i'm now testing with
> >n=10**30 and using >/dev/null)
> We have a winner.  If you want all of the Hamming numbers less
> than a fixed bound, this appears fastest.

I believe there are faster ways than that, but I don't want to go that
far...

> Theoretically the sort is k*log(k) where k is the number of
> elements.  Practically if you raise n large enough for that to
> matter, you will run out of memory on the machine. :-)

the hamming function, where h(1)=1, is very close to

proc{|k| 0.185*6.9893**(k**(1/3.0)) }

which can be used as a reliable approximation for large values of k
(add 2% for safety)

The size of the returned numbers is approximately s = 1.943*(k**(1/3.0)).
Average comparison is in O(s) time. k*log(k) for the sort assumes O(1)
comparisons. This sort is in O(k**(4/3.0) * log(k)). (well I think so)

The amount of RAM used is in O(k**(4/3.0)). I haven't calculated how much
yours take but it's much less...

> Of course if you just want to know what the thousandth element
> in the Hamming sequence is, I believe that my approach will be
> faster than an approach based on the above.

I believe that too.

> Ditto if you are asked for the first thousand elements.

Given the above approximation of the hamming function, the problem of
computing the sequence up to element number k is equivalent to the one of
computing the sequence up to value h(k). Therefore my solution will be
faster.

matju