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 H0 or H1 that is 1? My impl assumes it is H1...) –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)
- 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)