--- In

primenumbers@yahoogroups.com,

"David Broadhurst" <d.broadhurst@...> wrote:

> 97723892848682923994567734100095132801 =

> 59*67*71*79*89*101*113*191*233*239*307*349*379*911*2089*5279

A Pari-GP script for producing 246 such pseudoprimes is

\\ erdos2.gp

L=2^7*3^3*5^2*7*11*13*17*19*29; \\ super-smooth seed

mp=sqrtint(L+1);A=[];B=[];C=[];k=0;sa=[1];sb=[1];

{forprime(p=1,mp,if(gcd(L,p)==1&&L%(p^2-1)==0,

k=k+1;if(k%2,A=concat(A,p),B=concat(B,p))));}

for(k=1,#A,sa=concat(sa,sa*A[k]));

for(k=1,#B,sb=concat(sb,sb*B[k]));

st=vecsort(concat(sa%L,vector(#sb,k,(1/sb[k])%L)));

for(k=3,#st,r=st[k];if(r==st[k-1],C=concat(C,r)));

{for(k=1,#C,if(k%10==0,print("\\\\ done "k));c=C[k];

for(j=1,#sa,if(sa[j]%L==c,t=sa[j];break));d=(1/c)%L;

for(j=1,#sb,if(sb[j]%L==d,t=t*sb[j];break));C[k]=t;)}

C=vecsort(C);print("{C=[");for(k=1,#C,print(C[k]","));

print(#C"];}");print(round(gettime/10^3)" seconds");

but take care: I allocated 3GB of core.

This generates pseudoprimes N such that, for every prime p

dividing N, both p-1 and p+1 divide N-1. The full output,

comprising 246 "Carmichael numbers of order 2", is in

http://physics.open.ac.uk/~dbroadhu/cert/erdos2.out
and was obtained in 675 seconds, using 2.7 GB of core.

The largest pseudoprime, found with the seed L, was

127905790005702291893660711189034208857122374296\

660769359758600083769407029360111561601

=

23*31*41*43*53*67*71*79*89*109*113*131*181*199

*239*271*307*349*379*419*449*463*521*571*701

*1217*1429*1871*2089*2551*4159*5279*5851*9281

and has 34 prime factors.

This Erdos-type algorithm was outlined in a talk

entitled "Higher-order Carmichael numbers",

given by Everett W. Howe in December 2006:

alumnus.caltech.edu/~however/talks/FortCollins.pdf

David Broadhurst