Let k greater than or equal to 2 be an integer. Let E(k)(N) be the num
ber of natural numbers not exceeding N which are not the sum of a prim
e and a k-th power of a natural number. Assuming the Riemann Hypothesi
s for all Dirichlet L-functions it is shown that E(k)(N) much less tha
n N-1-1/25k.