Skip to content

Integers up to 1000 built from fours and fives

Question

How many integers from 11 to 10001000 can be expressed as a sum of one or more terms, each equal to 44 or 55 (for example 21=4+4+4+4+521=4+4+4+4+5)?

Short answer

994994. Since gcd⁡(4,5)=1\gcd(4,5)=1, every integer from 4⋅5−4−5+1=124\cdot5-4-5+1=12 upward is representable (Frobenius number 1111). Checking below 1212, the failures are 1,2,3,6,7,111,2,3,6,7,11, so 1000−6=9941000-6=994 work.

Adapted from QuantQuestions.io; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question