A064078 -id:A064078 - cp's OEIS frontend

A131952 a(n) is the maximal overpseudoprime q to base 2 such that the multiplicative order of 2 mod q equals A143584(n).

2047, 8388607, 1082401, 3277, 536870911, 8727391, 4033, 137438953471, 9588151, 2199023255551, 8796093022207, 838861, 14709241, 140737488355327, 65281, 1016801, 2454285751, 13421773, 9007199254740991, 567767102431, 39268347319, 178956971, 576460752303423487, 80581

Offset: 1

Vladimir Shevelev, Aug 26 2008

nonn

Or composite terms of A064078.

			For q=256999, 486737, 2304167 and 536870911, the multiplicative order of 2 mod q is A143584(5) = 29, so a(5) = 536870911.

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

Cf. A143584, A064078, A141232, A122929, A141629, A002326.

for(k=1,200,m=polcyclo(k,2);m/=gcd(m,k);m!=1&&!isprime(m)&&print1(m,", ")) \\ Jeppe Stig Nielsen, Aug 31 2020

More terms from Hugo Pfoertner, Aug 31 2020

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

Original entry on oeis.org

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

Vladimir Shevelev, Aug 25 2008

nonn

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

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

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

Cf. A131952 (for the corresponding maximal overpseudoprimes).

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

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

A261862 Terms in A261524 that are not multiples of earlier terms.

Original entry on oeis.org

3, 7, 31, 73, 85, 127, 2047, 3133, 4369, 8191, 11275, 49981, 60787, 76627, 121369, 131071, 140911, 178481, 262657, 486737, 524287, 599479, 1082401

Offset: 1

Joerg Arndt, Sep 07 2015

All Mersenne primes >= 3 are terms (see A001348).
From Jianing Song, Oct 13 2023: (Start)
In A261524 it is conjectured that degree(gcd( 1 + x^(Zs(d,2,1)), 1 + (1+x)^(Zs(d,2,1))) > 0 for every odd number d != 1, 15, 21, where Zs(d,2,1) is the d-th Zsigmondy number with parameters (2,1) (A064078). Since Zsigmondy numbers with different indices are coprime, if this conjecture is true, then there exists a term of this sequence k with ord(2,k) = d, and k must be a divisor of Zs(d,2,1) for every odd number d != 1, 15, 21. Here ord(a,k) is the multiplicative order of 2 modulo k. In A261524 we show that this conjecture is true for powers > 1 of a prime r >= 5, so there are infinitely many terms in this sequence.
One may conjecture that, if k is a term with ord(2,k) = d for even d, then k is a divisor of Zs(d,2,1)*Zs(d/2,2,1). This fails for (d,k) = (20,11275), (40,16962275), (44,165965585), ...
Conjecture: a term with ord(2,k) = d for even d exists if and only if d != 12 or 2*p, where p is any Mersonne exponent. (End)

Jianing Song, List of terms k of A261862 with ord(2,k) <= 47

Cf. A261524, A001348.

n=1; t= L= {}; While[n<5000, n+=2; If[ CoefficientList[ PolynomialGCD[1 + x^n, 1 + (x + 1)^n, Modulus->2], x] !={1}, If[ Intersection[Divisors@ n, t] == {}, Print@ AppendTo[L, n]]; AppendTo[t, n]]]; L (* Giovanni Resta, Sep 07 2015 *)

Corrected and extended by Giovanni Resta, Sep 09 2015

Terms a(17)-a(23) from Joerg Arndt, Sep 10 2015

A250208 Ratio of the primitive part of 2^n-1 to the product of primitive prime factors of 2^n-1.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 5, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 1

Eric Chen, Mar 02 2015

nonn

As with A178764, it can be shown that all terms are either 1 or prime.
a(2*3^n)   =  3 (n>=1).
a(4*5^n)   =  5 (n>=1).
a(3*7^n)   =  7 (n>=1).
a(10*11^n) = 11 (n>=1).
a(12*13^n) = 13 (n>=1).
a(8*17^n)  = 17 (n>=1).
a(18*19^n) = 19 (n>=1).
...
a(A014664(k)*prime(k)^n) = prime(k).
For other n (while Phi_n(2) is squarefree), a(n) = 1.
a(n) != 1 for n = {6, 18, 20, 21, 54, 100, 110, 136, 147, 155, 156, 162, ...}.
At least, a(A049093(n)) = 1. (In fact, since Phi_n(2) is not completely factored for n = 991, 1207, 1213, 1217, 1219, 1229, 1231, 1237, 1243, 1249, ..., so it is unknown whether they are squarefree or not, but it is likely that Phi_n(2) is squarefree for all n except 364 and 1755 (because it is likely 1093 and 3511 are the only two Wieferich primes), so a(991), a(1207), a(1213), ..., are likely to be 1.)

			a(11) = 1 since Phi_11(2) = (2^11-1)/(2-1) = 2047, and the primitive prime factors of 2^11-1 are 23 and 89, so a(11) = 2047/(23*89) = 1.
a(18) = 3 since Phi_18(2) = 2^6 - 2^3 + 1 = 57, and the only primitive prime factor of 2^18-1 is 19, so a(18) = 57/19 = 3.

Eric Chen, Table of n, a(n) for n = 1..990
Eric Chen, Table of n, a(n) for n = 1..1280 status (with unknown terms but all are conjectured to be 1)

Cf. A178764.

Cf. A001220, A237043, A093106, A049094, A049093, A014491, A072226, A161508.

a250208[n_] = If[n == 364, 1093, If[n == 1755, 3511, GCD[Cyclotomic[n, 2], n]]]; Table[a250208[n], {n, 0, 200}]

a(n) = if (n==364, 1093, if (n==1755, 3511, gcd(polcyclo(n, 2), n)));

isprimitive(p, n) = {for (r=1, n-1, if (((2^r-1) % p) == 0, return (0)); ); return (1); }
ppf(n) = {my(pf = factor(2^n-1)[,1]); prod(k=1,#pf, if (isprimitive(pf[k], n), pf[k], 1));}
a(n) = if (issquarefree(m=polcyclo(n,2)), gcd(m, n), m/ppf(n)); \\ Michel Marcus, Mar 06 2015

a(n) = A019320(n) / A064078(n) while Phi_n(2) is squarefree.
a(n) = GCD(Phi_n(2), n) while Phi_n(2) is squarefree.
Notice: a(364) = 1093, a(1755) = 3511. (See A001220.)

cp's OEIS Frontend

A131952 a(n) is the maximal overpseudoprime q to base 2 such that the multiplicative order of 2 mod q equals A143584(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

A261862 Terms in A261524 that are not multiples of earlier terms.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A250208 Ratio of the primitive part of 2^n-1 to the product of primitive prime factors of 2^n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula