Lemoine's conjecture (also called Levy's conjecture according to Professor Wikipedia) states that every odd integer larger than $5$ is the sum of a prime and of twice a prime.

Dabbling in the dark art of numerology, one observes that every odd integer $2n+1\geq 5$ up to $10^7$ (where my computer got somewhat tired) can be written as 
$$2n+1=p+2^kq$$
with $p$ a prime, $k$ an integer
and $q$ a prime which is smaller than $\log(2n+1)$.

*Is there a larger counterexample?*

There are two natural ways to relax things a bit:

One can drop the prime-requirement for $q$ and only require $q$
to be a positive integer smaller than $\log(2n+1)$.

One can weaken the inequality $q<\log(2n+1)$ (for $q$ not necessarily prime) to $q/\log(2n+1)$ bounded for all $n$.

Data up to $10^7$:

$q=3$ is first needed for $127>e^3$ (every odd integer $\geq 3$ up to $125$
is the sum of a prime and a power of $2$),

$q=5$ is first needed for $1719>e^5$,

$q=7$ is first needed for $10001>e^7$,

$q=11$ is first needed for $118335>e^{11}$,

$q=13$ is first needed for $3965753>e^{13}$.

**Counterexample**: $q=17$ is needed for $18133279<e^{17}$. However, $q=9$ works if dropping the prime-requirement on $q$.