# How many numbers from $1$ to $1000$ can be written as the sum of $4$s and $5$s?

I like the numbers $$4$$ and $$5$$. I also like any number that can be added together using $$4$$s and $$5$$s. Eg, $$9 = 4+5 \qquad 40 = 5 + 5 + 5 + 5 + 5 + 5 + 5 +5$$ How many number have this property from 1 to 1000?

Multiples of $$4$$s and $$5$$s are easy, but how do I calculate the number of numbers from different combinations of adding $$4$$ and $$5$$? (And which ones are different from multiples of $$4$$ and $$5$$?)

• What have you tried? Have you looked at the frobenius coin problem?en.wikipedia.org/wiki/Coin_problem#n_=_2 as that gives you an easy lower bounds Commented Nov 26, 2019 at 22:09
• Just apply sylvester's formula. And theck the remaining numbers by hand
– user727263
Commented Nov 26, 2019 at 22:19
• One thing. If $N \ge 12$ the $N = 4*k + r$ where $k \ge 3$ and $r= 0,1,2,3$. ANd $N = 4*(k-r) + 5*r$. And and $k-r \ge 3-r \ge 0$ this can be done.... if $N \ge 12$. Commented Nov 26, 2019 at 22:40

From the coin problem for $$n=2$$ we see that any number greater than 11 has this property, checking through 11 we have 4,5,8,9,10.

That would suggest 5+989 = 994 if I did my arithmetic right. The 6 that can't are 1,2,3,6,7,11

• +1 for the solution Commented Nov 26, 2019 at 22:20

It's rather easy. Let $$a$$ be the number of "4s" and let $$b$$ be the number of "5s".

You are looking for any number $$x$$ such that:

$$x = 4a + 5b \leq 1000,$$

with $$a, b \in \{0, 1, 2, \ldots\}$$.

Of course, one can notice that $$a \leq 250$$ and $$b \leq 200$$.

A simple MATLAB script can be used to find how many "$$x$$" satisfies these properties:

list = [];
for a=0:250
for b=0:200
x = 4*a + 5*b;
if (x <= 1000)
list = [list; x];
end
end
end

list = unique(list); % remove duplicate entries
count = numel(list); % how many numbers are in the list now?

fprintf('We found %d numbers which met the desired properties!\n', count);


My computer returned $$995$$ numbers in this form. Discarding the case $$a=0$$ and $$b=0$$, we get $$994$$ numbers.

The numbers $$x \leq 1000$$ which do not satisfy the requirements are: $$1, 2, 3, 6, 7$$ and $$11$$.

• @KitterCatter you are right. There are duplicate numbers. I've update the code to avoid such situation. In this case, I get 986 numbers. Commented Nov 26, 2019 at 22:17
• @KitterCatter thanks again. I've fixed this. Commented Nov 26, 2019 at 22:20
• perfect :) thanks! Commented Nov 26, 2019 at 22:23
• $8=4+4$ satisfies the conditions of the problem but $11$ does not. Commented Nov 26, 2019 at 22:36
• Uh,.... $8 = 4+4$..... that should be okay Commented Nov 26, 2019 at 22:37

But notice. If $$K = 4m + 5n$$ is such number then $$K+4 = 4(m+1)+5n$$ is such a number and all $$K + 4a = 4(m+a) + 5n$$ will be such numbers.

$$12 = 3*4$$ and $$13=2*4 + 5$$ and $$14=4+2*5$$ and $$15=3*5$$. So every $$12 + 4a$$ and $$13+4b$$ and $$14+4b$$ and $$15+4c$$ will be such numbers And that is every number greater than or equal to $$12$$.

The hard part is finding out that $$11$$ is the largest that can't be done.

ANd then counting that the ones that are less than $$11$$ than can be done are $$4; 8=2*4; 5;9=5+4;10=2*5$$ and all the others $$1,2,3,6,7,11$$ cant be done.

So that is $$6$$ that can't be done and all the rest that can. So $$994$$.

.....

Another way.... harder, but more intuitive for me....

If $$N = 4k + r$$ where $$r=0,1,2,3$$ is the remainder. We can do $$N = 4k+r = 4k-4r + 5r = 4(k-r)+5r$$ provided that $$k \ge r$$.

So if $$k=0$$ then we can't do this. If $$k=1$$ then if $$r \le 1$$, i.e. if $$N=4*1+0 =4$$ or $$N = 4*1 + 1 = 0*1 + 5$$, we can do this. but we can't do this if $$k=1$$ and $$r=2,3$$ i.e. if $$N =4*1 +2=6$$ and $$N = 4*1 + 3 = 7$$.

In $$k=2$$ and $$r\le 2$$ we can do this. $$N=4*2+ 0 =8; N=4*2 + 1=4*1 + 5 = 9$$; and $$N=4*2 +2 = 4*0 + 2*5$$. But if $$r=3$$ we can not; $$N=4*2+3=4*1 +5*1+2 = 4*0 +5*2+1$$ can not be done.

But if $$k \ge 3$$ and $$r \le 3$$ we can do it and that is the case for all $$N \ge 12$$.