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

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

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.

Example

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.

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}]

Prog

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

Crossrefs

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

Sequence in context: A276976 A135545 A123317 * A171453 A285707 A164879

Adjacent sequences: A231554 A231555 A231556 * A231558 A231559 A231560

Keyword

nonn

Author

Zhi-Wei Sun, Nov 11 2013

Status

approved