Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
    
Question: if $n < 0$, is $P(n) < 0$ by definition? If so then I think you can prove by induction. If not, then perhaps they mean that $n_1 = n_2 = 0$ when $k > \sqrt{n}$, which based on my proof sketch I believe you can also prove by induction. This is all assuming that $n_1$ and $n_2$ are indeed defined as you wrote. –  august Jan 8 '13 at 21:12
    
@august Shoot... My mistake. I did define $n_1$ and $n_2$ incorrectly. Even so, if the summation goes from $k=1$ to $n$, and if $n$ is less than $1$, then, as he said, the summation will not change any more... Right? –  Matthew D Jan 8 '13 at 21:37
    
I'm not exactly sure what you're asking here. In what scenario would $n$ be less than 1? Then there is no summation, and $P(n) = 0$ by definition. In any case, in your updated definition of $n_1$ and $n_2$, they will not always be less than 0 when $k > \sqrt{n}$, and I think it is easy to see that just from plugging in a few numbers for $k$ and $n$ as counterexamples. –  august Jan 9 '13 at 20:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.