Whole-turn gearing

A clockmaker's test bench runs only when every gear on it meshes at a whole-number ratio. Almost every way of loading it fails. The job is to count the ones that do not.

The problem

The bench has n spindles, numbered 1 to n; spindle s carries a pinion of 10s teeth. Beside it wait n gears, numbered the same way, so gear g has 10g teeth.

A gear mounts on a spindle only if the pair turns at a whole-number ratio — only if g divides s or s divides g. Anything else grinds. Every spindle takes one gear and every gear is used once. Count the complete loadings.

Input. n — the number of spindles, which is also the number of gears.

Output. The number of ways to mount all n gears with every spindle meshing cleanly.

Example.

n = 3   ->  3

Listing the gear on spindle 1, then 2, then 3, the three that work are 1 2 3, 2 1 3 and 3 2 1. The other three all put gear 3 on spindle 2 — a ratio of 1.5.

A second example, where the tightest spindle is not the last one:

n = 4   ->  8

Spindle 3 accepts only gear 1 or gear 3; spindle 4 accepts gear 1, 2 or 4; spindle 1 accepts anything. Eight of the 24 orderings survive.

Constraints.

• 1 <= n <= 15
• The answer fits in a 64-bit integer.

Hints

Approach

Brute force

Generate all n! orderings and check each with an O(n) pass. At n = 15 that is 1,307,674,368,000 orderings, about 2 × 10¹³ divisibility tests.

The insight

A loading that grinds at spindle s grinds no matter what you do with the spindles you have not filled yet, so reject it at s and never generate the subtree beneath it.

The mesh rule is local: it reads one spindle and the one gear on it. That is the precondition this prune needs — a partial loading that already breaks a rule can never be repaired by extending it — and it holds because no later choice touches spindle s again. Cutting a dead node at depth d discards (n - d)! orderings at once.

The filling order decides how much that saves. Spindle n accepts only divisors of n and n itself; spindle 1 accepts everything. Filling from n downward visits 102,376 nodes at n = 15, filling from 1 upward 747,961, for the same answer.

Algorithm

1. Keep one array mounted, a flag per gear, all false.
2. Define fill(s): if s == 0, every spindle is loaded, so return 1.
3. For each unmounted g with g % s == 0 or s % g == 0: mark it, add fill(s - 1) to a running total, unmark it.
4. Return the total.
5. Call fill(n), so the fussiest spindle is chosen at the root.

Complexity

Time O(n!) in the worst case — the bound is the size of the tree, and the filter changes its constant, not its order of growth. In practice it collapses: 102,376 nodes at n = 15. Space O(n) — one flag array and a stack n frames deep.

Solution

"""Whole-turn gearing — backtracking over spindles with a divisibility filter."""


def meshes(gear, spindle):
    """True when the ratio between the two tooth counts is a whole number."""
    return gear % spindle == 0 or spindle % gear == 0


def solve(n):
    mounted = [False] * (n + 1)

    def fill(spindle):
        # Invariant: spindles n down to spindle+1 each carry one gear, and
        # mounted[g] is True for exactly the gears those spindles hold.
        if spindle == 0:
            return 1
        total = 0
        for gear in range(1, n + 1):
            if not mounted[gear] and meshes(gear, spindle):
                mounted[gear] = True
                total += fill(spindle - 1)
                mounted[gear] = False     # un-choose: the bench is shared
        return total

    # High spindles have the fewest partners, so fill them first and the tree
    # narrows at the root instead of at the leaves.
    return fill(n)

TESTS = [
    ((1,), 1),
    ((2,), 2),
    ((3,), 3),
    ((4,), 8),
    ((6,), 36),
    ((9,), 250),
    ((15,), 24679),
]

Pitfalls

• Forgetting to unmark the gear after the recursive call. The flags are one shared buffer, so a gear left mounted vanishes from every sibling branch. The count does not drift slightly — it collapses to 1, because only the first path down the tree ever completes.
• Testing g % s == 0 alone. That forces every gear to be a multiple of its spindle, which only the identity loading satisfies, so the answer is 1 for every n. Either direction is a whole ratio: 40 teeth on a 10-tooth pinion and 10 on a 40-tooth pinion both mesh.
• Filling spindle 1 first. Correct, but the root branches n ways with nothing to prune, and the node count grows about sevenfold at n = 15.

Variants

• Glare-free floodlights — the same choose, recurse, un-choose loop, but the conflict runs between two placed items rather than between an item and its slot, and it returns the layouts.
• Pruning — the lesson behind the ordering choice, and how to state what a cut saves.