Introduction

I am used to doing a code kata on Codewars after getting up for some weeks, which is a useful training for me to keep programming skills and algorithmic thought. Today’s kata is about Hamming numbers.

In most cases, I would solve the problem in minutes. However, today I get stuck on this challenge. It is not clear to generalize how the exponents of 2, 3 and 5 change each time. Finally, I follow the approach from one answer on Stack Overflow and implement it in Python.

This approach works for the kata, but not in an elegant way, because it cannot calculate the $n^{th}$ Hamming number as requested, but give a large set of Hamming numbes. If the requested $n^{th}$ Hamming number is in, we can just return it; if not, we will fail. This way works because the kata asks for at most the first 5000 Hamming numbers, and we actually calculate the first 5809 numbers.

After submitting, I find a better solution from another user, which is better and more elegant, but somehow not that intuitive, at least for me. In this post, I will talk about these two different approaches.

Kata Description

The description for this kata is excerpted from Codewars:

A Hamming number is a positive integer of the form $2^{i}3^{j}5^{k}$, for some non-negative integers $i$, $j$, and $k$.

Write a function that computes the nth smallest Hamming number.

Specifically:

  • The first smallest Hamming number is $1 = 2^{0}3^{0}5^{0}$
  • The second smallest Hamming number is $2 = 2^{1}3^{0}5^{0}$
  • The third smallest Hamming number is $3 = 2^{0}3^{1}5^{0}$
  • The fourth smallest Hamming number is $4 = 2^{2}3^{0}5^{0}$
  • The fifth smallest Hamming number is $5 = 2^{0}3^{0}5^{1}$

Your code should be able to compute the first 5000 (LC: 400, Clojure: 2000, NASM, C, D, C++, Go and Rust: 13282) Hamming numbers without timing out.

You can refer to Wikipedia for more information about Hamming numbers.

The first solution adapted from this link is more intuitive. We just recursively calculate all the Hamming numbers smaller than a maximum number, and return the asked $n^{th}$ Hamming number.

This kata asks for at most the first 5000 Hamming numbers, so we set the maximum to 0xffffffffffff, which can result in actually 5809 numbers. The source code in Python is shown below:

hamming_nums = list()
max_num = 0xffffffffffff

def gen_hamming(n):
    if n in hamming_nums:
        return
    hamming_nums.append(n)
    if n < max_num // 2:
        gen_hamming(n*2)
    if n < max_num // 3:
        gen_hamming(n*3)
    if n < max_num // 5:
        gen_hamming(n*5)

def hamming(n):
    gen_hamming(1)
    hamming_nums.sort()
    return hamming_nums[n-1]

As said, this algorithm is intuitive, but not elegant for this kata’s request. What if the request is more than 5000? We want an algorithm that can calculate Hamming numbers from $1^{st}$ to $n^{th}$ sequentially.

Solution 2: Sequential Calcuation

The solution shared by another user in Codewars is more elegant:

def hamming(n):
    bases = [2, 3, 5]
    expos = [0, 0, 0]
    hamms = [1]
    for _ in range(1, n):
        next_hamms = [bases[i] * hamms[expos[i]] for i in range(3)]
        next_hamm = min(next_hamms)
        hamms.append(next_hamm)
        for i in range(3):
            expos[i] += int(next_hamms[i] == next_hamm)
    return hamms[-1]

We can unfold the iteration to understand:

#1 bases = [2, 3, 5]	expos = [0, 0, 0]       hamms = [1]
    -> next_hamms = [2*1, 3*1, 5*1]
    -> min(next_hamms) = 2
#2 bases = [2, 3, 5]	expos = [0+1, 0, 0]     hamms = [1, 2]
    -> next_hamms = [2*2, 3*1, 5*1]
    -> min(next_hamms) = 3
#3 bases = [2, 3, 5]	expos = [1, 0+1, 0]     hamms = [1, 2, 3]
    -> next_hamms = [2*2, 3*2, 5*1]
    -> min(next_hamms) = 4
#4 bases = [2, 3, 5]	expos = [1+1, 1, 0]     hamms = [1, 2, 3, 4]
    -> next_hamms = [2*3, 3*2, 5*1]
    -> min(next_hamms) = 5
#5 bases = [2, 3, 5]	expos = [2, 1, 0+1]     hamms = [1, 2, 3, 4, 5]
    -> next_hamms = [2*3, 3*2, 5*2]
    -> min(next_hamms) = 6
#6 bases = [2, 3, 5]	expos = [2+1, 1+1, 1]   hamms = [1, 2, 3, 4, 5, 6]
    -> next_hamms = [2*4, 3*3, 5*2]
    -> min(nex_hamms) = 8
#7 bases = [2, 3, 5]	expos = [3+1, 2, 1]     hamms = [1, 2, 3, 4, 5, 6, 8]

In each iteration, the algorithm will append the result list with the minimum product, which will be used in further multiplications as well.

Summary

It takes me some time to figure this kata out. The two solutions both work, and it is interesting to analyze the same problem in two ways. I recommend code kata, a good way to keep mentally active and healthy :)

BTW, the Rosetta Code site gathers implementations of Hamming numbers calculation in different programming languages.