4

I was doing a programming problem in which I was required to write a function that requires the nth hamming number.

I have some code with which creates a list of size n, with each value in the list being "1", and then doing some manipulations using the list to alter values of the list so that every value in the list is a hamming number.

The code is here:

def hamming(num):
  #Make a list of size n, n-1 is the value we want to return.
  h = [1] * num

  #Make 3 variables representing the 2^i, 3^j, 5^k of our hamming number.
  x2, x3, x5 = 2,3,5

  #Counter variables that we will raise 2, 3, and 5, to.
  i = j = k = 0

    #Our initial list is filled with n values of the integer 1.
  for n in xrange(1, num):
    #Get the smallest number, then we will multiply it by 2, 3, or 5.
    h[n] = min(x2, x3, x5)
    if x2 == h[n]:
      i += 1
      x2 = 2 * h[i]
    if x3 == h[n]:
      j += 1
      x3 = 3 * h[j]
    if x5 == h[n]:
      k += 1
      x5 = 5 * h[k]
  return h[-1]

Essentially, my question is not HOW this method of generating hamming numbers works, but WHY. For example, 128 is a hamming number, and 2^7 * 3^0 * 5^0 is also 128. However, because 7 is not a hamming number, and this generates hamming numbers using previously calculated values in the list, I guess I'm asking why it appears that for any hamming number expressed in 2^i * 3^j * 5^k, you can generate the hamming number without i, j, or k being hamming numbers.

Sorry if the question is confusing, if you need me to clarify something just ask and I'll try to explain it better.

1
  • 1
    "it appears that for any hamming number expressed in 2^i * 3^j * 5^k, you can generate the hamming number without i, j, or k being hamming numbers" - yes, that is correct.
    – jonrsharpe
    Jul 31, 2014 at 17:08

1 Answer 1

4

A hamming number is a number with only prime factors of 2, 3 and 5.

To quote the wikipedia article:

In number theory, these numbers are called 5-smooth, because they can be characterized as having only 2, 3, or 5 as prime factors.

You might want to read up on what prime factors are and how they work. But basically it means if you take the prime factor and multiply it enough times, you can get to your original number. A prime factor is the lowest possible multiplier (since you cant get smaller than a prime).

For example, if you have the number 12, 12 is evenly divisible by 6, 4, 3, and 2. Of these four factors, 2 are NOT prime and thus can be deduced even further. 6 can be divided by 2 and 3. And 4 by 2. Therefore our prime factors are 2 and 3.

Your code is taking the prime factors of a hamming number to i, j, and k powers. It doesn't matter what the power is as long as the prime factors are correct. So, you can get a hamming (128) with 2^7 even though 7 is not hamming because the 2 is what matters. For example, 2^7 is really just, 2 x 2 x 2 x 2 x 2 x 2. So 7 really isn’t involved. Your initial list is just a list of random integers, it has nothing to do with hamming. The 2, 3, and 5 are they keys.

1
  • I think I understand how it works now. The question was that 2^7 = 128, but the first couple hamming numbers are [1,2,3,4,5,6,8,9,10] so the fact that 7 wasn't in the list threw me off. If I just considered that 64 is a hamming number and 64 is 2^6, then at some point the code will reach x2 = 2 * h[i] where i is 64, then x2 will be 128. Jul 31, 2014 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.