login
A248972
a(n) is the smallest b such that b^((p-1)/2) == -1 (mod p) where p = A080076(n) is the n-th Proth prime.
2
2, 2, 2, 3, 3, 5, 3, 5, 7, 3, 3, 3, 5, 3, 5, 7, 3, 5, 3, 3, 3, 5, 13, 3, 3, 3, 5, 3, 5, 7, 5, 13, 3, 3, 13, 3, 11, 5, 3, 3, 3, 11, 3, 11, 3, 3, 5, 3, 7, 3, 3, 5, 3, 5, 11, 3, 3, 5, 11, 3, 7, 5, 5, 3, 5, 3, 5, 3, 3, 3, 5, 3, 3, 3, 19, 3, 3, 3, 7, 7, 3, 3, 11, 5, 3, 3, 5, 3, 11, 5, 3, 7
OFFSET
1,1
COMMENTS
Proth's theorem asserts that p=1+k*2^m (with odd k < 2^m) is prime if there exists b such that b^((p-1)/2) == -1 (mod n). This sequence lists the smallest b which certifies primality of A080076(n) via this relation.
For n > 3, a(n) is an odd prime. - Thomas Ordowski, Apr 23 2019
FORMULA
a(n) = A020649(A080076(n)) = A053760(k), where prime(k) = A080076(n). - Thomas Ordowski, Apr 23 2019
PROG
(PARI) A248972(n)=my(N=A080076[n]); for(a=0, 9e9, Mod(a, N)^(N\2)==-1&&return(a))
A080076=[]; forprime(p=1, 99999, isproth(p)&&(A080076=concat(A080076, p))&&print1(A248972(#A080076)", "))
isproth(x)={ !bittest(x--, 0) & (x>>valuation(x, 2))^2 < x }
CROSSREFS
Cf. A080076.
A subsequence of A020649 and of A053760.
Sequence in context: A237121 A329493 A139821 * A077563 A055256 A369985
KEYWORD
nonn
AUTHOR
M. F. Hasler, Oct 18 2014
STATUS
approved