This is a question about generalizations of the twin primes conjecture.

I would like to know a counterexample, or a proof, for the following couple of related arithmetical sentences. The first is

$(\forall p) Prime(p) \Rightarrow (\exists n)(\exists q)(Prime (q) \wedge (p = 2^n + q))$

More informally, if $p$ is prime, then $p$ can be written as the sum of a smaller prime $q$ and a power of $2$. The second is

$(\forall q) Prime(q) \Rightarrow (\exists n)(\exists p) (Prime(p) \wedge (p = 2^n + q))$

More informally, if $q$ is prime, then there exists a number $n$ such that the sum of $q$ and the $n$-th power of $2$ is a prime number.