Ugly numbers with heapq

Why this matters

Some problems ask for a list of whole numbers that have no prime factor except 2, 3 and 5. A typical question is "what is the 50th number in that list?" You have to list the numbers in order, skip the ones that do not fit, and stop at the right place.

A prime factor is a prime number that divides a number exactly. A prime is a number greater than 1 whose only divisors are 1 and itself. The number 12 has the prime factors 2 and 3, because 12 = 2 × 2 × 3. The number 14 has the prime factors 2 and 7, because 14 = 2 × 7.

The numbers in this problem are called ugly numbers. An ugly number is a positive whole number whose only prime factors are 2, 3 and 5. So 12 is ugly, and 14 is not, because 7 is a prime factor of 14 and 7 is not one of 2, 3 or 5.

This lesson gives two ways to find the nth ugly number. The first uses a heap. A heap is a structure that always gives back its smallest item quickly. Python has one in the heapq module, and the heap is stored in a plain list. The second method uses three indexes into a list, and it needs no heap at all. Both methods use the same idea, which is explained first.

Start by checking one number

Before any clever method, look at a plain test. A number is ugly if you can divide it by 2, 3 and 5 until only 1 is left. Take 45. Divide by 3: 15. Divide by 3 again: 5. Divide by 5: 1. Only 1 is left, so 45 is ugly. Take 49. Dividing by 7 is not allowed, because 7 is not one of 2, 3 or 5. The number stays at 49, so it is not ugly.

In Python, the test looks like this.

Output:

True
False

The % operator gives the remainder after division. The check x % p == 0 means "p divides x exactly." The while loop removes every copy of p. The // operator is integer division, which divides and drops any fraction. Python's int type has no size limit, so the test does not need a special type for big numbers.

The test works, but it is slow as a way to build a list. You would test 1, then 2, then 3, and so on, and most numbers fail. There are only 86 ugly numbers up to 1000. Testing every number up to 1000 to find them wastes most of its work on numbers that fail.

A better plan is to build the ugly numbers directly, from smaller ones.

The key observation

Here is the rule. Every ugly number except 1 is 2 times an earlier ugly number, or 3 times an earlier ugly number, or 5 times an earlier ugly number.

Look at 12. It is 2 times 6. Six is ugly, so 12 comes from 6. Look at 15. It is 3 times 5, and 5 is ugly. Look at 45. It is 5 times 9, and 9 is ugly.

The rule holds because an ugly number has prime factors only 2, 3 and 5. If it has at least one factor, take one of those factors away. What is left is still ugly and smaller. So the number is that smaller ugly number times 2, 3 or 5.

This rule gives a way to list the numbers in order. Start with 1. Each ugly number gives three candidates: its double, its triple and its five-times value. The next ugly number is the smallest candidate that has not been listed yet.

Here are the first fifteen ugly numbers, printed by the three-index method that appears later in this lesson:

[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24]

Method 1: a min-heap of candidates

A min-heap is a heap where the smallest value is always at the top. The heapq module works on a normal list. You do not create a special object. The functions are:

• heapq.heappush(heap, value) puts a value into the heap.
• heapq.heappop(heap) removes and returns the smallest value.
• heap[0] reads the smallest value without removing it.

A list with one item is already a valid heap, so heap = [1] is a heap that holds 1.

The heap method works in a loop. It starts with 1 in the heap. Each step does two things. It pops the smallest value, which is the next ugly number. Then it pushes that value times 2, times 3 and times 5 into the heap.

There is one problem. The same number can be made in two ways. The number 6 is 2 times 3, and it is also 3 times 2. If you push it twice, the list gets a duplicate. A Python set remembers which numbers have been pushed, so each one goes into the heap only once. A set is a collection that holds each value at most once, and checking in on a set is fast.

Here is the code.

Output:

1 12 15 36 2123366400

The variable current holds the value popped on the last loop. After n pops, it is the nth ugly number.

Notice the check if nxt not in seen: and then seen.add(nxt). In Python, set.add returns None, not a true or false answer, so you cannot write if seen.add(nxt): to add and test in one step. The Mistakes section shows what happens if you try.

To see the order, here is a version that prints each pop. It prints the heap after the pop and before that number's multiples are pushed.

Output:

pop 1: 1  heap now []
pop 2: 2  heap now [3, 5]
pop 3: 3  heap now [4, 5, 10, 6]
pop 4: 4  heap now [5, 6, 10, 15, 9]
pop 5: 5  heap now [6, 9, 8, 15, 20, 10, 12]
pop 6: 6  heap now [8, 9, 10, 15, 20, 25, 12]
pop 7: 8  heap now [9, 15, 10, 18, 20, 25, 12, 30]
pop 8: 9  heap now [10, 15, 12, 16, 20, 25, 40, 30, 18, 24]

Read the first lines by hand. Pop 1 takes 1 out, and the heap is empty. Then the code pushes 2, 3 and 5. Pop 2 takes 2 out. The heap is left with 3 and 5. The code pushes 4, 6 and 10 into it.

The lines show the heap as a Python list. The list is not sorted. So [4, 5, 10, 6] does not mean the list is in order. It means 4 is at the front, because a heap only keeps the smallest value at position 0. The other values are in an order that makes the heap rule true, and nothing more.

The answers from this method are: the 1st ugly number is 1, the 10th is 12, the 11th is 15, and the 1690th is 2123366400. The 1690th number is a common check value. The next section checks the method against a brute-force test, which is a test that checks each whole number one by one with is_ugly.

The cost is about n pops and about 3n pushes, each costing about log n steps, where log n is the number of levels in the heap. The heap stays small, but the set also grows with each new number.

Method 2: three indexes

The second method removes the heap. It builds a list of ugly numbers, one at a time, in order.

Keep three indexes. An index here is a position in the list, counted from 0. The index i2 points to the earliest ugly number whose double has not been added yet. The index i3 does the same for triples, and i5 for five-times values.

At each step, compute three candidates: the number at i2 times 2, the number at i3 times 3, and the number at i5 times 5. The smallest of the three is the next ugly number. Append it to the list. Then move forward every index whose candidate was the smallest. Use three separate if checks, not elif. A number can be a double of one ugly number and a triple of another, and both indexes must move past it.

Here is a trace of the first five steps. The list starts as [1].

At step 5, the value 6 came from two places, 2 times 3 and 3 times 2. Both indexes moved, so 6 is stored only once. The next step looks at the indexes again, and it does not see 6 a second time.

Here is the code.

Output:

1 12 15 36 2123366400

The list grows with append, so the method does not need to know the size in advance. That is different from a fixed-size array. The list ends with n values, and ugly[n - 1] is the last one.

Here is a version that prints the first nine steps. For each step it shows the three candidates, the value chosen, the three indexes after the step, and which indexes moved.

Output:

1  2,3,5  2  1,0,0  moved 2x
2  4,3,5  3  1,1,0  moved 3x
3  4,6,5  4  2,1,0  moved 2x
4  6,6,5  5  2,1,1  moved 5x
5  6,6,10  6  3,2,1  moved 2x and 3x
6  8,9,10  8  4,2,1  moved 2x
7  10,9,10  9  4,3,1  moved 3x
8  10,12,10  10  5,3,2  moved 2x and 5x
9  12,12,15  12  6,4,2  moved 2x and 3x
list: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12]

Look at step 8. The 2x candidate is 10 and the 5x candidate is 10 too. The chosen value is 10, and both the 2x index and the 5x index move past it. The index method handles ties this way without any set.

The method never looks back at a number it has already passed, and it never needs to test a candidate. It needs one list and three integers. Each step does a fixed amount of work, so the total time grows in a straight line with n.

Both methods agree. For every n from 1 to 300, the heap method, the index method and a brute-force test give the same answer.

The brute-force test checks every whole number up to 1000000 with is_ugly. It finds 507 ugly numbers in that range.

Choosing between the two methods

Both methods give the same answers. They differ in memory and in the work done for each number.

The index method is the one to write in a test or an interview, because it is short and its work is easy to count. The heap method is worth knowing because it reads like the idea itself: pop the smallest, then push its multiples. The heap method also shows how to extend the problem. With the factors 2, 3, 5 and 7, the heap method needs only one more entry in the factor tuple. The index method needs one more index and one more candidate in its loop.

Example 2: counting instead of listing

The index method gives a value for one n. Many problems ask a different question: how many ugly numbers are at most some limit? You can answer that by calling the method with n = 1, 2, 3, and so on, until the value passes the limit.

Output:

ugly numbers <= 1000: 86

The loop stops at the first ugly number above the limit. Every number before it was counted.

This version is simple, but it recomputes the list for each n. For a single query that is fine. For many queries, it is better to build the list once with a limit and count the entries that fit. That change is the exercise at the end of this lesson.

Example 3: where the numbers get large

The 1690th ugly number, 2123366400, is close to the largest value a 32-bit signed integer can hold. That largest value is 2147483647. In languages such as Java, a value past that limit wraps around to a negative number. This is called integer overflow.

Python does not have that problem for its int type. An int grows to fit the number, so the same method keeps going with exact values:

Output:

2147483648 2149908480 2152336050
8062156800

The value 2147483648 is one more than the largest 32-bit signed integer. Python keeps it exact. A fixed-size type does not. The array module can hold values of a fixed type, and it refuses a value that is too large for that type. Here is a short program that tries to store one more than the largest value of a signed 32-bit integer ("i" in array):

from array import array
 
values = array("i", [2147483647])
values[0] = values[0] + 1

Output from Python 3.14 when the file is saved as overflow_demo.py. The first line of the traceback shows the path where the file was saved, so it differs on each machine:

Traceback (most recent call last):
  File "overflow_demo.py", line 4, in <module>
    values[0] = values[0] + 1
    ~~~~~~^^^
OverflowError: signed integer is greater than maximum

Python raises an error here instead of wrapping around. The ctypes module can do the wrap-around on purpose. Its c_int32 type wraps the value into the 32-bit range, so ctypes.c_int32(2147483648).value gives -2147483648. Use it only when you need that behaviour, for example to match a C library.

The fix for a problem like this is to keep the numbers as Python int values, which is what the method above does. Check the result against a second method, such as the brute-force test, so a wrong answer is caught.

Common mistakes

The first mistake is adding duplicates in the heap method. Without the set, the heap method gives the number 6 twice. This version has the set check removed:

Output:

[1, 2, 3, 4, 5, 6, 6, 8, 9, 10]

The fix is the seen set. Any value that was already pushed must be skipped.

The second mistake is using elif in the index method. The code looks neater, but it fails on 6. Changing the three if checks to if, elif, elif gives this list of the first 10 numbers:

[1, 2, 3, 4, 5, 6, 6, 8, 9, 10]

Here 6 appears twice, because the elif chain moved only the 2x index at step 5, and the 3x index stayed behind. Its candidate 6 then appeared again at the next step. Three separate if checks make both indexes move.

The third mistake is checking set.add as if it were a true or false test. In Java, the add method returns a yes or no answer. In Python, set.add returns None, which is treated as false. So if seen.add(nxt): never runs the code inside it. Nothing is pushed, the heap runs out, and the next pop fails:

IndexError: index out of range

The error comes from heapq.heappop on an empty list. Use if nxt not in seen: on one line and seen.add(nxt) on the next.

The fourth mistake is mixing up nth with a list index. The function nth_with_pointers(1) returns 1, because the first ugly number is 1. It is stored at index 0, so the code returns ugly[n - 1]. Returning ugly[n] reads one position past the end of the list, and Python stops with an error:

IndexError: list index out of range

The fifth mistake is printing a heap and reading it as a sorted list. The heapq functions keep only the smallest value at position 0. The rest of the list is in heap order, not sorted order. Here is a heap of five values, printed as a list and then sorted:

Output:

heap list: [1, 2, 4, 5, 3]
sorted: [1, 2, 3, 4, 5]

To get the values in order from a heap, pop them one by one, or call sorted on a copy.

Practice

Exercise 1. What is the 20th ugly number?

Show the answer

It is 36. The function nth_with_pointers(20) returns 36. The list up to that point is 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36.

Exercise 2. How many ugly numbers are at most 1000? Explain why the answer is not 1000 divided by a simple factor.

Show the answer

There are 86 ugly numbers at most 1000. Ugly numbers are sparse, because each one must have only the factors 2, 3 and 5. A number with a factor such as 7, 11 or 13 is never ugly, and many whole numbers have one of those.

Exercise 3. Is 49 an ugly number? Explain your answer using the is_ugly function.

Show the answer

No. The function returns False. The loop divides 49 by 2 zero times, by 3 zero times, and by 5 zero times, so the value stays 49, which is not 1. The prime factor 7 is the reason. 49 = 7 × 7.

Exercise 4. Write a function that returns how many ugly numbers are at most a limit, but builds the list only once. Use the index method and stop when the next value passes the limit.

Show the answer

Output:

86
507

The function does not need a fixed array size, so there is no size limit to pick. It returns 86 for the limit 1000, the same as the slower version, and 507 for the limit 1000000.

Exercise 5. Why does the heap method need the seen set, but the index method does not?

Show the answer

The heap method can reach the same number through two different paths, such as 2 times 3 and 3 times 2. Each path pushes the number into the heap again, so the set blocks the second copy. The index method moves every index that produced the smallest candidate at once. Each path is consumed in the same step, so the same value is never stored twice.

Summary

• An ugly number has prime factors only 2, 3 and 5. Every ugly number except 1 is 2, 3 or 5 times a smaller ugly number.
• The heap method pops the smallest candidate and pushes its 2x, 3x and 5x values. A set stops duplicates from entering the heap.
• The index method keeps three positions in the list and appends the smallest candidate at each step. Move every index that matched, using separate if checks.
• Python int values do not overflow, so the same code gives exact answers past 2147483647. A fixed-size type such as array("i") raises an error instead.
• The list inside a heapq heap is not sorted. Only position 0 is guaranteed to be the smallest value.