But it's so large!

Let $a,b,c, d$ be the roots of the quartic $x^4+k_3x^3+k_2x^2+k_1x+k_0$ .

Define $a^n+b^n+c^n+d^n=P_n$ .

By Newton's sums, we see that: $\left\{ \begin{array}{l} P_1+k_3=0\\ P_2+k_3P_1+2k_2=0\\ P_3+k_3P_2+k_2P_1+3k_1=0\\ P_4+k_3P_3+k_2P_2+k_1P_1+4k_0=0 \end{array}\right.$ Substituting our known values in: $\left\{ \begin{array}{l} 3+k_3=0\\ 5+3k_3+2k_2=0\\ 3+5k_3+3k_2+3k_1=0\\ 9+3k_3+5k_2+3k_1+4k_0=0 \end{array}\right.$ Solving the system, we get $(k_3, k_2, k_1, k_0)=(-3, 2, 2, -4)$ Thus, the polynomial with roots $a, b, c, d$ is $x^4-3x^3+2x^2+2x-4$

Applying the Rational Root Theorem, we find that $x=-1, 2$ are roots of the quartic, and long division gives us that $x^4-3x^3+2x^2+2x-4=(x+1)(x-2)(x^2-2x+2)$ Then we apply the quadratic equation and find that the remaining two roots are $1\pm i$ .

So the roots are $(a,b,c,d)=(-1, 2, 1+i, 1-i)$ . Now we can directly compute $P_{2015}$ :

$\begin{aligned} P_{2015}&=(-1)^{2015}+2^{2015}+(1+i)^{2015}+(1-i)^{2015}\\ &= -1+2^{2015}+\sqrt{2}^{2015}\left(\dfrac{1}{\sqrt{2}}+\dfrac{1}{\sqrt{2}}i\right)^{2015}+\sqrt{2}^{2015}\left(\dfrac{1}{\sqrt{2}}-\dfrac{1}{\sqrt{2}}i\right)^{2015}\\ &= -1+2^{2015}+\sqrt{2}^{2015}\text{cis}\left(\dfrac{\pi}{4}\right)^{2015}+\sqrt{2}^{2015}\text{cis}\left(-\dfrac{\pi}{4}\right)^{2015}\\ &= -1+2^{2015}+\sqrt{2}^{2015}\text{cis}\left(\dfrac{2015\pi}{4}\right)+\sqrt{2}^{2015}\text{cis}\left(-\dfrac{2015\pi}{4}\right)\\ &= -1+2^{2015}+\sqrt{2}^{2015}\text{cis}\left(-\dfrac{\pi}{4}\right)+\sqrt{2}^{2015}\text{cis}\left(\dfrac{\pi}{4}\right)\\ &= -1+2^{2015}+2^{1007}\cdot \sqrt{2}\left(\dfrac{1}{\sqrt{2}}-\dfrac{1}{\sqrt{2}}i\right)+2^{1007}\cdot \sqrt{2}\left(\dfrac{1}{\sqrt{2}}+\dfrac{1}{\sqrt{2}}i\right)\\ &= -1+2^{2015}+2^{1007}\cdot(1-i)+2^{1007}\cdot(1+i)\\ &= 2^{2015}+2^{1008}-1 \end{aligned}$ So $(p, q, r, s)=(2, 2015, 1008, 1)$ and our final answer is $2+2015+1008+1=\boxed{3026}$

Consider the expansion $(a+b+c+d)^2 = (a^2+b^2+c^2+d^2) + 2(ab+ac+ad+bc+bd+cd)$ , upon substitution, we get $ab+ac+ad+bc+bd+cd = \frac{3^2 - 5}2 = 2$ .

Since the values of $a,b,c$ and $d$ satisfy these 4 equations and are interexchangeable, then there exist a 4th degree polynomial that have roots $a,b,c$ and $d$ . By Vieta's formula, the polynomial must be

$x^4 - 3x^3 +2x^2 + mx + n$

for unique constants $m$ and $n$ . Take its sum:

$\begin{aligned} \sum \left( x^4 - 3x^3 +2x^2 + mx + n \right) &=& 0 \\ \sum x^4 - 3 \sum x^3 + 2 \sum x^2 + m \sum x + n \sum 1 & = & 0 \\ 9 - 3(3) + 2(5) + m(3) + n(4) & = & 0 \\ 3m + 4n &=& -10 \quad (\ast) \\ \end{aligned}$

Now suppose that one of $a,b,c$ or $d$ is equals to $0$ , WLOG $a = 0$ . Then $n = 0 \Rightarrow m =-bcd= -\frac{10}3$ and by using the identity $b^3 + c^3 + d^3 - 3bcd = (b+c+d)( (b^2+ c^2+ d^2) - (bc+bd+cd))$ . We get $3 - 3\left( \frac{10}3\right) = 3\left(5 - 2\right)$ which is absurd. Thus $a,b,c,d \ne 0$ .

Thus for the equation $x^4 - 3x^3 +2x^2 + mx + n = 0$ , the division by $x$ is possible.

$\begin{aligned} \sum \left( x^3 - 3x^2 +2x + m + \frac nx \right) &=& 0 \\ \sum x^3 - 3 \sum x^2 + 2 \sum x + m \sum 1 + n \sum \frac1x & = & 0 \\ 3 - 3(5) + 2(3) + m(4) + n \sum \frac1x & = & 0 \\ 4m + n \sum \frac1x & = & 6 \quad (\ast\ast) \\ \end{aligned}$

Let $f(x) = x^4 - 3x^3 +2x^2 + mx + n$ , then $f(x)$ has roots $a,b,c,d$ . Similarly, $x^4 f\left(\frac1x\right) = 0$ has roots $\frac1a, \frac1b,\frac1c,\frac1d$ .

$x^4 f\left(\frac1x\right) = nx^4 + mx^3 + 2x^2 -3x + 1 \Rightarrow \frac1a +\frac1b+\frac1c+\frac1d = -\frac mn$

From $(\ast \ast)$ , we get $4m + n\left( - \frac mn \right) = 6 \Rightarrow m = 2$ thus from $(\ast)$ , $n = -4$ .

Hence the polynomial is $x^4 - 3x^3 +2x^2 + 2x - 4$ . With Rational Root Theorem, the two rational roots are $-1$ and $2$ by inspection. Factoring them out gives $(x+1)(x-2)(x^2-2x+2)$ . So the other two roots are $1\pm i$ by quadratic formula.

WLOG, let $a = -1, b = 2, c = 1 + i, d = 1- i$ . Then $a^{2015} = -1$ . And by De Moivre's Theorem

$\begin{aligned} c^{2015} &=& (1 + i)^{2015} \\ & =& (\sqrt2 )^{2015} \left( \frac1{\sqrt2} + i \frac1{\sqrt2} \right)^{2015} \\\ &=& 2^{2015/2} \left( \cos\left(\frac\pi4 \right) + i \sin\left(\frac\pi4 \right) \right)^{2015} \\ &=& 2^{2015/2} \left( \cos\left(\frac\pi4 \cdot 2015\right) + i \sin\left(\frac\pi4 \cdot 2015 \right) \right) \\ &=& 2^{2015/2} \left( \cos\left(\frac\pi4\right) + i \sin\left(\frac\pi4\right) \right) \\ \end{aligned}$

Analogously, $d^{2015} = 2^{2015/2} \left( \cos\left(\frac\pi4\right) - i \sin\left(\frac\pi4\right) \right)$ . So $c^{2015} + d^{2015} = 2^{2015/2} \cdot 2 \cos\left( \frac\pi4\right) = 2^{2015/2 + 1 - 1/2} = 2^{1008}$ .

Putting them all together yields $-1 + 2^{2015} + 2^{1008}$ . This suggests that $p = 2, q = 2015, r = 1008, s = 1$ . However, we need to prove that $p$ is unique.

By Euclidean Algorithm, $\gcd(2015,1008) = \gcd(1008,1007) = 1$ thus $2015$ and $1008$ don't share any common factor thus $p$ is indeed unique. Hence, our answer is $p+q+r+s= 2 + 2015 + 1008 +1 = \boxed{3026}$ .