Fourth floor challenge

Couple days ago, a friend sent me this link, which has an interesting problem.

In short, there is a vending machine that tries to dispense the fewest coins necessary to meet the change. The algorithm is to always dispensing the largest denomination coin that was equal or less than the remaining change first, and then repeating the process on the remaining change amount.

The algorithm would fail if the coins are denominated in 1, 4, 5, and 9 cents. For example, to return 8 cents the machine will return 5, 1, 1, 1; but 4, 4 would be fewer coins.

So the question is from 0 to 1000 cents, how many cases would the vending machine return more coins than necessary.

First list all the cases from 1 to 25:
1 => 1
2 => 1 1
3 => 1 1 1
4 => 4
5 => 5
6 => 5 1
7 => 5 1 1
8 => 5 1 1 1 (fails, more coins than necessary)
9 => 9
10 => 9 1
11 => 9 1 1
12 => 9 1 1 1 (fails again, 4, 4, 4 is better)
13 => 9 4
14 => 9 5
15 => 9 5 1
16 => 9 5 1 1
17 => 9 5 1 1 1 (9, 4, 4 is better)
18 => 9 9
19 => 9 9 1
20 => 9 9 1 1
21 => 9 9 1 1 1 (9, 4, 4, 4 is better)
22 => 9 9 4
23 => 9 9 5
24 => 9 9 5 1
25 => 9 9 5 1 1

It is not hard to see that the failed cases either ends with 5 1 1 1 (case 8 and 17) or 1 1 1 (case 12 and 21), and they all preceded by 9, not counting the first 1 1 1 case. This can be solved with one line of Scala code.

// Scala interpreter
// So start with case 4, all the way up to case 1000
// Count any case that has either 8 or 3 as remainder when divided by 9
scala> 4 to 1000 count {x => (x % 9 == 8) || (x % 9 == 3)}