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

Related explainers

ruby 
class ReportGenerator
  def initialize(account, period)
    @account = account
    @period = period

Memoized report metrics in Ruby in Rails

memoization query-composition service-object
Intermediate 7 steps
typescript 
import {
  createParamDecorator,
  ExecutionContext,
  UnauthorizedException,

Building a @CurrentUser decorator in NestJS

decorators authentication request-context
Intermediate 6 steps
python 
import re
from collections import defaultdict
from pathlib import Path
 

Summarizing log files by date in Python

regex parsing aggregation
Intermediate 7 steps
python 
import threading
import logging
 
logger = logging.getLogger(__name__)

A self-rescheduling periodic task in Python

threading scheduling concurrency
Intermediate 6 steps
php 
<?php
 
namespace App\Services;
 

Caching tenant dashboard metrics in Laravel

caching multi-tenancy aggregation
Intermediate 7 steps
python 
from collections import ChainMap
from functools import reduce
from typing import Any, Iterable, Mapping
 

Five ways to merge dicts in Python

dictionaries merging recursion
Intermediate 8 steps

Share this explainer

Here's the card — post it anywhere.

Memoizing number theory with lru_cache — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code