[Math] find the largest integer less than a number

algorithmsdynamic programmingproof-writing

I'm trying to figure out this problem for few hours now. please help.

Define $$\text{PCOM}(a,b,c) := \{ax + by + cz : x, y, z ≥ 0\}.$$

Given integers $t > c > b > a > 1,$ I need help to find the largest integer $w < t$ such that $w\notin\text{PCOM}(a,b,c).$

Example: $\text{PCOM}(3,5,7) =\{0,3,5,6,7,8,9,10,…\}.$ The largest integer less than $9$ that is not in $\text{PCOM}(3,5,7)$ is $4$.

Best Answer

This is a particularly simple variant of what is known as the coin problem. Here's a dynamic programming solution that runs in time linear in $t$. We use an array $m[0\dots t]$ of booleans, which I'll refer to as either T or F. The value of $m[i]$ will represent whether or not $i$ can be represented as the sum of zero or more copies of $a, b, c$. We will also keep a variable $w$, representing the current largest value not in $\text{PCOM}(a, b, c)$.

First, we initialize $m[0] = \text{T}$ (since we can obviously get a sum of zero by not using any of the values) and for $0 < i < a$ we set $m[i]=\text{F}$. We also initialize $w=a-1$.

Having done that, the algorithm is

for i = a to t
   m[i] = m[i - a] OR m[i - b] OR m[i - c]
   if m[i] = F
      w = i
return w

The only tweak is in the second line: if $i < b$ or $i < c$ we don't try to access the corresponding array element (since it would make no sense to do so here). There are some obvious improvements we can make in the algorithm, but I hope the idea is clear. If not, just ask.

Related Question