The nth bell in the pattern book

A foundry can only enlarge a bell pattern by a factor of 2, 3 or 5. The reachable weights thin out fast, so walking the integers is hopeless.

The problem

The pattern book starts with one entry: a 1 kg bell. A new pattern is made by casting an entry already in the book at exactly twice, three times or five times its weight — those are the only moulds the foundry owns. So a mould applied to a book entry always yields another book entry, and the book lists every reachable weight once, in increasing order.

The foreman reads by position: given n, report the weight of the n-th entry, counting the 1 kg pattern as entry 1.

Most whole numbers never appear: 7, 11, 13 and 14 kg are all unreachable, being no product of twos, threes and fives. The gaps widen — past entry 1000 the book skips millions of kilograms between consecutive patterns.

Input. n — the position in the book, counting from 1.

Output. The weight in kilograms of the n-th entry.

Example.

n = 10   ->  12

The book opens 1, 2, 3, 4, 5, 6, 8, 9, 10, 12. Note that 6 appears once even though two routes reach it, 2·3 and 3·2.

A second example, on a weight the moulds cannot reach:

n = 7    ->  8

7 kg is not in the book, so entry 7 is 8 kg, cast as 2·2·2.

Constraints.

• 1 <= n <= 1690
• the answer fits in a 64-bit integer; entry 1690 is 2123366400

Hints

Approach

Brute force

Walk the whole numbers upward, dividing out every 2, 3 and 5 and checking whether 1 remains. Each test costs about 30 divisions, and entry 1690 sits past two billion: roughly 6·10¹⁰ divisions to find 1690 answers.

The insight

Every entry after the first is an earlier entry scaled by 2, 3 or 5, so the book generates itself: hold the pending candidates in a min-heap and pop them in weight order.

The scaling only ever multiplies, so a candidate is strictly heavier than the entry that produced it. That is the precondition: an entry is always pushed before the entries it outweighs are popped, so nothing smaller than the root is ever still missing, and the pops come out sorted. A set of pushed weights keeps 6 kg from being counted twice.

Algorithm

1. Start the heap holding 1, and a set holding 1.
2. Repeat n times: pop the smallest weight — that is the next book entry.
3. For each mould 2, 3 and 5, multiply the popped weight. If the product is not in the set, add it and push it.
4. The weight popped on the n-th round is the answer.

Complexity

Time O(n log n) — n pops and at most 3n pushes on a heap that never exceeds about 2n entries. Space O(n) for the heap and set together.

Solution

"""The foundry's nth bell — grow the weights in order from a min-heap and a seen set."""

import heapq

SCALES = (2, 3, 5)


def solve(n):
    frontier = [1]
    seen = {1}
    weight = 1
    for _ in range(n):
        # Invariant: the heap holds every castable weight that is one scaling step
        # past a weight already emitted and not yet emitted itself. The smallest
        # weight not yet emitted must be one of them, so the root is the next one.
        weight = heapq.heappop(frontier)
        for scale in SCALES:
            larger = weight * scale
            if larger not in seen:      # the set is what keeps 6 = 2*3 = 3*2 single
                seen.add(larger)
                heapq.heappush(frontier, larger)
    return weight

TESTS = [
    ((1,), 1),
    ((7,), 8),
    ((10,), 12),
    ((11,), 15),
    ((25,), 54),
    ((1690,), 2123366400),
]

Pitfalls

• No set of seen weights. 6 kg is pushed twice, 12 kg four times, and the pops repeat: the run becomes 1, 2, 3, 4, 5, 6, 6, 8, 9, 10, so n = 10 returns 10 instead of 12. The duplicates also grow the heap by a constant factor at every level.
• Adding to the set at pop rather than at push. The duplicate 6 is already in the heap by then, so it still comes out twice.
• Enumerating exponents against a guessed ceiling. A triple loop over powers of 2, 3 and 5 up to 10^9, then sorting, never produces entry 1690 at all: that weight is 2123366400, above the ceiling, so the answer comes back short.

Variants

• The card catalogue merge — the same frontier of candidates, except the streams are handed to you already built instead of being generated as you go.
• The heap invariant — why repeated popping yields a sorted run without sorting anything.