Closed formula for Pokémon Go evolutions

Question

In the game Pokémon Go, you need a fixed number of candies to evolve one Pokémon belonging to a given species. However, when you transfer the evolved Pokémon, it gives you one candy back. For instance, a pidgey costs 12 candies to evolve. If you start with 498 such candies, you can evolve 41 pidgeys on the first round, 3 on the second round, and 1 on the last round, resulting in 45 evolutions.

I can easily write an iterative algorithm to calculate that:

def evolve_and_transfer(candies, evolution_cost):
    result = 0
    i = 1
    while candies >= evolution_cost:
        (evolutions, candies) = divmod(candies, evolution_cost)
        print("Round %s: %s evolutions, %s candies remain." % (i, evolutions, candies))
        candies += evolutions
        result += evolutions
        i += 1
    return result

assert evolve_and_transfer(498, 12) == 45

But I wonder whether there exists a closed formula which calculates the same function, and could be implemented without loops.

Answer 1

With:

• $E$ = number of evolutions;
• $A$ = initial number of candies;
• $N$ = evolution cost;

Then:

$$ E = \begin{cases} 0 & \text{if $A=0$}\\ \lfloor\frac{A-1}{N-1}\rfloor & \text{otherwise} \end{cases} $$

Answer 2

Took a little longer than a few hours ;P

As I said in the comments, Perdu's formula

$$ E = \begin{cases} 0 & \text{if $A=0$}\\ \left\lfloor\frac{A-1}{N-1}\right\rfloor & \text{otherwise} \end{cases} $$

is correct. The basic idea here is as follows:

• If you have at least $N$ candies, then you are permitted to evolve at least once, for an effective cost of $N-1$ candies.
• If you have at least $2N-1=(N-1)+N$ candies you are allowed to evolve at least twice: use the $+N$ candies first, receive $+1$ additional candy, and then use the remaining $(N-1)+1=N$ candies to evolve once more, for an effective cost of $2N-2$ candies.
• If you have at least $3N-2=(2N-2)+N$, you are allowed to evolve at least three times: use the $+N$ candies first, receive $+1$ additional candy, and then repeat the procedure in the previous step, for an effective cost of $3N-3$ candies.

This looks like a recursive process, so you use induction to show that if you have at least $E(N-1)+1$ candies, you can perform at least $E$ evolutions for an effective cost of $E(N-1)$ candies. [This argument is not hard, but it's also basically the same argument I made in the third bullet point, so I'll skip it.]

It follows that if you want to have exactly $E$ evolutions, you need to be able to evolve at least $E$ times, but not at least $E+1$ times, which means that $$ E(N-1)+1\leq A<(E+1)(N-1)+1. $$ This is equivalent to $$ E\leq \frac{A-1}{N-1}<E+1, $$

and that is precisely what the notation $E=\left\lfloor\frac{A-1}{N-1}\right\rfloor$ means.

---

Why does the $A=0$ case fail in this chain of reasoning? Well, our base case on the induction starts at $E=1$, which means that you cannot substitute $E=0$ into the double inequality. Thus cannot get the desired lower bound, and so you have no guarantee that the floor function describes the situation. So in fact we have to handle the case $A<N$ separately, but of course the problem tells us that in this case (including $A=0$), we cannot evolve at all; that is, $E=0$.

It is convenient that for $0<A<N$, zero happens to be equal to $\left\lfloor\frac{A-1}{N-1}\right\rfloor$, so that we can hide this corner case in the notation, but alas, the $A=0$ subcase still requires special treatment.

---

Amusing consequence:

Proposition. Fix $N$ and $A$ positive integers, and let $a_n$ be a sequence defined by $a_0=A$ and $$a_{n+1} = a_n - (N-1)\left\lfloor\frac{a_n}{N}\right\rfloor$$ Then $$\sum_{n=0}^\infty \left\lfloor\frac{a_n}{N}\right\rfloor = \left\lfloor\frac{A-1}{N-1}\right\rfloor.$$

Proof: the sequence $a_n$ is the number of candies left after performing $n$ rounds of evolutions, and hence both sides count the number of evolutions.