Talk:Hamming numbers

I have a list of references to add, plus another one or two Python algorithms. --Paddy3118 18:40, 2 December 2009 (UTC)

Done. --Paddy3118 21:55, 2 December 2009 (UTC)

Off-by-one error?

Since hamming(1692) = 2^31, the last one before 2^31 is hamming(1691). I changed it in the problem description. --Dsnouck 08:56, 3 December 2009 (UTC)

Originally I had the 1691. Tcl had 1690 so I stored all values in an array and found that 1690 was correct. Since I have checked twice, I have reverted your edit, but please check again (as I will tonight). --Paddy3118 09:09, 3 December 2009 (UTC)

I still believe my original remark was correct. I am not going to re-revert. I changed my Scheme program to show some extra output. Maybe some people that submitted other implementations can also check this. We actually do agree on the value of hamming(1690). It's just that this is not the last one before 2^31. Maybe there is something wrong with my implementation. At least we agree on the first 20 :). --Dsnouck 09:22, 3 December 2009 (UTC)

FWIW, calculating with the Tcl impl...

hamming{1690} = 2123366400

hamming{1691} = 2125764000

hamming{1692} = 2147483648

hamming{1693} = 2149908480

My only concern is whether I had an off-by-one error from counting indices from zero or one (i.e., is it H₀ or H₁ that is 1? My impl assumes it is H₁...) –Donal Fellows 10:20, 3 December 2009 (UTC)

So I think it is safe to say that we agree on the value of the 1690th Hamming number. Here it doesn't matter wheter indexing is zero-based or one-based. If we agree that the first Hamming number is 1, it is clear what we mean by the 1690th Hamming number. The only difference between zero-based indexing compared to one-based is that the first Hamming number is called hamming(0) in the former case and hamming(1) in the latter. Similarly for the 1690th Hamming number: with zero-based indexing it is called hamming(1689) as compared to hamming(1690) with one-based indexing. Anyway, to me it still looks like the last Hamming number before 2^31 is the 1691th, since the 1692th Hamming number is equal to 2^31. --Dsnouck 10:48, 3 December 2009 (UTC)

Hence the error is in the task itself. But it's not serious; any implementation that can compute one ought to be able to do the other (and if it can't... well, that's pretty poor). Doing the millionth though, that takes a bit more computation. Especially given that it has 84 digits in decimal notation. –Donal Fellows 11:15, 3 December 2009 (UTC)

Calculations using the Python implementation give: <lang python>>>> # Create a zero-based list of the Hamming numbers >>> h = list(islice(raymonds_hamming(), 1695)) >>> # Show some of the vaules in one-based, (as well as zero based) indexing >>> for i in chain(range(20), range(1689,1693)): print "(i=%4i), n=%4i, h(n)=%10i, (h(n)<2**31) = %s" % (i, i+1, h[i], h[i]<2**31)

(i= 0), n= 1, h(n)= 1, (h(n)<2**31) = True (i= 1), n= 2, h(n)= 2, (h(n)<2**31) = True (i= 2), n= 3, h(n)= 3, (h(n)<2**31) = True (i= 3), n= 4, h(n)= 4, (h(n)<2**31) = True (i= 4), n= 5, h(n)= 5, (h(n)<2**31) = True (i= 5), n= 6, h(n)= 6, (h(n)<2**31) = True (i= 6), n= 7, h(n)= 8, (h(n)<2**31) = True (i= 7), n= 8, h(n)= 9, (h(n)<2**31) = True (i= 8), n= 9, h(n)= 10, (h(n)<2**31) = True (i= 9), n= 10, h(n)= 12, (h(n)<2**31) = True (i= 10), n= 11, h(n)= 15, (h(n)<2**31) = True (i= 11), n= 12, h(n)= 16, (h(n)<2**31) = True (i= 12), n= 13, h(n)= 18, (h(n)<2**31) = True (i= 13), n= 14, h(n)= 20, (h(n)<2**31) = True (i= 14), n= 15, h(n)= 24, (h(n)<2**31) = True (i= 15), n= 16, h(n)= 25, (h(n)<2**31) = True (i= 16), n= 17, h(n)= 27, (h(n)<2**31) = True (i= 17), n= 18, h(n)= 30, (h(n)<2**31) = True (i= 18), n= 19, h(n)= 32, (h(n)<2**31) = True (i= 19), n= 20, h(n)= 36, (h(n)<2**31) = True (i=1689), n=1690, h(n)=2123366400, (h(n)<2**31) = True (i=1690), n=1691, h(n)=2125764000, (h(n)<2**31) = True (i=1691), n=1692, h(n)=2147483648, (h(n)<2**31) = False (i=1692), n=1693, h(n)=2149908480, (h(n)<2**31) = False</lang>

Since we are using 1 based indices for h(n) then the task should use 1691. --Paddy3118 16:39, 3 December 2009 (UTC)

J Solution limitations

There is no indication of how the J solution is used to produce the 1691'st Hamming number or the millionth. (Or if the algorithm used will work for larger values). --Paddy3118 15:05, 5 January 2010 (UTC)

O, I didn't realize this. But the millionth will be a problem. So, should I retreat my solution? --Gaaijz

Hi, No, keep it in. You might want to mention if the millionth is not achieved due to lack of multi-precision integer arithmetic or excessive run-time though. Thanks. --Paddy3118 05:43, 6 January 2010 (UTC)