python 41 lines · 8 steps

Memoizing number theory with lru_cache

Three cached functions share a divisor-sum core to compute perfect numbers and aliquot chains without redundant work.

Explained by highlit

Intermediate memoization number-theory caching recursion decorators

1from functools import lru_cache
2import math
3 
4 
5@lru_cache(maxsize=None)
6def divisor_sigma(n: int) -> int:
7    total = 0
8    for d in range(1, int(math.isqrt(n)) + 1):
9        if n % d == 0:
10            total += d
11            paired = n // d
12            if paired != d:
13                total += paired
14    return total
15 
16 
17@lru_cache(maxsize=1024)
18def is_perfect(n: int) -> bool:
19    return n > 1 and divisor_sigma(n) - n == n
20 
21 
22@lru_cache(maxsize=256)
23def aliquot_chain(start: int, depth: int = 16) -> tuple[int, ...]:
24    chain = [start]
25    current = start
26    for _ in range(depth):
27        nxt = divisor_sigma(current) - current
28        if nxt in chain or nxt <= 0:
29            chain.append(nxt)
30            break
31        chain.append(nxt)
32        current = nxt
33    return tuple(chain)
34 
35 
36def cache_report() -> dict[str, object]:
37    return {
38        "divisor_sigma": divisor_sigma.cache_info(),
39        "is_perfect": is_perfect.cache_info(),
40        "aliquot_chain": aliquot_chain.cache_info(),
41    }

01 / 01

STEP 01

Walkthrough

Space play ←→ step click any line

Three takeaways

1Caching a shared low-level function lets higher-level functions reuse its results for free.
2Iterating only to the square root and pairing divisors halves the work of summing factors.
3lru_cache requires hashable arguments and returns, which is why the chain is returned as a tuple.

Related explainers

python

from collections.abc import MutableMapping
 
 
class CaseInsensitiveDict(MutableMapping):

Building a case-insensitive dict in Python

data structures abstract base classes dunder methods

Intermediate 8 steps

python

from fastapi import FastAPI, Request, status
from fastapi.encoders import jsonable_encoder
from fastapi.exceptions import RequestValidationError
from fastapi.responses import JSONResponse

Redacting sensitive fields in FastAPI errors

validation error-handling security

Intermediate 7 steps

typescript

type Masker = (value: string) => string;
 
const maskEmail: Masker = (value) => {
  const [local, domain] = value.split("@");

Recursively masking sensitive data for logs

recursion regex data-masking

Intermediate 9 steps

ruby

def render_table(rows)
  return "(no data)" if rows.empty?
 
  columns = rows.flat_map(&:keys).uniq

Rendering an ASCII table in Ruby

text-formatting column-alignment recursion

Intermediate 8 steps

func UserDashboardCache(rdb *redis.Client, ttl time.Duration) gin.HandlerFunc {
	return func(c *gin.Context) {
		claims, ok := c.Get("claims")
		if !ok {

Per-user response caching in Gin with Redis

middleware caching redis

Advanced 9 steps

python

from datetime import timedelta
 
from flask import Blueprint, current_app, make_response, redirect, request, url_for
from itsdangerous import URLSafeTimedSerializer, BadSignature, SignatureExpired