Project Euler Problem 645
On planet J, a year lasts for D days.
Solution
Answer: 48894.2174
Let the holidays form connected blocks on a cycle of $D$ days. Rule (2) implies that once two holidays surround a gap, the whole gap collapses into holidays. Equivalently:
The set of holidays is always the cyclic convex hull of the emperor birthdays.
Thus, after enough emperors, all days become holidays exactly when the chosen birthday set is not contained in any open arc of length $D-1$.
A useful reformulation is to condition on the sequence of new birthday discoveries (ignoring repeated birthdays). One can group all emperor histories by the number $s$ of distinct birthday insertions needed to complete the year. The waiting time contributed by repeated birthdays becomes a coupon-collector–type factor.
A cubic-time dynamic program exists for counting arrangements, but the recurrence admits a closed-form coefficient. If $n=D-1$, the coefficient of the contribution with $n-1-i$ effective insertions is:
$$(2(n-1)-3i)\binom{n-1-i}{i}(n-2-i)!,$$
combined with the waiting-time factor
$$f(y,s)= \sum \text{(coupon waiting contribution)}$$
for year length $y=D$ and $s$ insertions. This reproduces the checks
$$E(2)=1,\qquad E(5)=\frac{31}{6},\qquad E(365)\approx1174.3501,$$
matching the problem statement.
Evaluating the resulting exact recurrence for $D=10000$ gives:
$$E(10000)=48894.2174\ldots$$
rounded to four decimal places.
Answer: 48894.2174