I solved a Project Euler problem (I won't say which one) involving the Partition Function P.
I used equation #11 from the above link:
$$P(n) = \sum_{k=1}^n (-1)^{k+1}\bigg(P\Big(n-{1\over 2}(3k-1)\Big)+P\Big(n-{1\over 2}(3k+1)\Big)\bigg)$$
As I was looking through the answer thread for the problem, I saw one person's comment that said:
[My algorithm] looks almost identical to [another user]'s, except my loop runs while $k \leq \sqrt n$ instead of $k \leq n$.
When $k > \sqrt n$, the values of $n_1$ and $n_2$ will both always be less than $0$.
-> $P(n_1)$ and $P(n_2)$ will always result in $0$
-> the value of $Pn$ will not change any more
It was established in an earlier post that:
- $n_1 = n-{1\over 2}(3k-1)$
- $n_2 = n-{1\over 2}(3k+1)$.
- $Pn$ is the running sum of all the calls to $P(n_1) + P(n_2)$.
My question is, why will the values of $n_1$ and $n_2$ be less than $0$ when $k \gt \sqrt n$?