= Greedy coin change for powers of an integer
{title2=$\{1,p,\ldots,p^k\}$}
For an <integer> $p\geq2$ and $k\geq0$, unlimited denominations $1,p,\ldots,p^k$ admit optimal <greedy algorithm>. In a minimum-count solution, no smaller denomination can occur $p$ times: carrying those stamps to the next denomination reduces their count by $p-1$. Thus all counts below the maximum are base-$p$ digits, whose total value is at most $p^k-1$. The maximum-denomination count is forced to be the quotient on division by $p^k$, and repeating the argument forces every greedy remainder step.
Back to article page
