Binomial number system

I just stumbled across the binomial number system in Exercise 5.38 of Concrete Mathematics. The exercise asks the reader to show that every non-negative integer n can be written as

and that the representation is unique if you require 0 a <b <c. The book calls this the binomial number system. I skimmed a paper that said this has some application in signal processing, but I haven't looked at it closely [1].

You can finda,b, andc much as you would find the representation in many other number systems: first find the largest possible c, then the largest possibleb for what's left, and then the remainder isa.

In order to findc, we start with the observation that the binomial coefficientC(k, 3) is less thank^3/6 and soc is less than the cube root of 6n. We can use this as an initial lower bound onc then search incrementally. If we wanted to be more efficient, we could do some sort of binary search.

Here's Python code to finda,b, andc.

from math import comb, factorialdef lower(n, r): "Find largest k such that comb(k, r) <= n." k = int( (factorial(r)*n)**(1/r) ) # initial guess while comb(k, r) <= n: k += 1 return k - 1 def binomial_rep(n): c = lower(n, 3) cc = comb(c, 3) b = lower(n - comb(c, 3), 2) bb = comb(b, 2) a = n - cc - bb assert(c > b > a >= 0) return (a, b, c)

For example, here's the binomial number system representation of today's date.

>>> binomial_rep(20250605)(79, 269, 496)>>> comb(496, 3) + comb(269, 2) + comb(79, 1)20250605

You could use any number of binomial terms, not just three.

[1] I looked back at the paper, and it is using a different kind of binomial number system, expressing numbers as sums of fixed binomial coefficients, not varying the binomial coefficient arguments. This representation has some advantages for error correction.

The post Binomial number system first appeared on John D. Cook.