login
Semiprimes of form p*q with p < q, such that 2^p - 1 == 0 (mod q).
1

%I #13 Nov 23 2019 23:05:05

%S 6,21,155,253,889,979,1081,6757,8251,13861,18533,31987,32047,34453,

%T 60581,64261,73153,106483,110497,114481,126253,212111,212273,256507,

%U 258121,325967,337133,351541,371953,383183,392941,417917,457207,482653,548047,869221,933661,946051

%N Semiprimes of form p*q with p < q, such that 2^p - 1 == 0 (mod q).

%C Number of terms < 10^k: 1, 2, 6, 9, 17, 38, 91, 222, ..., .

%H Robert Israel, <a href="/A179768/b179768.txt">Table of n, a(n) for n = 1..518</a>

%e 6 is a term because 6=2*3 and 2^2-1 (mod 3)=0;

%e 21 is a term because 21=3*7 and 2^3-1 (mod 7)=0;

%e 155 is a term because 155=5*31 and 2^5-1 (mod 31)=0;

%e 253 is a term because 253=11*23 and 2^11-1 (mod 23)=0;

%e 889 is a term because 889=7*127 and 2^7-1 (mod 127)=0;

%e 979 is a term because 979=11*89 and 2^11-1 (mod 89)=0; etc.

%p N:= 10^6: # to get all terms <= N

%p Q:= ceil(fsolve(q*log[2](q)=N));

%p Res:= NULL:

%p q:= 2:

%p do

%p q:= nextprime(q);

%p if q > Q then break fi;

%p p:= numtheory:-order(2,q);

%p if not isprime(p) then next fi;

%p v:= p*q;

%p if v <= N then Res:= Res, v fi

%p od:

%p sort([Res]); # _Robert Israel_, Nov 23 2019

%t fQ[n_] := Block[{fi = FactorInteger@ n}, Plus @@ Last /@ fi == 2 && PowerMod[2, fi[[1, 1]], fi[[2, 1]]] == 1]; Select[ Range@ 1000000, fQ] (* _Robert G. Wilson v_, Jan 10 2011 *)

%Y Cf. A000079, A001358.

%K nonn

%O 1,1

%A _Juri-Stepan Gerasimov_, Jan 10 2011

%E Corrected, extended & edited by _Robert G. Wilson v_, Jan 10 2011