Strange stair climbing

A solution can be: $\sum_{k=2}^{15} Coefficient[(x^{23}+x^{19}+x^{17}+x^{13}+x^{11}+x^7+x^5+x^3+x^2)^k, x^{30}] = 36039$

If $X_n$ is the number of ways of climbing $n$ steps, then the equations $X_0 = 1 \qquad X_1 = 0 \qquad X_n \; = \; \sum_{p \le n} X_{n-p}$ determine the sequence $X_n$ , where the symbol $p$ denotes that we are summing over primes $p$ less than or equal to $n$ .

The formula

X[n_] := Total[X[n - #] & /@ Table[Prime[r], {r, 1, PrimePi[n]}]]

together with $X[0] = 1$ and $X[1] = 0$ in Mathematica can be used to yield the following list of the first $31$ values $X_0,X_1,\ldots,X_{30}$ :

$\{1, 0, 1, 1, 1, 3, 2, 6, 6, 10, 16, 20, 35, 46, 72, 105, 152, 232, 332, 501, 732, \\ 1081, 1604, 2352, 3493, 5136, 7595, 11212, 16534, 24442, 36039\}$

The answer is $\boxed{36039}$ .

The solution can be found as follows...

If $f(n)$ is the number of ways she can climb up $n$ stairs, then it is easy to see that the first few number of ways are: $f(1) = 0, f(2) = 1, f(3) = 1, f(4) = 1, f(5) = 3$ . For higher values of $n$ you can use the following formula: $f(n) = f(n-2) + f(n-3) + f(n-5) + ...$ where you keep subtracting primes until you get to a number less than one (and stop just before you get to it). This is because on the $n$ th stair she must have come from one of the stairs $n-p$ where $p$ is a prime number

From this, you can determine that $f(30) = \boxed{36039}$