A058887 Smallest prime p such that (2^n)*p is a nontotient number.

3, 7, 17, 19, 19, 19, 31, 31, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47

Offset: 0

Author

Labos Elemer, Jan 08 2001

Keywords

• nonn

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)

Examples

			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.
		

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.
• Jianing Song, Proof that a(n) is the smallest prime p such that 2^e*p + 1 is composite for all 0 <= e <= n.

Crossrefs

Cf. A005277, A007617, A057192, A071628, A076336 (Sierpiński numbers), A000010, A181662.

Programs

Mathematica

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

PARI

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

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)

Extensions

Edited by T. D. Noe, Nov 15 2010

Edited by Max Alekseyev, Nov 19 2010