Greedy coin change for powers of an integer ($\{1,p,\dots ,p^k\}$)

For an integer $p\ge 2$ and $k\ge 0$, unlimited denominations $1,p,\dots ,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.