What about 5?
The smallest odd number > 1 that can't be written as the sum of a power of 2 and a prime number is 127...
127-1= 126= 2 x 7 x 9
127-2 = 125 = 5 x 5 x 5
127-4 = 123 = 3 x 41
127 - 8 = 119 = 7 x 17
127 - 16 = 111 = 3 x 37
127 - 32 = 95 = 5 x 19
127 - 64 = 63 = 3 x 3 x 7
Kind regards