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

%I #57 Sep 08 2020 02:14:41

%S 11,23,25,28,29,35,36,37,39,41,43,44,45,47,48,50,51,52,53,55,57,58,59,

%T 60,63,64,66,67,68,70,71,72,73,74,75,76,79,81,82,83,84,87,88,91,92,94,

%U 95,96,97,99,100,101,102,103,104,105,106,108,109,110,111,112

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

%C 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.

%C 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

%C 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

%C 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

%H Jeppe Stig Nielsen, <a href="/A143584/b143584.txt">Table of n, a(n) for n = 1..1000</a>

%o (PARI) isok(k) = my(m=polcyclo(k,2)); m/=gcd(m,k); m!=1&&!isprime(m) \\ _Jeppe Stig Nielsen_, Sep 01 2020

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

%Y Cf. A131952 (for the corresponding maximal overpseudoprimes).

%K nonn

%O 1,1

%A _Vladimir Shevelev_, Aug 25 2008

%E Name edited by _Michel Marcus_, Oct 06 2018

%E More terms from _Michel Marcus_, Oct 11 2018

%E Data for terms >= 100 corrected by _Jeppe Stig Nielsen_, Sep 01 2020