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

Table of n, a(n) for n=0..65.

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.

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

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

Sequence in context: A191147 A227211 A271725 * A355656 A306355 A087749

Adjacent sequences: A058884 A058885 A058886 * A058888 A058889 A058890

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