HMMT-Nov 2015 guts, Problem 32

Find the sum of all positive integers $n \leq 2015$ that can be expressed in the form $\left\lceil\frac{x}{2}\right\rceil+y+x y$, where $x$ and $y$ are positive integers.

Solution: Lemma: $n$ is expressible as $\left\lceil\frac{x}{2}\right\rceil+y+x y$ iff $2 n+1$ is not a Fermat Prime. Proof: Suppose $n$ is expressible. If $x=2 k$, then $2 n+1=(2 k+1)(2 y+1)$, and if $x=2 k-1$, then $n=k(2 y+1)$. Thus, if $2 n+1$ isn't prime, we can factor $2 n+1$ as the product of two odd integers $2 x+1,2 y+1$ both greater than 1, resulting in positive integer values for $x$ and $y$. Also, if $n$ has an odd factor greater than 1 , then we factor out its largest odd factor as $2 y+1$, giving a positive integer value for $x$ and $y$. Thus $n$ is expressible iff $2 n+1$ is not prime or $n$ is not a power of 2 . That leaves only the $n$ such that $2 n+1$ is a prime one more than a power of two. These are well-known, and are called the Fermat primes. It's a well-known fact that the only Fermat primes $\leq 2015$ are $3,5,17,257$, which correspond to $n=1,2,8,128$. Thus the sum of all expressible numbers is $\frac{2015 \cdot 2016}{2}-(1+2+8+128)=2029906$. $\fbox{2029906}$.

Answer: 2029906