Last updated May 13, 2025
The question
How many hexadecimal color codes contain digits that add to a given sum?
I wondered this while playing The Password Game. The game tells you the digits in your password must add to 25, then asks you to include a bunch of things that could add digits, like the hex code of a randomly-chosen color. You can have it choose a new color as many times as you like, so I wanted to estimate how long it would take to find one that wouldn't send me over 25. I wrote a script to calculate the sum of each color code by brute force, but I became curious how I could find the number of codes with a given sum in a more elegant way.
Background and research
Combinations are the building blocks of these "count how many ways there are to do something" problems:
- If you have \(n\) things, there are \(n\) ways to choose one of them.
- If you have \(n\) of one thing and \(m\) of another thing, there are \(n \times m\) ways to choose one of each.
- If you have 5 shirts and 4 pairs of pants, there are \(4 \times 3=12\) outfits you can make.
- Since there are 16 choices \(\{\text{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}\}\) for each of the 6 characters in a hex code, there are \(16^6=16,777,216\) hex codes. (\(16 \times 16 \times 16 \times \dots\))
- If you have \(n\) things, there are \(\binom{n}{r}\) ways to choose \(r\) of them.
- If you have 6 necklaces and want to wear 2 of them, there are \(\binom{6}{2}=15\) choices of which two you will wear.
- On calculators like Desmos, you would type this as nCr(6, 2)
- You can calculate combinations by hand as well.
Knowing that counting problems are quite well-studied because of gambling, I tried thinking of my question as a dice game, which proved useful. I found a formula for the number of ways to get \(n\) points when rolling dice, where \(k\) is the number of dice and \(s\) is the number of sides per die:
\[\begin{equation}\sum_{j=0} ^{\lfloor (n-k)/s \rfloor} (-1)^j \binom{k}{j} \binom{n-sj-1}{k-1}\end{equation}\]
I later learned that the "ways to get \(n\) points on (\k\) \(s\)-sided die" are known as compositions of \(n\) into \(k\) parts, restricted to parts no greater than \(s\)—or for \(s=9\), the number of ways for (\k\) nonzero digits to have a sum of \(n\).
The answer
The number of hex codes with a sum \(n\) can be calculated as:
\[\begin{equation}\sum_{k=0} ^{6} 7^{6-k} \binom{6}{k} \sum_{j=0} ^{\lfloor (n-k)/9 \rfloor} (-1)^j \binom{k}{j} \binom{n-9j-1}{k-1} \end{equation}\]
where \(7^{6-k}\) is the number of ways to choose \(6-k\) characters from \(\{\text{0, A, B, C, D, E, F}\}\); \(\binom{6}{k}\) is the number of ways to choose at which positions in the hex code they appear, and the rest is the number of ways to fill the remaining \(k\) positions with nonzero digits that add to \(n\).
Why it works
I'll start with the part based on equation (1). To find how many ways there are to write 5 as the sum of 2 positive integers, we can visualize a row of 5 stones. To divide them into 2 parts, we would need 1 stick, placed in one of the 4 spaces between stones. Dividing \(n\) stones into \(k\) parts is the same as choosing \(k-1\) of the \(n-1\) spaces between stones, or \(\binom{n-1}{k-1}\).
If we want to divide 11 into two parts, the above says there are \(\binom{11-1}{2-1}=10\) ways to do it, which is correct. However, two of these ways are \(10+1\) and \(1+10\), and in the hex code problem we only want digits that add to 11. We'll need to subtract any ways that include parts of more than 9.