login
A058887
Smallest prime p such that (2^n)*p is a nontotient number.
6
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
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
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