Is it true that all sufficiently large $n$ can be written as $2^k+m$ for some $k\ge 0$, where $\Omega (m)<\log \log m$? (Here $\Omega (m)$ is the number of prime divisors of $m$ counted with multiplicity.) What about $<ϵ\log \log m$? Or some more slowly growing function?