A367229 - OEIS

%I #15 Nov 12 2023 00:06:06

%S 1905,15841,129921,8322945,66977281,4395899025409,4398012825601,

%T 140735340806145,36892925197465616385,2342736497361113055105,

%U 4951750712408555360305545217,39304596247310823728047193985,2535301191011725837253847547905,1298074214624262174166747352924161

%N Fermat pseudoprimes to base 2 that are products of two Mersenne numbers (not necessarily distinct) that are larger than 1.

%C Without the restriction to Mersenne numbers that are larger than 1 all the composite Mersenne numbers (A065341) will be terms.

%C Szymiczek (1964) proved that if p is a prime == 7 (mod 8) (A007522) and t = 2^phi((p-1)/2), then M(p)*M(t) is a Fermat pseudoprime to base 2, where phi is the Euler totient function (A000010) and M(n) = 2^n-1 = A000225(n) is the n-th Mersenne number. The smallest pseudoprime that is generated by this rule, for p = 7 and t = 2^phi((7-1)/2) = 4, is M(7) * M(4) = 1905. The next two, corresponding to p = 23 and 31, have 316 and 87 digits, respectively.

%C Rotkiewicz and Makowski (1966) proved that if p is a prime or a Fermat pseudoprime to base 2 such that o(p), the multiplicative order of 2 modulo p, is odd (A014663 for primes, A367230 for pseudoprimes), then for each positive k <= p/o(o(p)), if t = 2^(k*o(o(p))) then M(p)*M(t) is a Fermat pseudoprime to base 2. For example, for p = 7, p/o(o(7)) = 7/2, so for k = 1, 2 and 3 the resulting pseudoprimes are 1905, 8322945 and 2342736497361113055105, respectively.

%H Amiram Eldar, <a href="/A367229/b367229.txt">Table of n, a(n) for n = 1..242</a>

%H Andrzej Rotkiewicz and Andrzej Makowski, <a href="https://doi.org/10.5169/seals-24655">On Pseudoprime Numbers of the Form M_p M_t</a>, Elemente der Mathematik, Vol. 21 (1966), pp. 133-134.

%H Kazimierz Szymiczek, <a href="https://doi.org/10.4064/cm-13-2-259-263">On prime numbers p,q and r such that pq, pr, and qr are pseudoprimes</a>, Colloquium Mathematicum, Vol. 13 (1964), pp. 259-263; <a href="https://eudml.org/doc/266626">alternative link</a>.

%e a(1) = 1905 = (2^4-1) * (2^7-1).

%e a(2) = 15841 = (2^5-1) * (2^9-1).

%t With[{max = 110}, m = 2^Range[2, max] - 1; Sort@ Select[Times @@@ Subsets[m, {2}], # < m[[-1]] && PowerMod[2, # - 1, #] == 1 &]]

%Y Cf. A000010, A000225, A001567, A007522, A014663, A065341, A367230.

%K nonn

%O 1,1

%A _Amiram Eldar_, Nov 11 2023