Composite values of shifted exponentials

A well-known open problem asks to show that $2^n+5$ is composite for almost
all values of $n$. This was proposed by Gil Kalai as a possible Polymath
project, and was posed originally by Christopher Hooley. We show that, assuming
GRH and a form of the pair correlation conjecture, the answer to this problem
is affirmative. We in fact do not need the full power of the pair correlation
conjecture, and it suffices to assume a generalization of the Brun-Titchmarsh
inequality for the Chebotarev density theorem that is implied by it. Our
methods apply to any shifted exponential sequence of the form $a^n-b$ and show
that, under the same assumptions, such numbers are $k$-almost primes for a
density $0$ of natural numbers $n$. Furthermore, we show that $a^p-b$ is
composite for almost all primes $p$ whenever $(a, b) \neq (2, 1)$.