OFFSET

0,1

COMMENTS

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)

REFERENCES

David Harden, Posting to Sequence Fans Mailing List, Sep 19 2010.

J. L. Selfridge, Solution to Problem 4995, Amer. Math. Monthly, 70:1 (1963), page 101.

LINKS

D. Bressoud, CNT.m Computational Number Theory Mathematica package.

FORMULA

Min{p|p is prime and card(invphi((2^n)*p))=0}.

From Jianing Song, Dec 14 2021: (Start)

a(0) = 3;

a(1) = 7;

a(2) = 17;

a(3..5) = 19;

a(6..7) = 31;

a(8..582) = 47;

a(583..6392) = 383;

a(6393..9714) = 2897;

a(9715..33287) = 3061;

a(33288..50010) = 5297;

a(50011..126112) = 7013;

a(126113..31172164) = 10223.

a(n) = A181662(n) / 2^n. (End)

EXAMPLE

For n=1, the initial segment of {2p} sequence is nops(invphi({2p}))={4, 4, 2, 0, 2, 0, 0, 0, 2, 2, ...}, where the position of the first 0 is 4, corresponding to p(4)=7, so a(1)=7.

For n=8 the same initial segment is: {11, 32, 23, 18, 24, 10, 11, 4, 9, 21, 2, 16, 9, 12, 0, 14, 5, 6, 12, ...}, where the first 0 is the 15th, corresponding to p(15)=47, thus a(8)=47.

MATHEMATICA

Needs["CNT`"]; Table[p=3; While[PhiInverse[p*2^n] != {}, p=NextPrime[p]]; p, {n, 0, 20}]

PROG

(PARI) a(n) = my(p=2); while(istotient(2^n*p), p=nextprime(p+1)); p; \\ Michel Marcus, May 14 2020

CROSSREFS

KEYWORD

nonn

AUTHOR

Labos Elemer, Jan 08 2001

EXTENSIONS

Edited by T. D. Noe, Nov 15 2010

Edited by Max Alekseyev, Nov 19 2010

STATUS

approved