|
|
A129802
|
|
Possible bases for Pepin's primality test for Fermat numbers.
|
|
7
|
|
|
3, 5, 6, 7, 10, 12, 14, 20, 24, 27, 28, 39, 40, 41, 45, 48, 51, 54, 56, 63, 65, 75, 78, 80, 82, 85, 90, 91, 96, 102, 105, 108, 112, 119, 125, 126, 130, 147, 150, 156, 160, 164, 170, 175, 180, 182, 192, 204, 210, 216, 224, 238, 243, 245, 250, 252, 260, 291, 294, 300
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
Prime elements of this sequence are given by A102742.
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.
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 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.
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)
|
|
LINKS
|
|
|
FORMULA
|
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).
|
|
EXAMPLE
|
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
|
|
PROG
|
(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 }
for(n=2, 1000, if(isPepin(n), print1(n, ", ")))
(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
(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
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.
|
|
STATUS
|
approved
|
|
|
|