>===== Original Message From Mathieu Bouchard <matju / sympatico.ca> =====
>On Sat, 10 Mar 2001, GOTO Kentaro wrote:
[...]
>Ok, I also had written the following one. How long does it take over
>there? it takes more time to initialize the ruby interpreter, and it takes
>more time to print the numbers than to generate them...
>
>        nums=[]
>        def foo(x,y,n); while y<=n; yield y; y *= x; end; end
>        foo(2,1,n) {|a| foo(3,a,n) {|b| foo(5,b,n) {|c| nums << c }}}
>        nums.sort!
>        for x in nums do p x end
>
>(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.

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. :-)

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.  Ditto if you are
asked for the first thousand elements.

Cheers,
Ben

-------------------------------------------
The Fastest Browser on Earth now for FREE!!
Download Opera 5 for Windows now! Get it at
http://www.opera.com/download/
-------------------------------------------