Sums of Fours and Fives

Combinatorics · Medium · Free problem

How many positive integers from

$ to
000$ can be written as $4a + 5b$ for some non-negative integers $a$ and $b$?

In other words, which numbers can you make using only $4$s and $5$s (with repetition)?

Hints

  1. Since $\gcd(4,5) = 1$, every sufficiently large integer is representable as $4a + 5b$. What is the threshold?
  2. The Frobenius number for two coprime integers $a, b$ is $ab - a - b$. For $4$ and $5$, this gives
    1$ -- so every integer $\geq 12$ works.
  3. You just need to check which integers from
    $ to
    1$ can be written as $4a + 5b$ and count the failures.

Worked Solution

How to Think About It: This is a classic "coin problem" (also called the Frobenius/Chicken McNugget problem). You have two denominations -- $4$ and $5$ -- and you want to know which totals are reachable. Since $\gcd(4, 5) = 1$, every sufficiently large integer is representable. The Frobenius number for two coprime integers $a, b$ is $ab - a - b$, which here gives $4 \cdot 5 - 4 - 5 = 11$. So every integer $\geq 12$ is representable. But we need to be careful: not every integer from

$ to
1$ is representable, so we have to check those by hand.

Quick Estimate: There are

000 - 12 + 1 = 989$ integers from
2$ to
000$, all representable. Below
2$, we can quickly list the representable ones: $4, 5, 8, 9, 10$. That is $5$ more. So the answer is roughly $989 + 5 = 994$.

Approach: Enumerate all integers from

$ to
1$ and check which are representable as $4a + 5b$ with $a, b \geq 0$. Then add all integers from
2$ to
000$.

Formal Solution:

Since $\gcd(4, 5) = 1$, by the Chicken McNugget theorem, every integer

Loading problems...
gt; 4 \cdot 5 - 4 - 5 = 11$ can be written as $4a + 5b$ for non-negative integers $a, b$. So every integer from
2$ to
000$ is representable.

Now check

$ through
1$:

| $n$ | Representable? | How? | |-----|---------------|------| | 1 | No | -- | | 2 | No | -- | | 3 | No | -- | | 4 | Yes | $4 = 4(1) + 5(0)$ | | 5 | Yes | $5 = 4(0) + 5(1)$ | | 6 | No | -- | | 7 | No | -- | | 8 | Yes | $8 = 4(2)$ | | 9 | Yes | $9 = 4(1) + 5(1)$ | | 10 | Yes |

0 = 5(2)$ | | 11 | No | -- |

Non-representable values below

2$: $\{1, 2, 3, 6, 7, 11\}$ -- that is $6$ values.

Representable values:

000 - 6 = 994$.

Alternatively: representable values from

$-
1$ are $\{4, 5, 8, 9, 10\}$ (5 values), plus all $989$ values from
2$-
000$, giving $5 + 989 = 994$.

Answer: $\boxed{994}$

Intuition

This is an instance of the Frobenius coin problem: given two coprime denominations $a$ and $b$, the largest integer that cannot be represented as a non-negative combination is $ab - a - b$. The key insight is that coprimality guarantees eventual representability -- once you can hit every residue class modulo one of the denominations, you can reach everything above a threshold. For $4$ and $5$, the residues modulo $4$ are covered by $0 \cdot 5 \equiv 0$,

\cdot 5 \equiv 1$,
\cdot 5 \equiv 2$, $3 \cdot 5 \equiv 3$ (mod $4$), so once you are high enough to subtract enough $5$s and still stay non-negative, you are fine.

In quant interviews, this type of problem tests whether you recognize a number theory pattern quickly and can handle edge cases systematically. The practical analog shows up whenever you are working with discrete lot sizes or tick sizes -- understanding which quantities are achievable matters for order sizing and hedging with discrete instruments.

Open the full interactive solver →