rec.puzzles Archive

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)