Perhaps the following rather silly conjecture could be added. Is it true that the set of odd integers not of the form 2^k + p is the not necessarily disjoint union of an infinite arithmetic progression and perhaps a sequence of density 0?

Erdős Problem #16 — Structure of the odd numbers not of the form 2^k+p

Erdős conjectured in 1950 that the odd integers not expressible as $p+2^k$ , with $p$ prime, consist of one infinite arithmetic progression plus a density-zero set. This was Problem 16 in Bloom’s list; the representation question goes back to de Polignac in 1849.

Known results

Romanoff (1934): a positive proportion of odd integers are expressible as $p+2^k$ .
Erdős (1950): an infinite arithmetic progression of odd exceptions exists.
Chen and Sun (2004), and Elsholtz and Schlage-Puchta (2018): later quantitative progress is recorded.

December 2023 disproof and February 2024 follow-up

Chen constructed two exception progressions with modulus $11184810$ and residues $992077$ and $3292241$ . Their incompatibility disproves Erdős’s conjecture; subsequent work supplied further progressions and proved that any exception progression has modulus at least $11184810$ . Related questions about finite unions and density remain open.

Current status (as of February 2024): Erdős’s one-progression conjecture is disproved, while the broader structure and density of the exceptional set remain open.

Erdős Problem #16 — Structure of the odd numbers not of the form $2^k+p$

Primary source

Progress summary

Solutions 0