0
$\begingroup$

Suppose we have a set of integers $\{a_1,a_2\dots,a_n\}$. with the property that any integer number is of the form $c_1a_1+c_2a_2\dots+ c_n a_n$ with all the $c's being non-negative integers.

The property I am asking for is the following: what is the name of the sets $\{a_1,a_2,\dots a_n\}$ such that the representation of any integer that has the least sum $c_1+c_2\dots c_n$ is the one that always puts the largest numbers possible.

For example: the system $1,2,4,8,16$ fits the bill since the one that uses less sumands is the one where we take as many 16's first, then as many 8's and so on.

I found what I was looking for here: https://math.stackexchange.com/a/200788/33907

Now I would like to know what number theoretical properties the set $\{a_1,a_2\dots,a_n\}$ must have to satisfy optimal substructure with regard to making change.

$\endgroup$
  • $\begingroup$ I am not able to understand what you mean. I think you need to be more precise. $\endgroup$ – Jostein Trondal Feb 5 '14 at 20:37
  • $\begingroup$ I don't think the set $(c_1,\dots,c_n)$ has a special name, but just introduce it yourself and cal it 'optimal' or something like that (if needed in a proof or something similar). $\endgroup$ – Ragnar Feb 5 '14 at 20:43
  • $\begingroup$ I found what I was looking for : math.stackexchange.com/a/200788/33907 $\endgroup$ – Jorge Fernández Hidalgo Feb 5 '14 at 20:47
  • $\begingroup$ namely I was asking for optimal substructure with regard to making change. $\endgroup$ – Jorge Fernández Hidalgo Feb 5 '14 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.