Do You Like "Odd" Primes?

We claim that $p$ can only be Mersenne primes in $P$ , thus the answer is $3+7+31+127=\boxed {168}$ . Let $M=\{3,7,31,127\}$ denote the set of odd Mersenne primes under $1000$ .

Suppose $p\notin M$ . Consider when $S=M$ , then there exists a non-mersenne prime $q$ that satisfies $q+1|(3+1)(7+1)(31+1)(127+1)\implies q+1|2^{17}$ It follows that $q+1$ is a power of $2$ or $q$ is a Mersenne prime, which contradicts $q$ being non-mersenne. Hence $p\in M$ .

To show that $p\in M$ works, assume by the contrary that it does not. This means that there exists a subset $S$ such that any $q$ that satisfies the divisibility condition must be an element of $S$ . With this observation in mind, we know $3\in S$ because $4|(p_1+1)(p_2+1)...(p_k+1)$ for any odd primes $p_i$ . Similarly, $8|(3+1)(p_2+1)...(p_k+1)$ is true for odd primes $p_i$ (note that $k\ge 2$ ), therefore $7\in S$ . In the same inductive manner we can show that the rest of the Mersenne primes are elements of $S$ . However, this contradicts the assumption that $p\in M$ ; hence $p\in M$ must work.

---

What great timing that a new Mersenne prime was recently discovered!