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

Question

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$?)

Answer 1

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

Answer 2

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.

Additional remark

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

Answer 3

Google frobenius coin problem.

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$.