%I
%S 0,1,1,2,1,2,1,2,3,1,4,2,1,2,5,3,1,8,2,1,4,2,7,3,2,1,2,1,2,7,2,3,1,10,
%T 1,4,4,2,5,3,1,4,1,2,1,6,4,2,1,2,3,1,4,5,9,3,1,20,2,1,6,7,2,1,2,5,4,4,
%U 1,2,27,3,4,4,2,15,3,2,3,10,1,8,1,4,2,7,3,2,1,2,5,3,2,3,2,7,5,1,6,4,4,9,3,1
%N Smallest k such that prime(n)+2^k is prime, or 1 if no such prime exists.
%C Conjecture: k > 0 for all n.
%C For all primes p < 1000 there exists a k such that p + 2^k is prime. However, for p = prime(321) = 2131, p + 2^k is not prime for all k < 30000. The conjecture may be in question. Similarly, I cannot find k such that p + 2^k is prime for p = 7013, 8543, 10711, 14033 for k < 20000.  _Cino Hilliard_, Jun 27 2005
%C prime(80869739673507329) = 3367034409844073483, so a(80869739673507329) = 1 since 2^k + 3367034409844073483 is covered by {3, 5, 17, 257, 641, 65537, 6700417}.  _Charles R Greathouse IV_, Feb 08 2008
%C k=271129 is a smaller counterexample: gcd(k+2^n,2^241)>1 always holds using (1 mod 2, 0 mod 4, 2 mod 8, 6 mod 24, 14 mod 24 and 22 mod 24) as a covering for the n's. k with gcd(k+2^n,2^241)>1 always true were first found by Erdos (see refs).  Bruno Mishutka (bruno.mishutka(AT)googlemail.com), Mar 11 2009
%D A. O. L. Atkin and B. J. Birch, eds., Computers in Number Theory, Academic Press, 1971, page 74.
%H P. ErdÅ‘s, <a href="http://www.renyi.hu/~p_erdos/195007.pdf">On integers of the form 2^k + p and some related problems</a>, Summa Brasil. Math. 2 (1950), pp. 113123. [From Bruno Mishutka (bruno.mishutka(AT)googlemail.com), Mar 11 2009]
%H Charles R Greathouse IV, <a href="http://math.crg4.com/a094076.pdf">Constructing a covering set for numbers 2^k + p</a>
%H Charles R Greathouse IV, <a href="/A094076/a094076.txt">Table of n, a(n) for n = 1..3000</a> (with question marks at 321, 1066, 2168)
%e p = 773, k = 995, p + 2^k is prime.
%e p = 5101, k = 5760, p + 2^k is prime.
%t sk[n_]:=Module[{p=Prime[n],k=1},While[!PrimeQ[p+2^k],k++];k]; Join[{0}, Array[sk,110,2]] (* _Harvey P. Dale_, Jul 07 2013 *)
%o (PARI) pplus2ton(n,m) = { local(k,s,p,y,flag); s=0; forprime(p=2,n, flag=1; for(k=0,m, y=p+2^k; if(ispseudoprime(y), print1(k,","); s++;flag=0;break) ); \ if(flag,print(p)); search for defiant primes. );print(); print(s); } (Hilliard)
%Y Cf. A067760.
%K nonn
%O 1,4
%A _Reinhard Zumkeller_, Apr 29 2004
%E More terms from Don Reble (djr(AT)nk.ca), May 02 2004
%E More terms from _Cino Hilliard_, Jun 27 2005
%E More terms from _Charles R Greathouse IV_, Feb 08 2008
