Charles Greathouse points out paper by T.Tao...
--oh, great, scooped by Terry Tao. Terence Tao: A remark on primality testing and decimal expansions, J.Australian Math'l. Soc. 91,3 (2011) 405-413. http://arxiv.org/abs/0802.3361 However, upon reading this paper, I observe that Tao does not have even any guess about what the constant C is. Tao proves that the proportion of n-bit primes (n sufficiently large) in which "every bit matters" is bounded between two constants in (0,1). He also proves analogous statement in every fixed radix other than 2. Tao also remarks that it should be possible to show not only that every bit-altered version is composite, but actually is fairly highly composite, i.e. having at least (loglogN)^0.33 prime factors. He also thinks it should be possible to consider "edits" of the number where you erase or insert one digit, and all edited versions must be composite. (He does not actually solve these problems, he just claims using similar techniques one presumably could solve them.) Tao's result with radix 2 is actually a trivial consequence of the fact, pointed out by Zhi-Wei Sun: Proc. Amer. Math. Soc. 128 (2000) 997-1002 http://www.ams.org/journals/proc/2000-128-04/S0002-9939-99-05502-1/ that every integer in the arithmetic progression with initial term 47867742232066880047611079 and increment 46397560804008899814641902590 = 2*3*5*7*11*13*17*19*31*37*41*61*73*97*109*151*241*257*231 has the property that all 1-bit alterations of it, are composite. Now use Dirichlet's theorem for primes in arithmetic progressions, end of proof. This shows the lower bound C >= 1/46397560804008899814641902590 > 2.155*10^(-29) on the proportion of "every bit matters" primes. However, Tao does not know, nor even guess, what these constants are, and he does not prove that a limit exists, i.e. he does not show that the constants in his upper and lower bounds ultimately become the same. I believe that (a) limit does exist, and (b) we should be able to write down an expression for the limit constant, somewhat like my wrong-guess expression, but trickier. There will be no known way to prove this expression is correct, but it will be correct anyhow. Also, I see little or no hope to prove the limit exists (but it should).