cp's OEIS Frontend

There exist odd integers 2k-1 such that (2k-1)2^n+1 is always composite.

For n=8,9,...,582, a(n) = 47. Note that A040076(47)=583.

For n=583,584,...,6392, a(n) = 383. Note that A040076(383)=6393.

Subsequent primes are 2897, 3061, 5297, and 7013 (cf. A057192 and A071628). [These are primes p such that the least e such that 2^e*p + 1 is prime sets a new record. - Jianing Song, Dec 14 2021]

Starting with some large N, a(n)=p for all n >= N. This prime p will likely be the first prime Sierpiński number, which is conjectured to be 271129.

In particular, a(n) <= 271129 for all n.

From Jianing Song, Dec 14 2021: (Start)

a(n) is the smallest prime p such that 2^e*p + 1 is composite for all 0 <= e <= n. A proof is given in the a-file below.

a(n) is also the smallest number k such that 2^n*k is a nontotient number (see A181662). (End)

Sierpiński proved that a(n)=0 for an infinite number of n. The first proven zero is n=78557. There is a conjecture that the first zero is n=65536 (which is equivalent to the statement that 2^(2^k)+1 is composite for k>4). - T. D. Noe, Feb 25 2011 [Edited by Jeppe Stig Nielsen, Jul 01 2020]

The next term in this sequence, a(54) for the prime p=251, is greater than 73000.

Is there a prime p such that p^k - p^(k-1) + 1 is composite for all k > 1? For the related question of Sierpinski numbers (n such that n*2^k+1 is composite for all k ), the answer is yes.

If n=251^k-251^(k-1)+1 is prime then k mod 10 = 1,5,7 or 9 because n mod 3 = 0 iff k is even and n mod 11 = 0 iff k mod 5 = 3. More exponents can be cleared this way. - Bernardo Boncompagni, Oct 23 2005

Note that k cannot be 8, 14, 20, ... (i.e. k == 2 mod 6) because then p^2 - p + 1 divides p^k - p^(k-1) + 1. - T. D. Noe, Aug 31 2006

Does such k exist (so that a(n) is nonzero) for all n? These binary trinomials can also be written as f*2^n+1, where f=2^m+1 for some m, which is reminiscent of the Sierpinski problem (see A076336). Hence if there are no Sierpinski numbers of the form 2^m+1, then a(n) is nonzero for all n.

The PFGW program was used to find a(32), which produces a 138012-digit probable prime. If a(256) is nonzero, it is greater than 10^6.

If n == 1 (mod 3), then for every positive integer k, 2*n^k+1 is divisible by 3 and cannot be prime (unless n=1). Thus we restrict the domain of this sequence to A007494 (n which is not in the form 3j+1).

Conjecture: a(n) is defined for all n.

a(145) > 200000, a(146) .. a(156) = {1, 1, 66, 1, 4, 3, 1, 1, 1, 1, 6}, a(157) > 100000, a(158) .. a(180) = {2, 1, 2, 11, 1, 1, 3, 321, 1, 1, 3, 1, 2, 12183, 5, 1, 1, 957, 2, 3, 16, 3, 1}.

a(n) = 1 if and only if n is in A144769.

When 2n-1 is the k-th prime, then a(n) = A040076(2n-1) = A046067(n) = A057192(k). [This is only partially correct. If 2n-1 = 2^2^m + 1 is a Fermat prime, then a(n) = min{2^m, A040076(2n-1)} if 2n-1 is not a Sierpiński number and a(n) = 2^m otherwise, since phi((2n-1)^2) = (2n-1)*2^m. For example, a(129) = 8 < A040076(257) = 279, a(32769) = 16 < A040076(65537) = 287. - Jianing Song, Dec 14 2021]

From Jianing Song, Dec 14 2021: (Start)

a(1) should have been 0.

If 2n-1 is a prime Sierpiński number which is not a Fermat prime, then a(2n-1) = -1.

Do there exists n such that 2n-1 is composite and that a(2n-1) = -1? It seems very unlikely that this will happen: Let 2n-1 = (a_1)^(e_1) * (a_2)^(e_2) * ... * (a_r)^(e_r) * (q_1)^(f_1) * (q_2)^(f_2) * ... * (q_s)^(f_s), where a_1, a_2, ..., a_r are distinct numbers that are not Fermat primes (a_i is not necessarily a prime), q_1, q_2, ..., q_s are distinct Fermat primes. If p_{i,1}, p_{i,2}, ..., p_{i,e_i} are distinct primes of the form 2^e * (a_i) + 1, then the odd part of phi((Product_{i=1..r, j=1..e_i} p_{i,j}) * (Product_{i=1..s} (q_s)^(1+f_s))) is 2n-1.

Therefore, if k is not a Sierpiński number implies that there are infinitely many e such that 2^e * k + 1 is prime, then a necessary condition for a(2n-1) = -1 is that: for every factorization 2n-1 = (u_1) * (u_2) * ... * (u_t) (u_i is not necessarily a prime, and (u_i)'s are not necessarily distinct), at least one u_i must be a Sierpiński number which is not a Fermat prime. In particular, 2n-1 itself must be a Sierpiński number. (End)

From Jianing Song, Dec 14 2021: (Start)

Let a(n) = 2^n * k, then k must be odd, otherwise a(n)/2 is a totient number, which implies that a(n) is a totient.

Note that 271129 * 2^m is a nontotient for all m (see A058887), so k <= 271129. In fact, let p be smallest prime such that 2^e*p + 1 is composite for all 0 <= e <= n, then k <= p (since 2^n*p is a nontotient).

Actually, k is equal to p. To verify this, it suffices to show that k cannot be an odd composite number < 271129; that is to say, if 2^n * k is a nontotient for an odd composite number < 271129, then there exists k' < k such that 2^n * k' is a nontotient.

The case k < 383 can be easily checked. Let k be an odd composite number in the range (383, 271129), k * 2^n is a nontotient implies n < 2554 unless k = 98431 or 248959 (see the a-file below), then 383 * 2^n is a nontotient (the least n such that 383 * 2^n + 1 is prime is n = 6393). For k = 98431 or 248959, k * 2^n is a nontotient implies n < 7062, then 2897 * 2^n is a nontotient (the least n such that 2897 * 2^n + 1 is prime is n = 9715. (End)

a(5k+4) = 0, since (5k+4)*6^n+1 is always divisible by 5, but there are infinitely many numbers not in the form 5k+4 such that a(n) = 0. For example, a(174308) = 0 since 174308*6^n+1 is always divisible by 7, 13, 31, 37, or 97 (See A123159). Conjecture: if n is not in the form 5k+4 and n < 174308, then a(n) > 0.

However, according to the Barnes link no primes n*6^k+1 are known for n = 1296, 7776 and 46656, so these may be counterexamples. - Robert Israel, Mar 17 2015

This appears to be a shifted variant of A040076. - R. J. Mathar, May 28 2013

If n is prime, then a(n) = 0. If the sequence never reaches a prime number (for n = 1) or the prime number has more than 1000 digits, -1 is used instead. There are 22 such numbers for n < 10000.