This problem can be solved with memorized recursion.

Problem 1

Consider the following problem.

The objective is the same as the original problem, except that there are only one kind of operation allowed, as follows:

• Pay \(Y\) yen. Roll a die that shows an integer between \(2\) and \(6\) with equal probability. Replace \(N\) with \(\left\lfloor\frac{N}{b}\right\rfloor\), where \(b\) is the number shown.

Let \(f(N)\) be the sought expected value. Then,

\(f(N)=Y +\frac{1}{5}f\left(\left\lfloor\frac{N}{2}\right\rfloor\right) +\frac{1}{5}f\left(\left\lfloor\frac{N}{3}\right\rfloor\right) +\frac{1}{5}f\left(\left\lfloor\frac{N}{4}\right\rfloor\right) +\frac{1}{5}f\left(\left\lfloor\frac{N}{5}\right\rfloor\right) +\frac{1}{5}f\left(\left\lfloor\frac{N}{6}\right\rfloor\right). \)

This can be evaluated with memorized recursion. (The complexity is discussed later.)

Problem 2

Next, we consider the following problem.

The objective is the same as the original problem, except that there are only one kind of operation allowed, as follows:

• Pay \(Y\) yen. Roll a die that shows an integer between \(2\) and \(6\) with equal probability. Replace \(N\) with \(\left\lfloor\frac{N}{b}\right\rfloor\), where \(b\) is the number shown.

Let \(f(N)\) be the sought expected value. Then,

\(f(N)=Y +\frac{1}{6}f\left(\left\lfloor\frac{N}{1}\right\rfloor\right) +\frac{1}{6}f\left(\left\lfloor\frac{N}{2}\right\rfloor\right) +\frac{1}{6}f\left(\left\lfloor\frac{N}{3}\right\rfloor\right) +\frac{1}{6}f\left(\left\lfloor\frac{N}{4}\right\rfloor\right) +\frac{1}{6}f\left(\left\lfloor\frac{N}{5}\right\rfloor\right) +\frac{1}{6}f\left(\left\lfloor\frac{N}{6}\right\rfloor\right). \)

The right hand side also has \(f(N)\), so at a glance it seems it is impossible to evaluate it recursively. However, we can transpose the term to the right hand side and multiply both sides by \(\frac{6}{5}\) to get:

\(f(N)= \frac{6}{5}Y +\frac{1}{5}f\left(\left\lfloor\frac{N}{2}\right\rfloor\right) +\frac{1}{5}f\left(\left\lfloor\frac{N}{3}\right\rfloor\right) +\frac{1}{5}f\left(\left\lfloor\frac{N}{4}\right\rfloor\right) +\frac{1}{5}f\left(\left\lfloor\frac{N}{5}\right\rfloor\right) +\frac{1}{5}f\left(\left\lfloor\frac{N}{6}\right\rfloor\right), \)

which we can evaluate with memorized recursion. (The complexity is discussed later.)

Original problem

We now consider the original problem. Let \(f(N)\) be the sought expected value. Since there are two kinds of operations, it is optimal to perform the one with the smaller expected value. That is,

\(f(N)=\min\left(X+f\left(\left\lfloor\frac{N}{A}\right\rfloor\right), \frac{6}{5}Y +\frac{1}{5}f\left(\left\lfloor\frac{N}{2}\right\rfloor\right) +\frac{1}{5}f\left(\left\lfloor\frac{N}{3}\right\rfloor\right) +\frac{1}{5}f\left(\left\lfloor\frac{N}{4}\right\rfloor\right) +\frac{1}{5}f\left(\left\lfloor\frac{N}{5}\right\rfloor\right) +\frac{1}{5}f\left(\left\lfloor\frac{N}{6}\right\rfloor\right), \right)\)

which we can apply memorized recursion.

Since \(\displaystyle \left\lfloor\frac{\left\lfloor\frac{N}{a}\right\rfloor}{b}\right\rfloor=\left\lfloor\frac{N}{ab}\right\rfloor\), what we need to evaluate for the memorized recursion is those that can be written as \(f\left(\left\lfloor\frac{N}{m}\right\rfloor\right)\) for some integer \(m\) represented as \(m=2^p3^q5^r\).

Since there are at most \(O((\log N)^3)\) number of such \(m\), the overall complexity is \(O((\log N)^3)\).