Hamming numbers are defined as numbers whose only prime factors are 2, 3, and 5.
arithmetic/hamming.numbers New
New entry, edited from material collected for the archive and not yet in a released version.
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
No solution was found in the collected postings.
[ 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. ]