Memoization

Memoization is the substitution of a table lookup for a computation: remember what a function returned, keyed on what it was asked, and hand back the stored value the next time the same question arrives. It is the cheapest large speed-up in this repository — usually one decorator, sometimes one array — and it recurs across the problems below because the short, obviously-correct statement of a counting or chain-following problem is almost always a recurrence, and a recurrence evaluated literally asks the same question an enormous number of times.

The idea

Two preconditions, both easy to state and easy to violate. The function must be pure — same arguments, same result, no observable side effect — and its arguments must serve as a key: hashable in Python, an integer index or a hash in C. Given those, the speed-up is a single ratio:

calls ÷ distinct arguments.

That number is worth estimating before writing anything, because it is also the diagnosis when the cache turns out to do nothing. What makes it large is always the same structural fact: the map from inputs to states is many-to-one. Memoization does not make a computation cheaper; it makes you pay for it once per state instead of once per visit, and the whole art is arranging for there to be far fewer states than visits.

Problem 92 is that sentence with the numbers filled in. It classifies every number below $10^7$ by whether its square-digit-sum chain ends at 89, but a chain depends only on the digit-square-sum, and a 7-digit number has at most $81 \times 7 = 567$ of those. So the classification is computed once per sum into a flat is89 table and read $10^7$ times — 567 chain walks instead of ten million. The input space is huge; the state space is a few hundred. Everything below is a variation on finding that collapse.

Where the repetition comes from

Overlapping subproblems in a recurrence. The dominant source, and the reason this tag and dynamic programming overlap so heavily. F(n) calls F(n-1) and F(n-k-1); the call tree is exponential, the set of distinct arguments is $O(n)$. Problems 76, 77, 115, 161, 259, 301, 755, 887 and 1000 are all this shape, differing only in what the state is — a remaining amount and a largest allowed part, a cell and a frontier mask, a position and a digit-DP carry, a tree height and a slack.

A functional graph. When every value has exactly one successor, chains merge and then share a tail. Problems 14 (Collatz), 74 (digit factorials) and 92 (square digit sums) all ask a question about $10^6$–$10^7$ chains that collectively visit only a modest set of distinct nodes. Cache per node and each start costs amortised $O(1)$; see functional graph.

Repeated arguments in a sweep. Sometimes the repetition is a theorem rather than a recursion. Problem 153 memoises the divisor-sum summatory $D(x)$ in a plain dict because the nested quotient blocking only ever evaluates it at values of the form $\lfloor N/k \rfloor$, of which there are $O(\sqrt N)$ however large $N$ is. Problem 641 leans on the same fact for the Mertens function: the recursion $M(x) = 1 - \sum_{k \ge 2} M(\lfloor x/k \rfloor)$ only ever recurses on quotients of $x$, and a quotient of a quotient is again a quotient, so evaluating $M$ near $10^9$ fills only a few hundred memo entries before it bottoms out. Problems 787 and 935 reuse that same Mertens memo, and 935 shares one cache across five different Möbius sums, because they all ask about the same quotients. Halving recursions are the narrowest form of this. Problem 463 wants the prefix sum $S(n)$ of a recurrence defined on $n/2$ and $n/4$ at $n = 3^{37}$. $S$ alone does not recur, but paired with a second sum $O$ over the odd indices the two do, each on $\lfloor n/2 \rfloor$ and its neighbour. That is about two states per level, 115 of each for the whole input. Without the memo, the four-way branching is exponential. The trick is general: if a quantity will not recur on itself, look for the companion sum that closes the system. Problem 549 keeps a per-prime list of $s(p^e)$, extended on demand as larger exponents appear, because the same prime powers recur all the way up a linear sieve. Neither cache is a dynamic program; both convert a quadratic-looking sweep into a linear one.

Plain deduplication. Least glamorous, often enough. Problem 60 memoises the edge predicate "both concatenations of $a$ and $b$ are prime" across a clique search that revisits the same pairs constantly; problem 21 memoises the $O(\sqrt n)$ proper-divisor sum because amicability asks for $d(d(x))$ and so queries each value roughly twice. Here the cache is not the algorithm, only a way of not repeating yourself.

A self-similar tree. Problem 943 is the extreme case of the opening sentence. It asks for prefix sums of a two-symbol Kolakoski-style sequence whose run lengths are the sequence itself. Read backwards, each element is the parent of the run it describes, so the first $2.2 \times 10^{13}$ terms are the leaves of a derivation tree only a few dozen levels deep. The tree is far too big to walk, but most of its subtrees have the same shape, so the memo is keyed on the subtree. The first key that comes to mind, (value, height), is not enough. A node's children take their symbol from the parity of the node's position, and that parity depends on everything to its left. The key that actually fixes a subtree adds a bitmask of those parities, one bit per level. With it, the distinct keys peak near $N^{\log 2 / \log(a+b)}$: a few million for the densest pair and a few dozen once $a+b$ is in the hundreds. That is roughly $10^{13}$ leaves served from $10^6$ table entries, and the answer becomes one root-to-leaf descent that adds up the cached totals of every whole subtree to the left.

A walk too long to take. Sometimes the thing to cache is not a value but a jump: where a process ends up after a stretch of steps, and what it collected on the way. Problem 551 steps $a_n = a_{n-1} + s(a_{n-1})$ (add your own digit sum) $10^{15}$ times. Write the current value as $H \cdot 10^k + L$. Until $L$ overflows $10^k$, the high part matters only through its digit sum $c$. So "how many steps until the low $k$ digits carry, and what is left behind" is a function of $(k, c, L)$ alone. A level-$k$ jump is about ten level-$(k-1)$ jumps, one per leading digit, and the memo holds 27,324 jumps at $n = 10^{20}$. Problem 946 is the finite version. Gosper's continued-fraction arithmetic is a 32-state machine, and the solution caches each (state, input term) transition once. With every edge cached, the memo is the state graph, so a long run of identical inputs can be cycle-detected, and whole cycles are skipped with one multiplication. Both problems memoise the step function, not the answer, and then ask questions of the result that the original walk could never have answered in time.

Writing the table

A decorator. @functools.lru_cache(maxsize=None) (or functools.cache) in Python — the default, and the subject of its own page: functools.lru_cache, which covers key construction, cache_info(), and the hazards specific to the decorator.

An explicit dict. What problem 153 does for $D(x)$: a dict in the enclosing scope, probed with .get and filled on a miss. Worth the four lines when the cache is not merely an accelerator but part of the algorithm's story — you can size it, inspect it, seed it, or clear it at a boundary the decorator does not know about. Seeding can mean a whole second tier. Problem 641's mertens_at reads any argument up to the sieve bound $L$ straight from a prefix-sum array of the Möbius sieve, and uses the dict only above $L$. The array is the recursion's base case, and choosing $L$ above $x^{2/3}$ is what keeps the dict tier down to a few hundred keys.

An array — direct addressing. When the key is a small integer, skip hashing entirely and index. Problem 74's C sibling caches chain lengths in a flat calloc'd array of 3,000,000 ints (every reachable digit-factorial value stays below $7 \times 9! = 2540160$), using 0 as the "absent" marker; problem 115's C sibling keeps a cache[] alongside a parallel cache_valid[] flag array, which is what you need when 0 is a legitimate stored value. Problem 887's C port is the in-between case: a fixed $64 \times 64$ table where 0 can safely mean "empty", because every capacity it stores is at least 1. Even a sparse key can sometimes be turned into an index. Problem 787's C port stores the large Mertens values $M(\lfloor N/i \rfloor)$ in an array indexed by $i$, since every argument above the sieve bound $L$ has that form with $i < N/L$. The floor set becomes a dense array with no hashing at all. This is direct addressing, and it is the reason the C solutions here are typically an order of magnitude faster than the Python ones rather than merely twice as fast — no hashing, no boxing, perfect locality. Where the keys are large or sparse, C has to build what Python handed you for free: problem 153's C solution hand-writes a 65,536-slot open-addressing hash table purely to mirror one Python dict.

An interned key. When the natural key is a structure — a tree shape, a game form, a matrix — first give every distinct structure a small integer id (hash consing). Then key the memo on the ids. Problem 829 interns factor-tree shapes as (left id, right id) pairs. Only 65 distinct shapes occur across thirty target trees, and the shared subtrees are computed once. Problem 949 interns canonical combinatorial-game forms, about 35,000 of them, and memoises the order test $G \le H$ on pairs of ids. That predicate is the inner loop of canonicalisation and would otherwise re-compare deep trees recursively. Problem 946's C port interns its 32 matrix states the same way, so the transition table becomes a plain array. Interning gives you equality in $O(1)$ and keys that are cheap to hash or index. It also merges two equal structures built by different routes, which is the canonical-form rule applied to the key.

Back-propagation along a walk. The form worth knowing because it is not recursion at all. Problem 74 walks forward from each start until it meets a node it already knows (or closes a cycle), then fills in every node of the walk on the way out:

seen: list[int] = []
current: int = start
while current not in seen and current not in chain_length_cache:
    seen.append(current)
    current = sum_of_digit_factorials(current)
length = len(seen) + chain_length_cache.get(current, 0)
for i, num in enumerate(seen):
    chain_length_cache[num] = length - i

One walk populates dozens of entries; there is no recursion, so no stack limit and no frame overhead, and the loop is trivially portable to C. Whenever the recurrence is a chain rather than a tree, this beats a memoised recursion on every axis.

The four ways it goes wrong

Not actually applying it. Problem 115's Python F(n) carries the word "memoised" in its docstring and no cache in its body, while the C version at the same index has the cache / cache_valid pair. The gap is not subtle: 0.844 s against 0.0000119 s — about seventy thousand times, where the language accounts for maybe fifty. Without the table the recursion does not count the configurations, it enumerates them, so its cost is the number being computed (over $10^6$) rather than the $O(n^2)$ the recurrence promises. Two lessons: a missing cache can dwarf the entire language gap (a better algorithm beats a faster language), and a Python/C pair that disagrees this loudly is a parity bug worth chasing (parity across languages).

Caching the wrong object. Problem 74 solves the same problem three ways with the same memoization strategy: index 0 stores one integer per node — the chain length — while indices 1 and 2 store the whole tail list. Identical asymptotics, and 0.914 s against 2.53 s and 2.57 s, with memory in a worse ratio still. Cache the number you need, not the objects it was derived from; if the cached value is bigger than the computation that made it, the table has become the cost. The exception proves the rule. Problem 943 does cache lists: for each run of same-valued siblings it stores prefix sums of their counts and totals, plus the point where their mask sequence starts to cycle. It does this because the questions that follow are "the first $k$ of them" for many different $k$. A run up to 223 long would otherwise be re-walked on every query; with the stored prefix and its period, each query is answered in $O(1)$ by counting whole periods. Storing a structure is right when it answers a whole family of later queries. It is wrong when it only holds one value, more expensively than a number would.

Caching what is cheaper to recompute. A cache hit is a hash, a probe and a function-call frame. Problem 78 memoises pentagonal(x), which is x * (3 * x - 1) // 2 — two arithmetic operations, comfortably cheaper than looking them up. Harmless here, but the habit is a real pessimisation in a hot loop, and it is the mirror image of the previous mistake: measure the body against the lookup before wrapping it.

Outliving its inputs. A cache is only valid for the parameters it was computed under, and this repository has a second, sharper reason to care: --runs=N times repeated calls to solve(), so a table that survives between runs is warm from the second run onward and the reported average measures dict lookups instead of the algorithm. Problem 103 keeps its optimum-set cache in a module-level _CACHE and never clears it; problem 17 keeps its speller at module level and calls cache_clear() as the first statement of solve(); problems 14, 21, 161, 259, 301, 755 and 1000 sidestep the question entirely by defining the memoised function as a closure inside solve(), which is both honest and correct — a closure's results depend on what it captured, so a cache that outlives the capture can answer a later call with a value computed under a different bound. Build the cache where the input lives. Problem 943 shows the same rule at a finer grain. Its key leaves out the pair $(a, b)$, so the memo is valid for one pair only, and the Python solution rebuilds it inside the per-pair function, roughly fifty thousand times per call. The C port does not free and reallocate fifty thousand tables. It stamps every slot with a generation counter and bumps the counter between pairs, so a slot from an earlier pair reads as empty. That invalidates the whole cache in $O(1)$ with no clearing pass. Problem 946's C port uses the same stamp for its per-run "seen" markers, so each run costs only its own short walk. Problem 887 is the opposite case, and the same rule explains it. It sums over every bound $d$ with a single memo, created in solve() and shared across the whole loop over $d$. That is sound because $d$ never hides in the function: it enters only as the starting slack, which is part of the key. A table can outlive a loop iteration exactly when everything that iteration changes is in the key.

How to reason about it

  • Estimate the hit ratio first. Calls divided by distinct arguments. If you cannot see why that ratio is large, memoization is not your optimisation.
  • Choosing the arguments is choosing the state. Every parameter joins the key: a redundant one multiplies the table, a missing one is a correctness bug, and two spellings of the same state (canonical form — an unsorted tuple, 1 versus 1.0) split entries that should have merged. To find the key, ask what fixes the result, not what describes it. Problem 943's subtrees look like they depend on (value, height), but they actually depend on a parity mask as well.
  • Leave a parameter out of the key only if the stored value cannot depend on it. Problem 551's jump takes a step limit so it can stop exactly on step $n$. Putting limit in the key would destroy the hit rate. So the solution stores only jumps that completed, where the limit never bound, and reuses a hit only when its step count fits under the current limit. Only the $O(k)$ calls on the final, truncated path miss. Problem 829 handles a bound the other way. Each shape caches every number of that shape up to the largest bound asked so far, with the bound stored beside the list. A smaller request is a binary search into the list, and only a larger one recomputes. Both obey the same rule: when the result is monotone in a parameter, store the parameter with the result, not in the key.
  • Let the base cases bound the key space. An argument that can grow without limit does not have to make the table grow too. Problem 887's tree capacity $F(h, c)$ recurses with a right-hand slack of $c - 1 + F(h-1, c-1)$, which grows exponentially. But once $c \ge h$ the constraint stops binding and $F = 2^h$, so that base case returns before touching the table. Only states with $0 < c < h$ are ever stored, $O(H^2)$ of them for $H = O(\log N)$, and the whole computation uses a few hundred entries. Look for the point where an argument saturates and stop there, so the saturated values never become keys.
  • Prefer an array when the keys are small integers. A dict is the general answer; an indexed array is the fast one, and in C it is usually the only one you get without writing a hash table yourself.
  • Never mutate what the cache handed you — the stored object is shared with every future hit. Returning an immutable value removes the hazard. The reverse hazard is the cache changing under a reader. Problem 829's C port reads a shape's cached list while computing a sibling. When the two subshapes are the same, that computation can grow and free the very list being read. Python keeps the old list alive while it is referenced, but C does not, so the port copies the list first.
  • Top-down memoization is still recursion, with Python's ~1000-frame limit and a frame's cost per miss. If every state will be visited anyway, a bottom-up table (problem 78) or a walk with back-propagation (problem 74) is faster and cannot overflow; top-down wins when the reachable state space is much smaller than the nominal one.
  • The table is your memory profile. Entries are the state space, and the state space is the complexity. A healthy hit rate on a still-slow program means the recurrence is wrong, not the cache — problem 76's naive partition recursion and Euler's pentagonal recurrence are both fully memoised and a thousandfold apart (reduce before coding).

Problems28 / 28

  • ● 0014 — Longest Collatz Sequence
  • ● 0017 — Number Letter Counts
  • ● 0021 — Amicable Numbers
  • ● 0060 — Prime Pair Sets
  • ● 0074 — Digit Factorial Chains
  • ● 0076 — Counting Summations
  • ● 0077 — Prime Summations
  • ● 0078 — Coin Partitions
  • ● 0092 — Square Digit Chains
  • ● 0103 — Special Subset Sums: Optimum
  • ● 0115 — Counting Block Combinations II
  • ● 0153 — Investigating Gaussian Integers
  • ● 0161 — Triominoes
  • ● 0259 — Reachable Numbers
  • ● 0301 — Nim
  • ● 0463 — A Weird Recurrence Relation
  • ● 0549 — Divisibility of Factorials
  • ● 0551 — Sum of Digits Sequence
  • ● 0641 — A Long Row of Dice
  • ● 0755 — Not Zeckendorf
  • ● 0787 — Bézout's Game
  • ● 0829 — Integral Fusion
  • ● 0887 — Bounded Binary Search
  • ● 0935 — Rolling Square
  • ● 0943 — Self Describing Sequences
  • ● 0946 — Continued Fraction Fraction
  • ● 0949 — Left vs Right II
  • ● 1000 — Problem $1000$