Project Euler Problem 709
Every day for the past n days Even Stevens brings home his groceries in a plastic bag.
Solution
Answer: 773479144
The packing process corresponds to counting increasing rooted forests where each bag contains an even number of child bags. Let $F(x)$ be the exponential generating function for $f(n)$.
Using the combinatorial specification, one obtains
$$F(x)=\sec x+\tan x,$$
whose coefficients are the Euler zig (up/down) numbers. This matches the checks:
- $f(4)=5$
- $f(8)=1385$
Computing the coefficient for $n=24680$ modulo $1020202009$ gives:
Answer: 773479144