%I #42 Jul 28 2016 09:11:19
%S 1,1,2,1,2,1,4,3,2,1,2,1,6,3,2,1,2,1,4,5,2,1,8,3,4,3,2,1,2,1,4,3,8,5,
%T 2,1,10,3,2,1,2,1,6,5,2,1,4,3,4,11,2,1,20,3,4,3,2,1,2,1,4,3,8,13,2,1,
%U 4,3,2,1,2,1,6,3,12,5,2,1,6,5,2,1,8,3,4,5,2,1,4,7,4,3,6,11,2,1,4,3,2,1
%N Least positive integer k <= n such that 2^k + (n - k) is prime, or 0 if such an integer k does not exist.
%C Conjecture: a(n) > 0 for all n > 0.
%C See also part (i) of the conjecture in A231201.
%C We have computed a(n) for all n up to 2*10^6 except for n = 1657977. Here are some relatively large values of a(n): a(421801) = 149536 (the author found that 2^{149536} + 421801 - 149536 is prime, and then his friend Qing-Hu Hou verified that 2^k + 421801 - k is composite for each integer 0 < k < 149536), a(740608) = 25487, a(768518) = 77039, a(1042198) = 31357, a(1235105) = 21652, a(1253763) = 39018, a(1310106) = 55609, a(1346013) = 33806, a(1410711) = 45336, a(1497243) = 37826, a(1549802) = 21225, a(1555268) = 43253, a(1674605) = 28306, a(1959553) = 40428.
%C Now we find that a(1657977) = 205494. The prime 2^205494 + (1657977-205494) has 61860 decimal digits. - _Zhi-Wei Sun_, Aug 30 2015
%C We have found that a(n) > 0 for all n = 1..7292138. For example, a(5120132) = 250851, and the prime 2^250851 + 4869281 has 75514 decimal digits. - _Zhi-Wei Sun_, Nov 16 2015
%C We have verified that a(n) > 0 for all n = 1..10^7. For example, a(7292139) = 218702 and 2^218702 + (7292139-218702) is a prime of 65836 decimal digits; also a(9302003) = 311468 and the prime 2^311468 + (9302003-311468) has 93762 decimal digits. - _Zhi-Wei Sun_, Jul 28 2016
%H Zhi-Wei Sun, <a href="/A231557/b231557.txt">Table of n, a(n) for n = 1..10000</a>
%H Zhi-Wei Sun, <a href="http://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;85566cc1.1311">Write n = k + m with 2^k + m prime</a>, a message to Number Theory List, Nov. 16, 2013.
%H Zhi-Wei Sun, <a href="http://arxiv.org/abs/1312.1166">On a^n+bn modulo m</a>, arXiv:1312.1166 [math.NT], 2013-2014.
%e a(1) = 1 since 2^1 + (1-1) = 2 is prime.
%e a(2) = 1 since 2^1 + (2-1) = 3 is prime.
%e a(3) = 2 since 2^1 + (3-1) = 4 is not prime, but 2^2 + (3-2) = 5 is prime.
%t Do[Do[If[PrimeQ[2^x+n-x],Print[n," ",x];Goto[aa]],{x,1,n}];
%t Print[n," ",0];Label[aa];Continue,{n,1,100}]
%o (PARI) a(n) = {for (k = 1, n, if (isprime(2^k+n-k), return (k));); return (0);} \\ _Michel Marcus_, Nov 11 2013
%Y Cf. A000040, A000079, A231201, A231555, A231725.
%K nonn
%O 1,3
%A _Zhi-Wei Sun_, Nov 11 2013