Difficult Running Time

From: Robert Jacobson (rljacobson_at_gmail.com)
Date: 11/22/04 

Date: 21 Nov 2004 17:56:06 -0800

I am writing a paper about the unrestricted partition function p(n).
One method of determining the parity of p(n) is to use the following
recurrence:

p(4n) === p(n) + p(n - 7) + p(n - 9) + ... + p(n - a_i) + ... (mod 2),
p(4n + 1) === p(n) + p(n - 5) + p(n - 11) + ... + p(n - b_i) + ... (mod
2),
p(4n + 3) === p(n) + p(n - 3) + p(n - 13) + ... + p(n - c_i) + ... (mod
2),
p(4n + 6) === p(n) + p(n - 1) + p(n - 15) + ... + p(n - d_i) + ... (mod
2),

where a_i = i(8i +/- 1), b_i = i(8i +/- 3), c_i = i(8i +/- 5), d_i =
i(8i +/- 7).

Now p(N)=0 for all N<0, so all we need to compute the parity is a few
base cases:
p(0)=1===1 (mod 2)
p(1)=1===1
p(2)=2===0
p(3)=3===1
p(4)=5===1
p(5)=7===1
p(6)=11===1
.
.
.

I'm having a little difficulty determining the running time of this
algorithm. Thinking of the recursion as a tree, the branching factor is
initially O( sqrt(n) ), and the depth of the tree is O( log_4(n) ),
but. . . I get stuck from here. One approach might be to make a
convenient simplification (for the sake of determining an upper bound
on running time) and assume that

p(4n) = p(n) + p(n) + ... + p(n)

for O( sqrt(n) ) copies of p(n). This way, at the mth level on the
tree, each node has (1/4^m)^(1/2) children. Or something like that.
Any thoughts?