in reply to
Golf: Buying with exact change

I've not followed this thread in detail so I don't know if it's already been mentioned, but this is indeed a well known mathematical (combinatorial) problem, and a "hard" one, actually called "the money changing problem".

The problem is discussed in some detail e.g. in the beautiful book *generatingfunctionology* by Prof. Wilf, available for download from http://www.math.upenn.edu/%7Ewilf/DownldGF.html

To quote from Wilf:

There are no general `formulas' for the conductor if M >= 3, and no good algorithms for calculating it if M >= 4.

(M is the number of "changes" and the "conductor" is the smallest quantity N such that all n>=N can be represented as sums of the changes. In this case the latter must be -of course- coprime.)