Logarithmic-Hamming-Numbers

Finds the nth Hamming number, 2ⁱ·3ʲ·5ᵏ, by counting lattice points under a plane in log space, instead of generating every number before it. The billionth, all 844 digits, takes about 11 ms with its C extension, and the 10¹⁶th takes under two minutes.

Left: the 200 lattice points under the plane i ln 2 + j ln 3 + k ln 5 ≤ B, filling a tetrahedron, with the 200th Hamming number, 16200, on its face. Right: for n of one billion, the count misses by 287, then 2, 2 and −1, then lands on n, giving 2^1334 · 3^335 · 5^404. — Drawn from the algorithm’s own counts and secant steps.

A Hamming number is a positive integer with no prime factors other than 2, 3 and 5: H = 2ⁱ · 3^j · 5^k. The classic way to find the nth one is Dijkstra’s three-pointer method, which builds the whole sequence in order. That’s fine for n in the thousands, but it takes O(n) time and memory, so the billionth is out of reach.

This takes a geometric route instead. Taking logs turns the product into a sum, i ln 2 + j ln 3 + k ln 5 ≤ B, so the Hamming numbers up to some bound are exactly the integer points inside a tetrahedron. Finding the nth one means finding the B with exactly n points under it. Counting them loops over j and k and gets the number of valid i with one division, so each count costs O(n^2/3).

The bound starts from the tetrahedron’s volume, takes one Newton step using the volume’s derivative as the slope, and then switches to the secant method on the real counts. Because the count is a step function, it brackets the answer in a narrow band, lists the few points inside it, sorts them and picks the right one.

Two C extensions do the heavy lifting. _hamming_count runs the count and the band walk in 80-bit long double, parallelized with OpenMP, which keeps the floating-point bounds reliable to at least n = 10¹⁶ (64-bit doubles are good to about 10¹²). _hamming_exact is an optional checker that recounts every point at or below the answer using exponent-weighted logs, redoing near-boundary cells in 128-bit quad precision. The Python module falls back to pure Python if the extension isn’t built.

Benchmarks

n	Digits	Logarithmic	Memory	Dijkstra	Memory
10³	8	7 µs	228 B	133 µs	38 KB
10⁴	18	14 µs	264 B	2.0 ms	422 KB
10⁵	39	37 µs	248 B	18.2 ms	5 MB
10⁶	84	141 µs	404 B	214.5 ms	63 MB
10⁷	182	505 µs	388 B	2.42 s	934 MB
10⁸	392	2.2 ms	892 B	—	—
10⁹	844	11.4 ms	9 KB	—	—
10¹⁰	1,819	17.3 ms	65 KB	—	—
10¹¹	3,920	71.2 ms	2 KB	—	—
10¹²	8,445	241.8 ms	14 KB	—	—
10¹³	18,195	1.12 s	—	—	—
10¹⁴	39,199	6.13 s	—	—	—
10¹⁵	84,453	24.43 s	—	—	—
10¹⁶	181,949	107.16 s	—	—	—

Median of repeated runs (5 up to ten million, 3 at 10⁸, a single run from 10⁹) on a Runpod CPU pod with an AMD EPYC 9575F, 8 vCPU, CPython 3.13, using the C extension; peak memory is the Python heap from tracemalloc, skipped from 10¹³. The logarithmic method is ahead at every size, about 4,800× faster than Dijkstra at ten million with some 2.4 million times less memory, and time grows roughly 4–5.5× per tenfold increase in n at the top end, close to the 4.6× that the n^2/3 cost of a count predicts. Dijkstra wasn’t run past ten million, where it already needs almost a gigabyte. Every answer was checked against Dijkstra up to 20,000 and the known values for the millionth and billionth, and every row was confirmed by the exact rank checker.

Highlights

A volume estimate, one Newton step and the secant method usually land on the bound in a handful of counts
Constant-time counting along each row of the lattice, now in a C extension that uses 80-bit long doubles and OpenMP
A second C extension, an exact rank checker with a quad-precision fallback, confirms every result up to 10¹⁶
Only the points in the final band are ever turned into big integers, with powers of two done as bit shifts
An interactive 3D Desmos graph of the tetrahedron and its lattice points

view source on GitHub → explore the 3D Desmos visualization → the Codewars kata →

Access: public
Year: 2026
Built with: Python, C, Number theory, Desmos, Codewars