A356866 - OEIS

%I #61 Oct 02 2022 13:32:40

%S 15841,5310721,440707345,10761055201,5478598723585,713808066913201,

%T 1022751992545146865,5993318051893040401,120459489697022624089201,

%U 27146803388402594456683201,14889929431153115006659489681

%N Smallest Carmichael number (A002997) with n prime factors that is also a strong pseudoprime to base 2 (A001262).

%F a(n) >= max(A180065(n), A006931(n)).

%o (PARI)

%o carmichael_strong_psp(A, B, k, base) = A=max(A, vecprod(primes(k+1))\2); (f(m, l, p, k, k_exp, congr, u=0, v=0) = my(list=List()); if(k==1, forprime(q=u, v, my(t=m*q); if((t-1)%l == 0 && (t-1)%(q-1) == 0, my(tv=valuation(q-1, 2)); if(tv > k_exp && Mod(base, q)^(((q-1)>>tv)<<k_exp) == congr, listput(list, t)))), forprime(q = p, sqrtnint(B\m, k), if(base%q != 0, my(tv=valuation(q-1, 2)); if(tv > k_exp && Mod(base, q)^(((q-1)>>tv)<<k_exp) == congr, my(L=lcm(l, q-1)); if(gcd(L, m) == 1, my(t = m*q, u=ceil(A/t), v=B\t); if(u <= v, my(r=nextprime(q+1)); if(k==2 && r>u, u=r); list=concat(list, f(t, L, r, k-1, k_exp, congr, u, v)))))))); list); my(res=f(1, 1, 3, k, 0, 1)); for(v=0, logint(B, 2), res=concat(res, f(1, 1, 3, k, v, -1))); vecsort(Vec(res));

%o a(n,base=2) = if(n < 3, return()); my(x=vecprod(primes(n+1))\2,y=2*x); while(1, my(v=carmichael_strong_psp(x,y,n,base)); if(#v >= 1, return(v[1])); x=y+1; y=2*x);

%Y Cf. A001262, A002997, A006931, A063847, A180065.

%K nonn,more

%O 3,1

%A _Daniel Suteu_, Oct 01 2022