A058887 - OEIS

%I #54 Aug 05 2024 09:42:45

%S 3,7,17,19,19,19,31,31,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,

%T 47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,

%U 47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47

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

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

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

%C 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]

%C 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.

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

%C From _Jianing Song_, Dec 14 2021: (Start)

%C 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.

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

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

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

%H D. Bressoud, <a href="http://www.macalester.edu/~bressoud/books/CNT.m">CNT.m</a> Computational Number Theory Mathematica package.

%H Jianing Song, <a href="/A058887/a058887.txt">Proof that a(n) is the smallest prime p such that 2^e*p + 1 is composite for all 0 <= e <= n</a>.

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

%F From _Jianing Song_, Dec 14 2021: (Start)

%F a(0) = 3;

%F a(1) = 7;

%F a(2) = 17;

%F a(3..5) = 19;

%F a(6..7) = 31;

%F a(8..582) = 47;

%F a(583..6392) = 383;

%F a(6393..9714) = 2897;

%F a(9715..33287) = 3061;

%F a(33288..50010) = 5297;

%F a(50011..126112) = 7013;

%F a(126113..31172164) = 10223.

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

%e 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.

%e 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.

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

%o (PARI) a(n) = my(p=2); while(istotient(2^n*p), p=nextprime(p+1)); p; \\ _Michel Marcus_, May 14 2020

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

%K nonn

%O 0,1

%A _Labos Elemer_, Jan 08 2001

%E Edited by _T. D. Noe_, Nov 15 2010

%E Edited by _Max Alekseyev_, Nov 19 2010