HMMT November 2015 U36

Consider the following seven false conjectures with absurdly high counterexamples. Pick any subset of them, and list their labels in order of their smallest counterexample (the smallest $n$ for which the conjecture is false) from smallest to largest. For example, if you believe that the below list is already ordered by counterexample size, you should write "PECRSGA".

• P. (Polya's conjecture) For any integer $n$, at least half of the natural numbers below $n$ have an odd number of prime factors.
• E. (Euler's conjecture) There is no perfect cube $n$ that can be written as the sum of three positive cubes.
• C. (Cyclotomic) The polynomial with minimal degree whose roots are the primitive $n$th roots of unity has all coefficients equal to $-1,0$, or 1 .
• R. (Prime race) For any integer $n$, there are more primes below $n$ equal to $2(\bmod 3)$ than there are equal to $1(\bmod 3)$.
• S. (Seventeen conjecture) For any integer $n, n^{17}+9$ and $(n+1)^{17}+9$ are relatively prime.
• G. (Goldbach's (other) conjecture) Any odd composite integer $n$ can be written as the sum of a prime and twice a square.
• A. (Average square) Let $a_{1}=1$ and $a_{k+1}=\frac{1+a_{1}^{2}+a_{2}^{2}+\ldots+a_{k}^{2}}{k}$. Then $a_{n}$ is an integer for any $n$.

If your answer is a list of $4 \leq n \leq 7$ labels in the correct order, your score will be $(n-2)(n-3)$. Otherwise, it will be 0 .