cp's OEIS Frontend

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

%I A058887 #54 Aug 05 2024 09:42:45
%S A058887 3,7,17,19,19,19,31,31,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,
%T A058887 47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,
%U A058887 47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47
%N A058887 Smallest prime p such that (2^n)*p is a nontotient number.
%C A058887 For n=8,9,...,582, a(n) = 47. Note that A040076(47)=583.
%C A058887 For n=583,584,...,6392, a(n) = 383. Note that A040076(383)=6393.
%C A058887 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 A058887 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 A058887 In particular, a(n) <= 271129 for all n.
%C A058887 From _Jianing Song_, Dec 14 2021: (Start)
%C A058887 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 A058887 a(n) is also the smallest number k such that 2^n*k is a nontotient number (see A181662). (End)
%D A058887 David Harden, Posting to Sequence Fans Mailing List, Sep 19 2010.
%D A058887 J. L. Selfridge, Solution to Problem 4995, Amer. Math. Monthly, 70:1 (1963), page 101.
%H A058887 D. Bressoud, <a href="http://www.macalester.edu/~bressoud/books/CNT.m">CNT.m</a> Computational Number Theory Mathematica package.
%H A058887 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 A058887 Min{p|p is prime and card(invphi((2^n)*p))=0}.
%F A058887 From _Jianing Song_, Dec 14 2021: (Start)
%F A058887 a(0) = 3;
%F A058887 a(1) = 7;
%F A058887 a(2) = 17;
%F A058887 a(3..5) = 19;
%F A058887 a(6..7) = 31;
%F A058887 a(8..582) = 47;
%F A058887 a(583..6392) = 383;
%F A058887 a(6393..9714) = 2897;
%F A058887 a(9715..33287) = 3061;
%F A058887 a(33288..50010) = 5297;
%F A058887 a(50011..126112) = 7013;
%F A058887 a(126113..31172164) = 10223.
%F A058887 a(n) = A181662(n) / 2^n. (End)
%e A058887 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 A058887 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 A058887 Needs["CNT`"]; Table[p=3; While[PhiInverse[p*2^n] != {}, p=NextPrime[p]]; p, {n,0,20}]
%o A058887 (PARI) a(n) = my(p=2); while(istotient(2^n*p), p=nextprime(p+1)); p; \\ _Michel Marcus_, May 14 2020
%Y A058887 Cf. A005277, A007617, A057192, A071628, A076336 (Sierpiński numbers), A000010, A181662.
%K A058887 nonn
%O A058887 0,1
%A A058887 _Labos Elemer_, Jan 08 2001
%E A058887 Edited by _T. D. Noe_, Nov 15 2010
%E A058887 Edited by _Max Alekseyev_, Nov 19 2010