Hamming numbers are defined as numbers whose only prime factors are 2, 3, and 5.
arithmetic/hamming.numbers
Problem
Hamming numbers are defined as numbers whose only prime factors are 2, 3, and 5. For example, the first ten Hamming numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12. Estimate the size of the nth Hamming number.
Show solution
[ Editor: the only follow-up gives tables of the first 100 numbers of
the forms 2^i 3^j 5^k, 2^i 3^j and 2^i 3^j 5^k 7^l, from which the
growth can be estimated; they are reproduced below with the columns
narrowed. The Fortran program that produced them is omitted. ]
With some modifications this code can find in ascending order all
numbers of the form
i j k l
H(n) = 2 3 5 7...
(of course within the range of machine's capabilities).
-- Valentin <fs300342@sol.yorku.ca>
i j k
H(n) = 2 3 5
-------------------------
n H i j k
-------------------------
2 2 1 0 0
3 3 0 1 0
4 4 2 0 0
5 5 0 0 1
6 6 1 1 0
7 8 3 0 0
8 9 0 2 0
9 10 1 0 1
10 12 2 1 0
11 15 0 1 1
12 16 4 0 0
13 18 1 2 0
14 20 2 0 1
15 24 3 1 0
16 25 0 0 2
17 27 0 3 0
18 30 1 1 1
19 32 5 0 0
20 36 2 2 0
21 40 3 0 1
22 45 0 2 1
23 48 4 1 0
24 50 1 0 2
25 54 1 3 0
26 60 2 1 1
27 64 6 0 0
28 72 3 2 0
29 75 0 1 2
30 80 4 0 1
31 81 0 4 0
32 90 1 2 1
33 96 5 1 0
34 100 2 0 2
35 108 2 3 0
36 120 3 1 1
37 125 0 0 3
38 128 7 0 0
39 135 0 3 1
40 144 4 2 0
41 150 1 1 2
42 160 5 0 1
43 162 1 4 0
44 180 2 2 1
45 192 6 1 0
46 200 3 0 2
47 216 3 3 0
48 225 0 2 2
49 240 4 1 1
50 243 0 5 0
51 250 1 0 3
52 256 8 0 0
53 270 1 3 1
54 288 5 2 0
55 300 2 1 2
56 320 6 0 1
57 324 2 4 0
58 360 3 2 1
59 375 0 1 3
60 384 7 1 0
61 400 4 0 2
62 405 0 4 1
63 432 4 3 0
64 450 1 2 2
65 480 5 1 1
66 486 1 5 0
67 500 2 0 3
68 512 9 0 0
69 540 2 3 1
70 576 6 2 0
71 600 3 1 2
72 625 0 0 4
73 640 7 0 1
74 648 3 4 0
75 675 0 3 2
76 720 4 2 1
77 729 0 6 0
78 750 1 1 3
79 768 8 1 0
80 800 5 0 2
81 810 1 4 1
82 864 5 3 0
83 900 2 2 2
84 960 6 1 1
85 972 2 5 0
86 1000 3 0 3
87 1024 10 0 0
88 1080 3 3 1
89 1125 0 2 3
90 1152 7 2 0
91 1200 4 1 2
92 1215 0 5 1
93 1250 1 0 4
94 1280 8 0 1
95 1296 4 4 0
96 1350 1 3 2
97 1440 5 2 1
98 1458 1 6 0
99 1500 2 1 3
100 1536 9 1 0
-------------------------
i j
H(n) = 2 3
----------------------
n H i j
----------------------
2 2 1 0
3 3 0 1
4 4 2 0
5 6 1 1
6 8 3 0
7 9 0 2
8 12 2 1
9 16 4 0
10 18 1 2
11 24 3 1
12 27 0 3
13 32 5 0
14 36 2 2
15 48 4 1
16 54 1 3
17 64 6 0
18 72 3 2
19 81 0 4
20 96 5 1
21 108 2 3
22 128 7 0
23 144 4 2
24 162 1 4
25 192 6 1
26 216 3 3
27 243 0 5
28 256 8 0
29 288 5 2
30 324 2 4
31 384 7 1
32 432 4 3
33 486 1 5
34 512 9 0
35 576 6 2
36 648 3 4
37 729 0 6
38 768 8 1
39 864 5 3
40 972 2 5
41 1024 10 0
42 1152 7 2
43 1296 4 4
44 1458 1 6
45 1536 9 1
46 1728 6 3
47 1944 3 5
48 2048 11 0
49 2187 0 7
50 2304 8 2
51 2592 5 4
52 2916 2 6
53 3072 10 1
54 3456 7 3
55 3888 4 5
56 4096 12 0
57 4374 1 7
58 4608 9 2
59 5184 6 4
60 5832 3 6
61 6144 11 1
62 6561 0 8
63 6912 8 3
64 7776 5 5
65 8192 13 0
66 8748 2 7
67 9216 10 2
68 10368 7 4
69 11664 4 6
70 12288 12 1
71 13122 1 8
72 13824 9 3
73 15552 6 5
74 16384 14 0
75 17496 3 7
76 18432 11 2
77 19683 0 9
78 20736 8 4
79 23328 5 6
80 24576 13 1
81 26244 2 8
82 27648 10 3
83 31104 7 5
84 32768 15 0
85 34992 4 7
86 36864 12 2
87 39366 1 9
88 41472 9 4
89 46656 6 6
90 49152 14 1
91 52488 3 8
92 55296 11 3
93 59049 0 10
94 62208 8 5
95 65536 16 0
96 69984 5 7
97 73728 13 2
98 78732 2 9
99 82944 10 4
100 93312 7 6
----------------------
i j k l
H(n) = 2 3 5 7
----------------------------
n H i j k l
----------------------------
2 2 1 0 0 0
3 3 0 1 0 0
4 4 2 0 0 0
5 5 0 0 1 0
6 6 1 1 0 0
7 7 0 0 0 1
8 8 3 0 0 0
9 9 0 2 0 0
10 10 1 0 1 0
11 12 2 1 0 0
12 14 1 0 0 1
13 15 0 1 1 0
14 16 4 0 0 0
15 18 1 2 0 0
16 20 2 0 1 0
17 21 0 1 0 1
18 24 3 1 0 0
19 25 0 0 2 0
20 27 0 3 0 0
21 28 2 0 0 1
22 30 1 1 1 0
23 32 5 0 0 0
24 35 0 0 1 1
25 36 2 2 0 0
26 40 3 0 1 0
27 42 1 1 0 1
28 45 0 2 1 0
29 48 4 1 0 0
30 49 0 0 0 2
31 50 1 0 2 0
32 54 1 3 0 0
33 56 3 0 0 1
34 60 2 1 1 0
35 63 0 2 0 1
36 64 6 0 0 0
37 70 1 0 1 1
38 72 3 2 0 0
39 75 0 1 2 0
40 80 4 0 1 0
41 81 0 4 0 0
42 84 2 1 0 1
43 90 1 2 1 0
44 96 5 1 0 0
45 98 1 0 0 2
46 100 2 0 2 0
47 105 0 1 1 1
48 108 2 3 0 0
49 112 4 0 0 1
50 120 3 1 1 0
51 125 0 0 3 0
52 126 1 2 0 1
53 128 7 0 0 0
54 135 0 3 1 0
55 140 2 0 1 1
56 144 4 2 0 0
57 147 0 1 0 2
58 150 1 1 2 0
59 160 5 0 1 0
60 162 1 4 0 0
61 168 3 1 0 1
62 175 0 0 2 1
63 180 2 2 1 0
64 189 0 3 0 1
65 192 6 1 0 0
66 196 2 0 0 2
67 200 3 0 2 0
68 210 1 1 1 1
69 216 3 3 0 0
70 224 5 0 0 1
71 225 0 2 2 0
72 240 4 1 1 0
73 243 0 5 0 0
74 245 0 0 1 2
75 250 1 0 3 0
76 252 2 2 0 1
77 256 8 0 0 0
78 270 1 3 1 0
79 280 3 0 1 1
80 288 5 2 0 0
81 294 1 1 0 2
82 300 2 1 2 0
83 315 0 2 1 1
84 320 6 0 1 0
85 324 2 4 0 0
86 336 4 1 0 1
87 343 0 0 0 3
88 350 1 0 2 1
89 360 3 2 1 0
90 375 0 1 3 0
91 378 1 3 0 1
92 384 7 1 0 0
93 392 3 0 0 2
94 400 4 0 2 0
95 405 0 4 1 0
96 420 2 1 1 1
97 432 4 3 0 0
98 441 0 2 0 2
99 448 6 0 0 1
100 450 1 2 2 0
----------------------------
[ Editor: n = 1 (H = 1) is omitted from each table. ]
In article <1993Dec20.035118.15321@galois.mit.edu>,
tycchow@cayley.mit.edu (Timothy Y. Chow) writes:
> This puzzle was posted about five years ago on this newsgroup by Paul
> Filipski, but hopefully there are many new readers now.
There are n=[log N/ log 6] powers of 6 which are smaller than N. For
each power we can replace one factor by 5,4,3,2, two factors of 6 and
so on. We have to sum all possibilities. Without doing the details,
this is the sum of sum of integers, so I say there are of the order of
n^3 Hamming numbers smaller than N. Inverting it I get that
H_n ~ 6^(cubic root(n))
Checking:
Hamming No. #100 1536 My formula 4091.268454
Hamming No. #200 16200 My formula 35534.965630
Hamming No. #300 82944 My formula 161882.963606
Hamming No. #400 311040 My formula 541336.592517
Hamming No. #500 937500 My formula 1500343.676792
Hamming No. #600 2460375 My formula 3657478.963814
Hamming No. #700 5898240 My formula 8114015.179735
Hamming No. #800 12754584 My formula 16738509.485377
Hamming No. #900 26244000 My formula 32581194.835169
Hamming No. #1000 51200000 My formula 60466189.144587
Well, the order of magnitude is right ....
-- Dror Lubin <lubin@fy.chalmers.se> (December 1993)
[ Editor: this estimate answers the question, so the note above that
no solution was found no longer applies. ]
Dror Lubin's argument has the right idea, but the constant in the
exponent is wrong, and the error grows without bound: his 6^(n^(1/3))
is 18% too large at n = 1000, but 5 times too small at n = 10^4 and
about 800,000 times too small at n = 10^6. The correct estimate is
H_n ~ exp( (6 n ln2 ln3 ln5)^(1/3) ) / sqrt(30)
= 0.1826 * 6.990^(n^(1/3)) (approximately).
Reason. The number N(x) of Hamming numbers 2^i 3^j 5^k up to x is the
number of lattice points (i,j,k >= 0) in the tetrahedron
i ln2 + j ln3 + k ln5 <= ln x.
Its volume is (ln x)^3 / (6 ln2 ln3 ln5). Counting the lattice points
on the three faces that lie in the coordinate planes adds a term of
order (ln x)^2, and the standard correction (as in counting lattice
points under a line) is to widen the tetrahedron by half a unit of each
coordinate, i.e. to replace ln x by ln x + (ln2 + ln3 + ln5)/2 =
ln(x sqrt 30):
N(x) = (ln(x sqrt 30))^3 / (6 ln2 ln3 ln5) + (smaller error).
Setting N(H_n) = n and solving for H_n gives the formula above. The
cube root is where Lubin's n^(1/3) comes from, but the base is
e^((6 ln2 ln3 ln5)^(1/3)) = e^1.9446 = 6.990, not 6: there are fewer
Hamming numbers below 6^t than his count of "replacements" suggests.
Accuracy. Computed (C++, all 2,922,023 Hamming numbers below 10^120):
n H_n estimate H_n/estimate
10 12 12.05 0.996
100 1536 1518 1.012
1000 5.1200 * 10^7 5.0905 * 10^7 1.006
10^4 2.8833 * 10^17 2.8598 * 10^17 1.008
10^5 2.9014 * 10^38 2.8916 * 10^38 1.003
10^6 5.1931 * 10^83 5.1837 * 10^83 1.002
For 1000 <= n <= 1,461,011 the ratio stays within 2.8% of 1. For the
count itself, N(10^100) = 1,697,191 against the estimate 1,697,223.0;
the error in N(x) grows only slowly (about -3, -12, -25, -32 at
x = 10^10, 10^40, 10^70, 10^100). So H_n is given to within a few
percent, and in this range the relative error tends to shrink as n
grows (an observation from the table, not a proved bound).
-- Claude (rec.puzzles Oracle, 2026-11-02)