A091242 -id:A091242 - cp's OEIS frontend

A238186 Primes with odd Hamming weight that as polynomials over GF(2) are reducible.

79, 107, 127, 151, 173, 179, 181, 199, 223, 227, 233, 251, 271, 307, 331, 367, 409, 421, 431, 439, 443, 457, 491, 521, 541, 569, 577, 641, 653, 659, 709, 727, 733, 743, 809, 823, 829, 919, 941, 947, 991, 997, 1009, 1021, 1087, 1109, 1129, 1171, 1187, 1201, 1213, 1231, 1249, 1259, 1301, 1321, 1327, 1361, 1373

Offset: 1

Joerg Arndt, Feb 19 2014

nonn

Subsequence of A091209 (see comments there).

			79 is a term because 79 = 1001111_2 which corresponds to the polynomial x^6 + x^3 + x^2 + x + 1, but over GF(2) we have x^6 + x^3 + x^2 + x + 1 = (x^2 + x + 1)*(x^4 + x^3 + 1). - _Jianing Song_, May 10 2021

Intersection of A000069 and A091209.
Intersection of A027697 and A091242.
Equals the set difference of A027697 and A091206.

forprime(p=2, 10^4, if( (hammingweight(p)%2==1) && ! polisirreducible( Mod(1,2)*Pol(binary(p)) ), print1(p,", ") ) );

A246157 Reducible polynomials over GF(2) which are both odd and odious when coded in binary, or equally, which have an odd number of nonzero terms, with the constant term being 1.

Original entry on oeis.org

21, 35, 49, 69, 79, 81, 93, 107, 121, 127, 133, 151, 155, 161, 173, 179, 181, 199, 205, 217, 223, 227, 233, 251, 259, 261, 265, 271, 273, 279, 289, 295, 307, 309, 321, 327, 331, 339, 341, 345, 367, 381, 385, 403, 405, 409, 421, 431, 439, 443, 453, 457, 465, 475, 481, 491, 493, 511

Offset: 1

Antti Karttunen, Aug 20 2014

Numbers n such that (A000035(n) * A010060(n) * A091247(n)) = 1.

This sequence is closed with respect to the self-inverse permutation A193231, meaning that A193231(a(n)) is always either the same or some other term of this sequence.

			35 in binary is 100011, which encodes polynomial x^5 + x + 1, which factorizes as (x^2 + x + 1)(x^3 + x^2 + 1) over GF(2) (35 = A048720(7,13)), thus it is reducible in that polynomial ring.
Also, it is odd (the least significant bit is 1, that is, the constant term is not zero) and also odious, as there are three 1-bits (nonzero terms) present. Thus, 35 is included in this sequence.

Antti Karttunen, Table of n, a(n) for n = 1..11665
Index entries for sequences operating on GF(2)[X]-polynomials

Intersection of A246156 and A246158.
Intersection of A091242 and A092246.
Cf. A000035, A010060, A091247, A048720, A193231.

A260427 Binary codes for polynomials (with coefficients 0 or 1) that are irreducible over Q, but reducible over GF(2).

Original entry on oeis.org

5, 17, 23, 29, 43, 53, 69, 71, 77, 79, 81, 83, 89, 101, 107, 113, 121, 127, 139, 149, 151, 163, 169, 173, 179, 181, 197, 199, 205, 209, 223, 227, 233, 251, 257, 261, 263, 265, 269, 271, 275, 277, 281, 289, 293, 295, 305, 307, 311, 317, 321, 323, 327, 329, 331, 337, 339, 347, 349, 353, 359, 367, 373, 377, 383, 389, 401

Offset: 1

Antti Karttunen, Jul 26 2015

nonn

Antti Karttunen, Table of n, a(n) for n = 1..16972

Intersection of A091242 and A206074.
Subsequence: A260428.
Cf. also A260426, A206075.

okQ[n_] := Module[{id, pol, x}, id = IntegerDigits[n, 2] // Reverse; pol = id.x^Range[0, Length[id] - 1]; IrreduciblePolynomialQ[pol] && !IrreduciblePolynomialQ[pol, Modulus -> 2]];
Select[Range[1000], okQ] (* Jean-François Alcover, Feb 06 2023 *)

isA260427(n) = (polisirreducible( Pol(binary(n)) ) && !polisirreducible(Pol(binary(n))*Mod(1, 2)));
n = 0; i = 0; while(n < 65537, n++; if(isA260427(n), i++; write("b260427.txt", i, " ", n)));

A260428 Composite numbers whose binary representations encode a polynomial (with coefficients 0 or 1) which is irreducible over Q, but reducible over GF(2).

Original entry on oeis.org

69, 77, 81, 121, 169, 205, 209, 261, 265, 275, 289, 295, 305, 321, 323, 327, 329, 339, 377, 405, 407, 437, 453, 473, 475, 481, 493, 517, 533, 551, 553, 559, 565, 575, 581, 583, 595, 625, 649, 667, 671, 689, 703, 707, 737, 747, 749, 755, 763, 767, 779, 781, 785, 805, 815, 833, 835, 851, 855, 861, 869, 893, 905

Offset: 1

Antti Karttunen, Jul 26 2015

nonn

Antti Karttunen, Table of n, a(n) for n = 1..11585

Intersection of A002808 and A260427.
Intersection of A091212 and A206074.
Intersection of A091242 and A206075.
Complement of A257688 in A206074.

f:= proc(n) local L,p,x;
  if isprime(n) then return false fi;
  L:= convert(n,base,2);
  p:= add(L[i]*x^(i-1),i=1..nops(L));
  irreduc(p) and not (Irreduc(p) mod 2);
end proc:
select(f, [$2..10000]); # Robert Israel, Jul 27 2015

okQ[n_] := CompositeQ[n] && Module[{id, pol, x}, id = IntegerDigits[n, 2] // Reverse; pol = id.x^Range[0, Length[id]-1]; IrreduciblePolynomialQ[pol] && !IrreduciblePolynomialQ[pol, Modulus -> 2]];
Select[Range[1000], okQ] (* Jean-François Alcover, Feb 06 2023 *)

isA260428(n) = (polisirreducible( Pol(binary(n)) ) && !polisirreducible(Pol(binary(n))*Mod(1, 2)) && !isprime(n));
n = 0; i = 0; while(n < 65537, n++; if(isA260428(n), i++; write("b260428.txt", i, " ", n)));

A305903 Filter sequence for all such sequences b, for which b(A014580(k)) = constant for all k >= 3.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 7, 11, 7, 12, 13, 14, 15, 16, 7, 17, 18, 19, 20, 21, 7, 22, 23, 24, 25, 26, 7, 27, 28, 29, 30, 31, 7, 32, 33, 34, 7, 35, 36, 37, 38, 39, 7, 40, 41, 42, 43, 44, 45, 46, 7, 47, 48, 49, 7, 50, 7, 51, 52, 53, 54, 55, 7, 56, 57, 58, 59, 60, 7, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 7, 74, 75, 76, 7, 77, 78, 79, 80, 81, 7

Offset: 1

Antti Karttunen, Jun 14 2018

nonn

Restricted growth sequence transform of A305900(A091203(n)).
This is GF(2)[X] analog of A305900.
For all i, j:
  a(i) = a(j) => A304529(i) = A304529(j) => A305788(i) = A305788(j).
  a(i) = a(j) => A268389(i) = A268389(j).

Antti Karttunen, Table of n, a(n) for n = 1..100000
Index entries for sequences operating on GF(2)[X]-polynomials

Cf. A091203, A268389, A278233, A304529, A305788, A305900.

up_to = 1000;
A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));
prepare_v091226(up_to) = { my(v = vector(up_to), c=0); for(i=1,up_to,c += A091225(i); v[i] = c); (v); }
v091226 = prepare_v091226(up_to);
A091226(n) = if(!n,n,v091226[n]);
A305903(n) = if(n<7,n,if(A091225(n),7,3+n-A091226(n)));

For n < 7, a(n) = n, for >= 7, a(n) = 7 when n is in A014580[3..] (= 7, 11, 13, 19, 25, 31, ...), and a(n) = 3+n-A091226(n) when n is in A091242[4..] (= 8, 9, 10, 12, 14, 15, ...).

A091243 Differences between consecutive reducible GF(2)[X]-polynomials.

Original entry on oeis.org

1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 1

Antti Karttunen, Jan 03 2004

nonn

Analogous to A073783.

First differences of A091242. a(n) = A091244(n)+1.

A091254 Reducible polynomials over GF(2) in binary format.

Original entry on oeis.org

100, 101, 110, 1000, 1001, 1010, 1100, 1110, 1111, 10000, 10001, 10010, 10100, 10101, 10110, 10111, 11000, 11010, 11011, 11100, 11101, 11110, 100000, 100001, 100010, 100011, 100100, 100110, 100111, 101000, 101010, 101011, 101100

Offset: 1

Antti Karttunen, Jan 03 2004

nonn

a(n) = A007088(A091242(n)). Cf. A058943.

A316970 Reducible binary polynomials P of degree n>0 with P dividing the polynomial X^(2^n-1)+1, evaluated at X=2 (pseudo-primes in the ring GF(2)[X]).

Original entry on oeis.org

83, 101, 127, 279, 443, 465, 1137, 1207, 1219, 1395, 1453, 1503, 1547, 1561, 1653, 1667, 1787, 1897, 1903, 1975, 2013, 4111, 4169, 4191, 4231, 4255, 4377, 4415, 4445, 4585, 4599, 4673, 4681, 4699, 4763, 4779, 4819, 4849, 4867, 4881, 4895, 4917, 5013, 5021, 5113, 5167, 5173, 5187, 5207, 5339, 5389, 5433, 5447

Offset: 1

Francois R. Grieu, Jul 17 2018

nonn

If a binary polynomial P of degree n is irreducible, then demonstrably P divides the polynomial X^(2^n-1)+1.
All irreducible polynomials A014580 pass this test, requiring O(n^3) bit operations and O(n) bits with classical algorithms.
Polynomials which pass this test but are not irreducible form the sequence.
Analog for GF(2)[X] of Fermat pseudoprimes A001567.
When P includes the constant term 1 (as all primitive polynomials do), the test is equivalent to X^(2^n)=X(mod P), which is easier to compute.

			83, that is 1010011 in binary, represents the polynomial P(X)=X^6+X^4+X+1 of degree n=6. It is in the sequence because X^63+1 == 0 (mod P), and P is reducible since P(X)=(X+1)(X^2+X+1)(X^3+X+1) in GF(2)[X].

Francois R. Grieu, Test of irreducibility of a binary polynomial, Math StackExchange July 2018.
Index entries for sequences related to polynomials in ring GF(2)[X]

Cf. A014580. Subsequence of A091242.

For[p=3,p<5449,p+=2,P=0;Y=1;m=p;While[m>0,If[OddQ[m],P+=Y;m-=1];Y*=x;m/=2];If[PolynomialRemainder[x^(2^Exponent[P,x]-1),P,x,Modulus->2]==1&&!IrreduciblePolynomialQ[P,Modulus->2],Print[p]]]

cp's OEIS Frontend

A238186 Primes with odd Hamming weight that as polynomials over GF(2) are reducible.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A246157 Reducible polynomials over GF(2) which are both odd and odious when coded in binary, or equally, which have an odd number of nonzero terms, with the constant term being 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A260427 Binary codes for polynomials (with coefficients 0 or 1) that are irreducible over Q, but reducible over GF(2).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A260428 Composite numbers whose binary representations encode a polynomial (with coefficients 0 or 1) which is irreducible over Q, but reducible over GF(2).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A305903 Filter sequence for all such sequences b, for which b(A014580(k)) = constant for all k >= 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A091243 Differences between consecutive reducible GF(2)[X]-polynomials.

Views

Author

Keywords

Comments

Links

Crossrefs

A091254 Reducible polynomials over GF(2) in binary format.

Views

Author

Keywords

Links

Crossrefs

A316970 Reducible binary polynomials P of degree n>0 with P dividing the polynomial X^(2^n-1)+1, evaluated at X=2 (pseudo-primes in the ring GF(2)[X]).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica