Paying with cash - part I

If I decide to include $D$ dimes in my payment (with $0\leq D \leq 15$ ), then I have exactly $31-2D$ ways to pay up: I can use anywhere from 0 to $\frac{150-10D}{5}=30-2D$ nickels and pay the rest in pennies. Thus the answer is $\sum_{D=0}^{15} (31-2D) = 16^2 =\boxed{256}$ .

A Wolfram Mathematica 11.3 function: $\text{RationalQ}\text{:=}\text{\$\#\$1}\in \mathbb{Q}\&;$ which tests whether its argument is a rational number.

Another function: $\text{change}(\\ \text{amount\$\_\$}\text{/;}\text{RationalQ}(\text{amount}),\\ \text{coins\$\_\_\$}\text{/;}\text{AllTrue}[\text{coins},\text{RationalQ}]\land \text{AllTrue}[\text{coins},\text{Positive}])\\ \text{:=}\\ \text{Block}[\{c,\text{amt},\text{tokens}\},\\ c(\text{amt\$\_\$},\{\})\text{:=}0\text{/;}\text{amt}\neq 0;\\ c(0,\_)\text{:=}1;\\ c(\text{amt\$\_\$},\text{tokens\$\_\$})\text{:=}0\text{/;}\text{amt}<0;\\ c(\text{amt\$\_\$},\text{tokens\$\_\$})\text{:=}c(\text{amt},\text{tokens})=\\ c(\text{amt}-\text{First}[\text{tokens}],\text{tokens})+c(\text{amt},\text{Rest}[\text{tokens}]);\\ c(\text{amount},\text{Select}[\text{Sort}[\text{Union}[\text{coins}],\text{Greater}],\text{\$\#\$1}\leq \text{amount}\&])\\ ]$

1. A function named $\text{change}$ .

2. First argument, called $\text{amount}$ , must be a rational number.

3. Second argument, called $\text{coins}$ , must be a list of positive, rational numbers,

4. is defined as

5. A local scope with two local variables, $\text{amt}$ and $\text{tokens}$ .

6. If amt is not equal to 0 and the remaining list of coins is empty, then c[amt,{}] is defined as 0

7. If amt is 0, regardless of the remaining coins, then c[0,_] is defined as 1

8. If amt < 0, then c[amt ,tokens ] is defined as 0

9. Otherwise, c[amt ,tokens ] is defined as the memo-ed value of that combination of values which is

10. sum of two invocations of c: c with the amount reduced by the first coin and the full list of coins and c with the full amount and list with the first coin dropped.

11. Invoke c with the initial and the coins sorted in descending order and the coins which are too large to be useful to be removed.

12. Close the local scope.

$\text{change}\left(\frac{150}{100},\left\{\frac{1}{100},\frac{5}{100},\frac{10}{100}\right\}\right) = 256$

$\text{change}\left(100,\left\{1000,500,100,50,20,10,5,2,1,\frac{1}{2},\frac{1}{4},\frac{1}{10},\frac{1}{20},\frac{1}{100}\right\}\right)$ is $9823546661906$ .

In words, nine trillion, eight hundred twenty-three billion, five hundred forty-six million, six hundred sixty-one thousand, nine hundred six.