A143584 Integers that are equal to the multiplicative order of 2 modulo some overpseudoprime to base 2.

11, 23, 25, 28, 29, 35, 36, 37, 39, 41, 43, 44, 45, 47, 48, 50, 51, 52, 53, 55, 57, 58, 59, 60, 63, 64, 66, 67, 68, 70, 71, 72, 73, 74, 75, 76, 79, 81, 82, 83, 84, 87, 88, 91, 92, 94, 95, 96, 97, 99, 100, 101, 102, 103, 104, 105, 106, 108, 109, 110, 111, 112

Offset: 1

Author

Vladimir Shevelev, Aug 25 2008

Keywords

• nonn

Comments

A064078(a(n)) is a composite number. The sequence has a positive density since it contains, in particular, numbers of the form 8n+20 for n >= 1 (C. Pomerance, private correspondence). Since, e.g., 38 is not in the sequence, there is not an overpseudoprime m such that ord_m(2)=38.

Phi_{a(n)}(2), the a(n)-th cyclotomic polynomial of x evaluated at x=2 has at least 2 distinct prime factors that are not prime factors of the Phi_k(2) for any positive integer k < a(n). For example, Phi_11(2) = 2^11 - 1 = 2047 = 23 * 89 and Phi_25(2) = 2^20 + 2^15 + 2^10 + 2^5 + 1 = 1082401 = 601 * 1801. Note that p = a(n) is prime if and only if Phi_p(2) = 2^p - 1 is composite. - David Terr, Sep 09 2018

It is easy to prove the statement above. We use the fact that Phi_j(n) and Phi_k(n) are coprime whenever j and k are coprime as well as the fact that an overpseudoprime has at least 2 distinct prime factors. - David Terr, Oct 10 2018

A number k is included iff either 2^k-1 has more than one primitive prime factor (cf. A086251, A161508) or the only primitive prime factor of 2^k-1 is a Wieferich prime (no examples known). - Jeppe Stig Nielsen, Sep 01 2020

Links

• Jeppe Stig Nielsen, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A002326, A014664, A064078, A086251, A122929, A141232, A161508.

Cf. A131952 (for the corresponding maximal overpseudoprimes).

Programs

PARI

isok(k) = my(m=polcyclo(k,2)); m/=gcd(m,k); m!=1&&!isprime(m) \\ Jeppe Stig Nielsen, Sep 01 2020

Extensions

Name edited by Michel Marcus, Oct 06 2018

More terms from Michel Marcus, Oct 11 2018

Data for terms >= 100 corrected by Jeppe Stig Nielsen, Sep 01 2020