Problem #16: Odd Numbers Not of Form 2^k+p

Erdos characterized this conjecture as 'rather silly.'

SOLVED

Problem Statement

Is the set of odd integers not of the form $2^k+p$ the union of an infinite arithmetic progression and a set of density $0$?

Categories: Number Theory Additive Basis Primes

Chen: DISPROVED this conjecture.

Erdos had demonstrated using covering congruences that such odd integers contain an infinite arithmetic progression.

Source: erdosproblems.com/16 | Last verified: January 13, 2026