A071642 -id:A071642 - cp's OEIS frontend

A071566 Numbers k such that x^k + x^(k-1) + x^(k-2) + ... + x + 1 is irreducible over GF(11).

2, 12, 16, 22, 28, 30, 40, 46, 58, 66, 70, 72, 100, 102, 108, 148, 162, 172, 178, 196, 222, 232, 250, 276, 280, 292, 330, 366, 372, 382, 418, 442, 460, 462, 466, 486, 498, 556, 568, 586, 592, 598, 600, 612, 618, 642, 646, 672, 676, 682, 700, 718, 760, 768

Offset: 1

Robert G. Wilson v, Jun 22 2002

Cf. A071642.

a(n) = A019339(n+1) - 1. - Ralf Stephan, Dec 26 2004

A136250 Numbers n such that optimal normal basis exists for GF(2^n) over GF(2).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 9, 10, 11, 12, 14, 18, 23, 26, 28, 29, 30, 33, 35, 36, 39, 41, 50, 51, 52, 53, 58, 60, 65, 66, 69, 74, 81, 82, 83, 86, 89, 90, 95, 98, 99, 100, 105, 106, 113, 119, 130, 131, 134, 135, 138, 146, 148, 155, 158, 162, 172, 173, 174, 178, 179, 180, 183, 186

Offset: 1

Joerg Arndt, Mar 17 2008

nonn

An optimal normal basis for GF(2^n) is either of type-1 (A071642) or type-2 (A054639).

Joerg Arndt, Mar 17 2008, Table of n, a(n) for n = 1..240
Joerg Arndt, Matters Computational (The Fxtbook)

Cf. A071642 and A054639.

Edited by N. J. A. Sloane, Apr 08 2008

A333468 Length of the largest disjoint cycle of the permutation that results from the composition of first n circular shifts.

Original entry on oeis.org

1, 2, 2, 3, 5, 6, 3, 4, 9, 4, 7, 10, 9, 14, 4, 5, 7, 18, 8, 10, 7, 7, 14, 11, 6, 26, 12, 9, 29, 30, 5, 6, 33, 11, 21, 6, 11, 15, 22, 27, 41, 6, 17, 8, 8, 7, 22, 24, 15, 50, 28, 8, 53, 18, 22, 14, 25, 9, 15, 55, 14, 50, 6, 7, 65, 11, 19, 34, 69, 23, 35, 14, 22, 74, 10

Offset: 1

Richard Locke Peterson, Mar 22 2020

nonn

Size of the largest part of the partition of n that is associated with the cycle structure of the permutation given by the permutation product (1)*(1,2)*(1,2,3)*...*(1,2,3,...n) after the product is rewritten as the product of disjoint cycles, where * means functional composition, and the permutations are written in cycle form.
Also see Circular shift on Wikipedia.
For n>1, a(n) is always greater than 1, since the given product can never be the identity permutation on the set {1,2,...,n}, which is the only permutation associated with the partition <1,1,...,1> (1 repeated n times).
Connections: The image of 1 in each resulting permutation appears to be the same as the numbers in A003602. The number of parts in the partition associated with each resulting permutation appear to match the numbers in A006694.
The LCM of all cycle lengths gives A051732(n+1). - Alois P. Heinz, Apr 08 2020

			For n=3, the permutation (1)*(1,2)*(1,2,3)=(1)*(2,3), which is associated with the partition <2,1> of 3. The size of the largest part is 2, so a(3)=2.
For n=11, the permutation (1)*(1,2)*..*(1,2,..11)=(1,2,7,5)*(3,4,8,10,11,6,9) when rewritten as the product of disjoint cycles, which is associated with the partition <7,4> of 11. The size of the largest part is 7, so a(11)=7.

Alois P. Heinz, Table of n, a(n) for n = 1..3000
Wikipedia, Circular shift

Cf. A003602, A006694, A051732, A071642, A163782.

Follow(s, f)={my(t=f(s), k=1); while(t>s, k++; t=f(t)); if(s==t, k, 0)}
mkp(n)={my(v=vector(n,i,i)); for(k=1, n, my(t=v[1]); for(i=1, k-1, v[i]=v[i+1]); v[k]=t); v}
a(n)={my(v=mkp(n), m=0); for(i=1, n, m=max(m, Follow(i, j->v[j]))); m} \\ Andrew Howroyd, Mar 27 2020

a(n) = n <=> n in { A163782 } union { 1 }. - Alois P. Heinz, Apr 08 2020

Terms a(20) and beyond from Andrew Howroyd, Mar 27 2020

A335379 a(n) is the number of Mersenne prime (irreducible) polynomials M = x^k(x+1)^(n-k)+1 of degree n in GF(2)[x] (k goes from 1 to n-1) such that Phi_7(M) has an odd number of prime divisors (omega(Phi_7(M)) is odd).

Original entry on oeis.org

1, 2, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2

Offset: 2

Luis H. Gallardo, Jun 03 2020

nonn

Phi_7(x)=1+x+x^2+x^3+x^4+x^5+x^6, is the 7th cyclotomic polynomial; omega(P(x)) counts the 2 X 2 distinct irreducible divisors of the binary polynomial P(x) in GF(2)[x].

It is surprising that a(n) be so small (conjecturally it is always 1 or 2). The sequence appeared when working the special case p=7 of a conjecture (see Links) about prime divisors in GF(2)[x] of the composed cyclotomic polynomial Phi_p(M), where p is a prime number and M is a Mersenne irreducible polynomial.

			For n=4 a(4)= 0 (the sequence begins a(2)=1,a(3)=2,...), since there is no Mersenne polynomial M of degree 4 in GF(2)[x] such that omega(Phi_7(M)) is odd.

Antti Karttunen, Table of n, a(n) for n = 2..1700
L. H. Gallardo and O. Rahavandrainy, On Mersenne polynomials over GF(2), Finite Fields Appl. 59 (2019), 284-296.

Cf. A057460 (A074710), A071642, A267918, A272486, A162570.

a(n)={my(phi7=polcyclo(7)); sum(k=1, n-1, my(p=Mod(x^k * (x+1)^(n-k) + 1, 2)); polisirreducible(p) && #(factor(subst(phi7, x, p))~)%2)} \\ Andrew Howroyd, Jun 04 2020

Terms a(22) and beyond from Andrew Howroyd, Jun 04 2020

A056679 Primes p such that 1 + x + Sum_{q prime <= p} x^q is irreducible over GF(2).

Original entry on oeis.org

2, 5, 17, 59, 73, 269, 3769, 4327

Offset: 1

Robert G. Wilson v, Nov 10 2000

			a(3) = 17 because 1 + x + x^2 + x^3 + x^5 + x^7 + x^11 + x^13 + x^17 is irreducible over GF(2).

Cf. A071642.

lista(nn) = {my(f=1+x); forprime(p=2, nn, f+=x^p; if(polisirreducible(Mod(1, 2)*f), print1(p, ", "))); } \\ Jinyuan Wang, Apr 15 2020

a(7)-a(8) from Jinyuan Wang, Apr 15 2020

A071428 Numbers n such that x^n + x^(n-1) + x^(n-2) + ... + x + 1 is irreducible over GF(3).

Original entry on oeis.org

4, 6, 16, 18, 28, 30, 42, 52, 78, 88, 100, 112, 126, 136, 138, 148, 162, 172, 196, 198, 210, 222, 232, 256, 268, 280, 282, 292, 316, 330, 352, 378, 388, 400, 448, 460, 462, 486, 508, 520, 556, 568, 570, 592, 606, 616, 630, 640, 652, 676, 690, 700, 738, 750

Offset: 1

Robert G. Wilson v, Jun 22 2002

n such that n+1 is a prime with primitive root 3 (A019334 except for the first term). [Joerg Arndt, Jul 05 2011]

Cf. A071642.

for(n=2,1000,if(polisirreducible(Mod(1,3)*sum(e=0,n,x^e)),print1(n+1,", "))) /* Joerg Arndt, Jul 05 2011 */

forprime(p=5,1000,if(znorder(Mod(3,p))==p-1,print1(p-1,", "))) /* much faster */ /* Joerg Arndt, Jul 05 2011 */

A071565 Numbers k such that x^k + x^(k-1) + x^(k-2) + ... + x + 1 is irreducible over GF(7).

Original entry on oeis.org

4, 10, 12, 16, 22, 40, 60, 66, 70, 78, 88, 96, 100, 106, 126, 150, 162, 172, 178, 210, 228, 238, 240, 256, 262, 268, 292, 346, 348, 358, 378, 396, 430, 432, 442, 460, 490, 498, 508, 520, 546, 576, 592, 598, 600, 630, 658, 676, 682, 732, 738, 742, 760, 772

Offset: 1

Robert G. Wilson v, Jun 22 2002

Cf. A071642.

Cf. A019337. - Joerg Arndt, Apr 17 2020

a(n) = A019337(n+1) - 1. - Joerg Arndt, Apr 17 2020

cp's OEIS Frontend

A071566 Numbers k such that x^k + x^(k-1) + x^(k-2) + ... + x + 1 is irreducible over GF(11).

Views

Author

Keywords

Crossrefs

Formula

A136250 Numbers n such that optimal normal basis exists for GF(2^n) over GF(2).

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A333468 Length of the largest disjoint cycle of the permutation that results from the composition of first n circular shifts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A335379 a(n) is the number of Mersenne prime (irreducible) polynomials M = x^k(x+1)^(n-k)+1 of degree n in GF(2)[x] (k goes from 1 to n-1) such that Phi_7(M) has an odd number of prime divisors (omega(Phi_7(M)) is odd).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A056679 Primes p such that 1 + x + Sum_{q prime <= p} x^q is irreducible over GF(2).

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Extensions

A071428 Numbers n such that x^n + x^(n-1) + x^(n-2) + ... + x + 1 is irreducible over GF(3).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

PARI

A071565 Numbers k such that x^k + x^(k-1) + x^(k-2) + ... + x + 1 is irreducible over GF(7).

Views

Author

Keywords

Crossrefs

Formula