cp's OEIS Frontend

A129802 Possible bases for Pepin's primality test for Fermat numbers.

%I A129802 #30 Jul 09 2025 04:26:54
%S A129802 3,5,6,7,10,12,14,20,24,27,28,39,40,41,45,48,51,54,56,63,65,75,78,80,
%T A129802 82,85,90,91,96,102,105,108,112,119,125,126,130,147,150,156,160,164,
%U A129802 170,175,180,182,192,204,210,216,224,238,243,245,250,252,260,291,294,300
%N A129802 Possible bases for Pepin's primality test for Fermat numbers.
%C A129802 Prime elements of this sequence are given by A102742.
%C A129802 From _Jianing Song_, May 15 2024: (Start)
%C A129802 Let m be an odd number and ord(2,m) = 2^r*d be the multiplicative order of 2 modulo m, where d is odd, then 2^2^n + 1 is congruent to one of 2^2^r + 1, 2^2^(r+1) + 1, ..., 2^2^(r+ord(2,d)-1) + 1 modulo m, so it suffices to check these ord(2,d) numbers.
%C A129802 Note that if m > 1, then m does not divide 2^2^n + 1 for n >= r, otherwise we would have 2^(2^n*d) = (2^ord(2,m))^2^(n-r) == 1 (mod m) and 2^(2^n*d) = (2^2^n)^d == (-1)^d == -1 (mod m). As a result, m is a term if and only if the Jacobi symbol ((2^2^n + 1)/m) is equal to -1 for m = r, r+1, ..., r+ord(2,d)-1.
%C A129802 By definition, a squarefree number that is a product of elite primes (A102742) or anti-elite primes (A128852) is a term if and only if its number of elite factors is odd. But a squarefree term can have factors that are neither elite nor anti-elite, the smallest being 551 = 19*29. (End)
%H A129802 Arkadiusz Wesolowski, <a href="/A129802/b129802.txt">Table of n, a(n) for n = 1..10000</a>
%H A129802 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PepinsTest.html">Pepin's Test</a>.
%F A129802 A positive integer 2^k*m, where m is odd and k >= 0, belongs to this sequence iff the Jacobi symbol (F_n/m) = 1 for only a finite number of Fermat numbers F_n = A000215(n).
%e A129802 For n >= 2, we have 2^2^n + 1 == 170, 461, 17, 257, 519, 539 (mod 551) respectively for n == 0, 1, 2, 3, 4, 5 (mod 6). As we have (170/551) = (461/551) = (17/551) = (257/551) = (519/551) = (539/551) = -1, 551 is a term. - _Jianing Song_, May 19 2024
%o A129802 (PARI) { isPepin(n) = local(s,S=Set(),t); n\=2^valuation(n,2); s=Mod(3,n); while( !setsearch(S,s), S=setunion(S,[s]); s=(s-1)^2+1); t=s; until( t==s, if( kronecker(lift(t),n)==1, return(0)); t=(t-1)^2+1);1 }
%o A129802 for(n=2,1000,if(isPepin(n),print1(n,", ")))
%o A129802 (PARI) for(b=2, 300, k=b/2^valuation(b, 2); if(k>1, i=logint(k, 2); m=Mod(2, k); z=znorder(m); e=znorder(Mod(2, z/2^valuation(z, 2))); t=0; for(c=1, e, if(kronecker(lift(m^2^(i+c))+1, k)==-1, t++, break)); if(t==e, print1(b, ", ")))); \\ _Arkadiusz Wesolowski_, Sep 22 2021
%o A129802 (PARI) isA129802(n) = n = (n >> valuation(n,2)); my(d = znorder(Mod(2, n)), StartPoint = valuation(d, 2), LengthTest = znorder(Mod(2, d >> StartPoint))); for(i = StartPoint, StartPoint + LengthTest - 1, if(kronecker(lift(Mod(2, n)^2^i + 1), n) == 1, return(0))); 1 \\ _Jianing Song_, May 19 2024
%Y A129802 Cf. A000215, A019434, A060377, A102742, A128852, A372894.
%K A129802 nonn
%O A129802 1,1
%A A129802 _Max Alekseyev_, Jun 14 2007, corrected Dec 29 2007. Thanks to _Ant King_ for pointing out an error in the earlier version of this sequence