cp's OEIS Frontend

A007011 a(n) = smallest pseudoprime to base 2 with n prime factors.

%I A007011 M5444 #31 Mar 05 2023 01:28:35
%S A007011 341,561,11305,825265,45593065,370851481,38504389105,7550611589521,
%T A007011 277960972890601,32918038719446881,1730865304568301265,
%U A007011 606395069520916762801,59989606772480422038001,6149883077429715389052001,540513705778955131306570201,35237869211718889547310642241
%N A007011 a(n) = smallest pseudoprime to base 2 with n prime factors.
%C A007011 Smallest composite number m with n prime factors such that 2^(m-1)-1 is divisible by m.
%D A007011 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A007011 Daniel Suteu, <a href="/A007011/b007011.txt">Table of n, a(n) for n = 2..34</a>
%H A007011 R. Pinch, <a href="http://www.chalcedon.demon.co.uk/rgep/p41.ps">Pseudoprimes up to 10^13</a>, Proceedings ANTS-IV, 4th Algorithmic Number Theory Symposium, Leiden, 2000. Springer Lecture Notes in Computer Science 1838 (2000) 459--474.
%H A007011 <a href="/index/Ps#pseudoprimes">Index entries for sequences related to pseudoprimes</a>
%o A007011 (PARI)
%o A007011 fermat_psp(A, B, k, base) = A=max(A, vecprod(primes(k))); (f(m, l, lo, k) = 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, 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; 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)); q *= p; Mod(base, q)^z == 1 || break; v *= p))); list); vecsort(Set(f(1, 1, 2, k)));
%o A007011 a(n) = if(n < 2, return()); my(x=vecprod(primes(n)), y=2*x); while(1, my(v=fermat_psp(x, y, n, 2)); if(#v >= 1, return(v[1])); x=y+1; y=2*x); \\ _Daniel Suteu_, Mar 04 2023
%Y A007011 Cf. A007535.
%K A007011 nonn,nice
%O A007011 2,1
%A A007011 _Richard Pinch_
%E A007011 More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), May 05 2007