A180065 Smallest strong pseudoprime to base 2 with n prime factors.

2047, 15841, 800605, 293609485, 10761055201, 5478598723585, 713808066913201, 90614118359482705, 5993318051893040401, 24325630440506854886701, 27146803388402594456683201, 4365221464536367089854499301, 2162223198751674481689868383601, 548097717006566233800428685318301

Offset

2,1

Links

Daniel Suteu, Table of n, a(n) for n = 2..17

Index entries for sequences related to pseudoprimes

Example

800605 is the third term because 800605 = 5 * 13 * 109 * 113, more prime factors than smaller 2-strong pseudoprimes.

Prog

(PARI)
strong_check(p, base, e, r) = my(tv=valuation(p-1, 2)); tv > e && Mod(base, p)^((p-1)>>(tv-e)) == r;
strong_fermat_psp(A, B, k, base) = A=max(A, vecprod(primes(k))); (f(m, l, lo, k, e, r) = my(list=List()); my(hi=sqrtnint(B\m, k)); if(lo > hi, return(list)); if(k==1, forstep(p=lift(1/Mod(m, l)), hi, l, if(isprimepower(p) && gcd(m*base, p) == 1 && strong_check(p, base, e, r), my(n=m*p); if(n >= A && (n-1) % znorder(Mod(base, p)) == 0, listput(list, n)))), forprime(p=lo, hi, base%p == 0 && next; strong_check(p, base, e, r) || next; my(z=znorder(Mod(base, p))); gcd(m, z) == 1 || next; my(q=p, v=m*p); while(v <= B, list=concat(list, f(v, lcm(l, z), p+1, k-1, e, r)); q *= p; Mod(base, q)^z == 1 || break; v *= p))); list); my(res=f(1, 1, 2, k, 0, 1)); for(v=0, logint(B, 2), res=concat(res, f(1, 1, 2, k, v, -1))); vecsort(Set(res));
a(n) = if(n < 2, return()); my(x=vecprod(primes(n)), y=2*x); while(1, my(v=strong_fermat_psp(x, y, n, 2)); if(#v >= 1, return(v[1])); x=y+1; y=2*x); \\ Daniel Suteu, Mar 04 2023

Crossrefs

Cf. A007011, A001262.

Sequence in context: A361256 A360184 A062568 * A270697 A075954 A011561

Adjacent sequences: A180062 A180063 A180064 * A180066 A180067 A180068

Keyword

nonn

Author

Kevin Batista (kevin762401(AT)yahoo.com), Aug 09 2010

Extensions

a(6)-a(10) and editing from Charles R Greathouse IV, Aug 29 2010

a(11)-a(15) from Daniel Suteu, Sep 24 2022

Status

approved