A231557 Least positive integer k <= n such that 2^k + (n - k) is prime, or 0 if such an integer k does not exist.

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, 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, 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

Offset: 1

Author

Zhi-Wei Sun, Nov 11 2013

Keywords

• nonn

Comments

Conjecture: a(n) > 0 for all n > 0.

See also part (i) of the conjecture in A231201.

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.

Now we find that a(1657977) = 205494. The prime 2^205494 + (1657977-205494) has 61860 decimal digits. - Zhi-Wei Sun, Aug 30 2015

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

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

Examples

			a(1) = 1 since 2^1 + (1-1) = 2 is prime.
a(2) = 1 since 2^1 + (2-1) = 3 is prime.
a(3) = 2 since 2^1 + (3-1) = 4 is not prime, but 2^2 + (3-2) = 5 is prime.
		

Links

• Zhi-Wei Sun, Table of n, a(n) for n = 1..10000
• Zhi-Wei Sun, Write n = k + m with 2^k + m prime, a message to Number Theory List, Nov. 16, 2013.
• Zhi-Wei Sun, On a^n+bn modulo m, arXiv:1312.1166 [math.NT], 2013-2014.

Crossrefs

Cf. A000040, A000079, A231201, A231555, A231725.

Programs

Mathematica

Do[Do[If[PrimeQ[2^x+n-x],Print[n," ",x];Goto[aa]],{x,1,n}];
Print[n," ",0];Label[aa];Continue,{n,1,100}]

PARI

a(n) = {for (k = 1, n, if (isprime(2^k+n-k), return (k));); return (0);} \\ Michel Marcus, Nov 11 2013