Closed form of recurrence with two inputs

Question

This question comes from a relatively simple coding challenge at Codesignal, but represents an interesting CS/math puzzle. The question states:

"When a candle finishes burning it leaves a leftover. m leftovers can be combined to make a new candle, which, when burning down, will in turn leave another leftover.

You have c candles in your possession. What's the total number of candles you can burn, assuming that you create new candles as soon as you have enough leftovers?"

So the inputs are the number of starting candles and how many burned candles can be reused recursively to make new candles.

Now, I solved this with a while loop, and the loop itself just involves division and modulo math:

def candles(c, m):
    
    burned=c
    while c>=m:
        burned+=c//m
        c=(c%m)+c//m
    return burned

But many of the other solutions go straight to closed form (which is obviously better in terms of complexity). I tried to figure out how they were reaching this by writing out a recurrence relation, but I can't do it... Here's an example of an accepted solution:

return c + (c - 1) // (m - 1)

I was hoping someone could help me figure out what techniques are used to arrive at this solution.

Answer 1

In order to prove the closed form you have to think in a different way about the consuming $m$ candles and adding a new one. Notice that if you break down the $(n-1)//(m-1)$ part into an iterative approach you basically subtract $m$ raise your counter of possible candles by $1$ and add $1$ back to the number you subtracted from, hence you don't subtract $m$ but actually $m-1$ (it is like taking $m$ candles and adding $1$ directly back). Now why do we use $n-1$ then? Well in order to do the above trick with subtracting $m-1$ instead of $m$ we still need to ensure that there are $m$ candles left e.g. if $m = 3$ and $n=6$ you would end up with
$6 - 3 = 3 (\text{1 candle possible});\\ 3+1 = 4;\\ 4-3 = 1 (\text{2 candles possible});\\ 1+1 = 2 (\text{finished})$.
Now if we merge the subtract 3 and add 1 operation we could just do $6 - 2 = 4 (\text{1 candle possible});\\ 4-2 = 2 (\text{2 candles possible});\\ 2 - 2= 0 (\text{3 candles possible})$
Notice that we get the wrong result cause in the last step we subtract $m-1$ instead of checking that the result is $\geq m$. To ensure that this doesn't happen we use $n-1$. You could write the closed form as iterative program and slowly transform it:

def candles(n,m):
  burned = n
  while n >= m:
    n -= m
    burned += 1
    n += 1
  return burned

def candles(n,m):
  burned = n
  while n >= m:
    n -= (m-1)
    burned += 1
  return burned

def candles(n,m):
  burned = n + (n-1)//(m-1)
  return burned

Answer 2

The candle burning rules are as follows: if you have c>=m candles, you can remove (m-1) of them and score m points while doing so. If you have fewer than c<m candles, then you score c points and are then done.

The total number of points you can score are then the points you score at the end (c % (m-1)), and the number of points you score before then (m * (c // (m-1))).