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$.