A246158 -id:A246158 - cp's OEIS frontend

A091242 Reducible polynomials over GF(2), coded in binary.

4, 5, 6, 8, 9, 10, 12, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 26, 27, 28, 29, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 43, 44, 45, 46, 48, 49, 50, 51, 52, 53, 54, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 71, 72, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 88

Offset: 1

Antti Karttunen, Jan 03 2004

nonn

"Coded in binary" means that a polynomial a(n)*X^n+...+a(0)*X^0 over GF(2) is represented by the binary number a(n)*2^n+...+a(0)*2^0 in Z (where a(k)=0 or 1). - M. F. Hasler, Aug 18 2014
The reducible polynomials in GF(2)[X] are the analog to the composite numbers A002808 in the integers.
It follows that the sequence is closed under application of A048720(.,.), which effects multiplication of the coded polynomials. It is also closed under application of blue code, A193231. The majority of the terms are coded multiples of X^1 (represented by 2) and/or X^1+1 (represented by 3): see A005843 and A001969 respectively. A246157 lists the other terms. - Peter Munn, Apr 20 2021

			For example, 5 = 101 in binary encodes the polynomial x^2+1 which is factored as (x+1)^2 in the polynomial ring GF(2)[X].

Robert Israel, Table of n, a(n) for n = 1..10000
Antti Karttunen, Scheme-program for computing this sequence.
Index entries for sequences operating on GF(2)[X]-polynomials

Inverse: A091246. Almost complement of A014580. Union of A091209 & A091212. First differences: A091243. Characteristic function: A091247. In binary format: A091254.
Number of degree-n reducible polynomials: A058766.
Subsequences: A001969\{0,3}, A005843\{0,2}, A246156, A246157, A246158, A316970.
Cf. A002808, A048720, A193231.

filter:= proc(n) local L;
  L:= convert(n,base,2);
  not Irreduc(add(L[i]*x^(i-1),i=1..nops(L))) mod 2
end proc:
select(filter, [$2..200]); # Robert Israel, Aug 30 2018

okQ[n_] := Module[{x, id = IntegerDigits[n, 2] // Reverse}, !IrreduciblePolynomialQ[id.x^Range[0, Length[id]-1], Modulus -> 2]];
Select[Range[2, 200], okQ] (* Jean-François Alcover, Jan 04 2022 *)

Edited by M. F. Hasler, Aug 18 2014

A246156 Odd reducible polynomials over GF(2), coded in binary. (Polynomials with the constant term 1 that are reducible over GF(2)).

Original entry on oeis.org

5, 9, 15, 17, 21, 23, 27, 29, 33, 35, 39, 43, 45, 49, 51, 53, 57, 63, 65, 69, 71, 75, 77, 79, 81, 83, 85, 89, 93, 95, 99, 101, 105, 107, 111, 113, 119, 121, 123, 125, 127, 129, 133, 135, 139, 141, 147, 149, 151, 153, 155, 159, 161, 163, 165, 169, 173, 175, 177, 179, 181, 183, 187, 189, 195, 197, 199, 201

Offset: 1

Antti Karttunen, Aug 20 2014

Self-inverse permutation A193231 maps each term of this sequence to some term of A246158 and vice versa.

			5, which is 101 in binary, encodes polynomial x^2 + 1, which factorizes as (x+1)(x+1) over GF(2), (5 = A048720(3,3)), thus it is reducible in that polynomial ring. Also, its constant term is 1, (not zero), thus 5 is a member of this sequence.

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

Intersection of A091242 and A005408 (odd numbers).

A246157 is a subsequence. Cf. also A048720, A193231, A246158.

filter:= proc(n) local L,p,x;
    L:= convert(n,base,2);
    p:= add(L[i]*x^(i-1),i=1..nops(L));
    not (Irreduc(p) mod 2)
end proc:
select(filter,[seq(2*i+1,i=1..100)]); # Robert Israel, Aug 21 2014

A246163 Permutation of natural numbers: a(1) = 1, a(A014580(n)) = A065621(1+a(n)), a(A091242(n)) = A048724(a(n)), where A065621(n) and A048724(n) give the reversing binary representation of n and -n, respectively, and A014580 resp. A091242 are the binary coded irreducible resp. reducible polynomials over GF(2).

Original entry on oeis.org

1, 2, 7, 3, 6, 9, 8, 5, 10, 27, 4, 24, 11, 15, 30, 45, 12, 40, 26, 29, 17, 34, 119, 20, 25, 120, 46, 39, 51, 102, 14, 153, 60, 43, 136, 114, 31, 105, 85, 170, 44, 18, 427, 68, 125, 408, 13, 150, 33, 187, 255, 510, 116, 54, 41, 765, 204, 135, 28, 680, 16, 23, 442, 99, 461, 257, 35, 514, 156, 90, 123, 1799, 118, 340, 393, 36

Offset: 1

Antti Karttunen, Aug 19 2014

nonn

This is an instance of entanglement permutation, where the two complementary pairs to be entangled with each other are A014580/A091242 (binary codes for irreducible and reducible polynomials over GF(2)) and A065621/A048724, the latter which themselves are permutations of A000069/A001969 (odious and evil numbers), which means that this permutation shares many properties with A246161.
Because 3 is the only evil number in A014580, it implies that, apart from a(3)=7, odious numbers occur in odious positions only (along with many evil numbers that also occur in odious positions).
Furthermore, all terms of A246158 reside in infinite cycles, and apart from 4 and 8, all of them reside in separate cycles. The infinite cycle containing 4 and 8 goes as: ..., 2091, 97, 47, 13, 11, 4, 3, 7, 8, 5, 6, 9, 10, 27, 46, 408, 2535, ... and it is only because a(3) = 7, that it can temporarily switch back from evil terms to odious terms, until right after a(8) = 5 it is finally doomed to the eternal evilness.
Please see also the comments at A246201 and A246161.

Inverse: A246164.
Similar or related permutations: A246205, A193231, A246201, A234026, A245701, A234612, A246161, A246203.
Cf. A010060, A014580, A048724, A065621, A091225, A091226, A091245.

a(1) = 1, and for n > 1, if n is in A014580, a(n) = A065621(1+a(A091226(n))), otherwise a(n) = A048724(a(A091245(n))).
As a composition of related permutations:
a(n) = A193231(A246201(n)).
a(n) = A234026(A245701(n)).
a(n) = A234612(A246161(n)).
a(n) = A193231(A246203(A193231(n))).
Other identities:
For all n > 1, A010060(a(n)) = A091225(n). [Maps binary representations of irreducible GF(2) polynomials (A014580) to odious numbers and the corresponding representations of reducible polynomials (A091242) to evil numbers, in some order].

A246161 Permutation of positive integers: a(1) = 1, a(A014580(n)) = A000069(1+a(n)), a(A091242(n)) = A001969(1+a(n)), where A000069 and A001969 are the odious and evil numbers, and A014580 resp. A091242 are the binary coded irreducible resp. reducible polynomials over GF(2).

Original entry on oeis.org

1, 2, 4, 3, 5, 9, 8, 6, 10, 18, 7, 17, 11, 12, 20, 36, 15, 34, 19, 23, 24, 40, 72, 30, 16, 68, 39, 46, 48, 80, 13, 144, 60, 33, 136, 78, 21, 92, 96, 160, 37, 27, 288, 120, 66, 272, 14, 156, 43, 184, 192, 320, 75, 54, 35, 576, 240, 132, 22, 544, 25, 29, 312, 86, 368, 384, 41

Offset: 1

Antti Karttunen, Aug 17 2014

nonn

This is an instance of entanglement permutation, where the two complementary pairs to be entangled with each other are A014580/A091242 (binary codes for irreducible and reducible polynomials over GF(2)) and A000069/A001969 (odious and evil numbers).
Because 3 is the only evil number in A014580, it implies that, apart from a(3)=4, odious numbers occur in odious positions only (along with many evil numbers that also occur in odious positions).
Note that the two values n=21 and n=35 given in the Example section both encode polynomials reducible over GF(2) and have an odd number of 1-bits in their binary representation (that is, they are both terms of A246158). As this permutation maps all terms of A091242 to the terms of A001969, and apart from a single exception 3 (which here is in a closed cycle: a(3) = 4, a(4) = 3), no term of A001969 is a member of A014580, so they must be members of A091242, thus successive iterations a(21), a(a(21)), a(a(a(21))), etc. always yield some evil number (A001969), so the cycle can never come back to 21 as it is an odious number, so that cycle must be infinite.
On the other hand, when we iterate with the inverse of this permutation, A246162, starting from 21, we see that its successive pre-images 37, 41, 67, 203, 5079 [e.g., 21 = a(a(a(a(a(5079)))))] are all irreducible and thus also odious.
In each such infinite cycle, there can be at most one term which is both reducible (in A091242) and odious (in A000069), i.e. in A246158, thus 21 and 35 must reside in different infinite cycles.
The sequence of fixed points begin as: 1, 2, 5, 19, 54, 71, 73, 865.
Question: apart from them and transposition (3 4) are there any more instances of finite cycles?

			Consider n=21. In binary it is 10101, encoding for polynomial x^4 + x^2 + 1, which factorizes as (x^2 + x + 1)(x^2 + x + 1) over GF(2), in other words, 21 = A048720(7,7). As such, it occurs as the 14th term in A091242, reducible polynomials over GF(2), coded in binary.
By definition of this permutation, a(21) is thus obtained as A001969(1+a(14)). 14 in turn is 8th term in A091242, thus a(14) = A001969(1+a(8)). In turn, 8 = A091242(4), thus a(8) = A001969(1+a(4)), and 4 = A091242(1).
By working the recursion back towards the toplevel, the result is a(21) = A001969(1+A001969(1+A001969(1+A001969(1+1)))) = 24.
Consider n=35. In binary it is 100011, encoding for polynomial x^5 + x + 1, which factorizes as (x^2 + x + 1)(x^3 + x^2 + 1) over GF(2), in other words, 35 = A048720(7,13). As such, it occurs as the 26th term in A091242, thus a(35) = A001969(1+a(26)), and as 26 = A091242(18) and 18 = A091242(12) and 12 = A091242(7) and 7 = A014580(3) [the polynomial x^2 + x + 1 is irreducible over GF(2)], and 3 = A014580(2) and 2 = A014580(1), we obtain the result as a(35) = A001969(1+A001969(1+A001969(1+A001969(1+A000069(1+A000069(1+A000069(2))))))) = 136.

Inverse: A246162.
Related permutations: A003188, A234612, A245701, A233280, A246163, A246201.
Cf. A000069, A001969, A010060, A014580, A091225, A091226, A091242, A091245, A246158.

a(1) = 1, and for n > 1, if n is in A014580, a(n) = A000069(1+a(A091226(n))), otherwise a(n) = A001969(1+a(A091245(n))).
As a composition of related permutations:
a(n) = A233280(A245701(n)).
a(n) = A003188(A246201(n)).
a(n) = A234612(A246163(n)).
Other identities:
For all n > 1, A010060(a(n)) = A091225(n). [Maps binary representations of irreducible GF(2) polynomials (A014580) to odious numbers and the corresponding representations of reducible polynomials (A091242) to evil numbers, in some order].

A246162 Permutation of natural numbers: a(1) = 1, a(A000069(n)) = A014580(a(n-1)), a(A001969(n)) = A091242(a(n-1)), where A000069 and A001969 are the odious and evil numbers, and A014580 resp. A091242 are the binary coded irreducible resp. reducible polynomials over GF(2).

Original entry on oeis.org

1, 2, 4, 3, 5, 8, 11, 7, 6, 9, 13, 14, 31, 47, 17, 25, 12, 10, 19, 15, 37, 59, 20, 21, 61, 185, 42, 319, 62, 24, 87, 137, 34, 18, 55, 16, 41, 97, 27, 22, 67, 229, 49, 415, 76, 28, 103, 29, 109, 425, 78, 1627, 222, 54, 283, 3053, 373, 79, 433, 33, 131, 647, 108, 1123, 166, 45, 203, 26, 91, 379, 71, 23

Offset: 1

Antti Karttunen, Aug 17 2014. Erroneous comment corrected Aug 20 2014

nonn

This is an instance of entanglement-permutation, where the two complementary pairs to be entangled with each other are A000069/A001969 (odious and evil numbers) and A014580/A091242 (binary codes for irreducible and reducible polynomials over GF(2)).

Because 3 is the only evil number in A014580, it implies that, apart from a(4)=3, all other odious positions contain an odious number. There are also odious numbers in some of the evil positions, precisely all the terms of A246158 in some order, together with all evil numbers larger than 3. (Permutation A246164 has the same property, except there a(7)=3.) See comments in A246161 for more details how this affects the cycle structure of these permutations.

Inverse: A246161.
Related permutations: A006068, A233279, A234612, A237427, A245702, A246202, A246164.
Cf. A010060, A014580, A091242, A115384, A245710.

a(1) = 1, and for n > 1, if A010060(n) = 1 [i.e. n is one of the odious numbers, A000069], a(n) = A014580(a(A115384(n)-1)), otherwise, a(n) = A091242(a(A245710(n))).
As a composition of related permutations:
a(n) = A245702(A233279(n)).
a(n) = A246202(A006068(n)).
a(n) = A246164(A234612(n)).
For all n > 1, A091225(a(n)) = A010060(n). [Maps odious numbers to binary representations of irreducible GF(2) polynomials (A014580) and evil numbers to the corresponding representations of reducible polynomials (A091242), in some order].

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.

cp's OEIS Frontend

A091242 Reducible polynomials over GF(2), coded in binary.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A246156 Odd reducible polynomials over GF(2), coded in binary. (Polynomials with the constant term 1 that are reducible over GF(2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A246161 Permutation of positive integers: a(1) = 1, a(A014580(n)) = A000069(1+a(n)), a(A091242(n)) = A001969(1+a(n)), where A000069 and A001969 are the odious and evil numbers, and A014580 resp. A091242 are the binary coded irreducible resp. reducible polynomials over GF(2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A246162 Permutation of natural numbers: a(1) = 1, a(A000069(n)) = A014580(a(n-1)), a(A001969(n)) = A091242(a(n-1)), where A000069 and A001969 are the odious and evil numbers, and A014580 resp. A091242 are the binary coded irreducible resp. reducible polynomials over GF(2).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

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