A246156 -id:A246156 - 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

A246201 Permutation of natural numbers: a(1) = 1, a(A014580(n)) = (2a(n))+1, a(A091242(n)) = 2a(n), where A014580(n) = binary code for n-th irreducible polynomial over GF(2), A091242(n) = binary code for n-th reducible polynomial over GF(2).

Original entry on oeis.org

1, 3, 7, 2, 6, 14, 15, 4, 12, 28, 5, 30, 13, 8, 24, 56, 10, 60, 29, 26, 16, 48, 112, 20, 31, 120, 58, 52, 32, 96, 9, 224, 40, 62, 240, 116, 25, 104, 64, 192, 57, 18, 448, 80, 124, 480, 11, 232, 50, 208, 128, 384, 114, 36, 61, 896, 160, 248, 27, 960, 17, 22, 464, 100, 416, 256, 49, 768, 228, 72, 122, 1792, 113, 320, 496, 54, 1920, 34, 44

Offset: 1

Antti Karttunen, Aug 19 2014

nonn

Because 2 is the only even term in A014580, it implies that, apart from a(2)=3, odd numbers occur in odd positions only (along with many even numbers that also occur in odd positions).
Note that for any value k in A246156, "Odd reducible polynomials over GF(2)": 5, 9, 15, 17, 21, 23, ..., a(k) will be even, and apart from 2, all other even numbers are mapped to some even number, so all those terms reside in infinite cycles. Furthermore, apart from 5 and 15, all of them reside in separate cycles. The infinite cycle containing 5 and 15 goes as: ..., 47, 11, 5, 6, 14, 8, 4, 2, 3, 7, 15, 24, 20, 26, 120, 7680, ... and it is only because a(2) = 3, that it can temporarily switch back from even terms to odd terms, until after a(15) = 24 it is finally doomed to the eternal evenness.
(Compare also to the comments given at A246161).

Inverse: A246202.
Similar or related permutations: A245701, A246161, A006068, A054429, A193231, A246163, A246203, A237427.
Cf. A091225, A091226, A091245.

a(1) = 1, and for n > 1, if A091225(n) = 1 [i.e. when n is in A014580], a(n) = 1 + (2*a(A091226(n))), otherwise a(n) = 2*a(A091245(n)).
As a composition of related permutations:
a(n) = A054429(A245701(n)).
a(n) = A006068(A246161(n)).
a(n) = A193231(A246163(n)).
a(n) = A246203(A193231(n)).
Other identities:
For all n > 1, A000035(a(n)) = A091225(n). [After 1 maps binary representations of reducible GF(2) polynomials to even numbers and the corresponding representations of irreducible polynomials to odd numbers, in some order. A246203 has the same property].

A246202 Permutation of natural numbers: a(1) = 1, a(2n) = A091242(a(n)), a(2n+1) = A014580(a(n)), where A091242(n) = binary code for n-th reducible polynomial over GF(2) and A014580(n) = binary code for n-th irreducible polynomial over GF(2).

Original entry on oeis.org

1, 4, 2, 8, 11, 5, 3, 14, 31, 17, 47, 9, 13, 6, 7, 21, 61, 42, 185, 24, 87, 62, 319, 15, 37, 20, 59, 10, 19, 12, 25, 29, 109, 78, 425, 54, 283, 222, 1627, 33, 131, 108, 647, 79, 433, 373, 3053, 22, 67, 49, 229, 28, 103, 76, 415, 16, 41, 27, 97, 18, 55, 34, 137, 39, 167, 134, 859, 98, 563, 494, 4225, 70, 375, 331, 2705, 264, 2011, 1832, 19891, 44

Offset: 1

Antti Karttunen, Aug 19 2014

This sequence can be represented as a binary tree. Each left hand child is produced as A091242(n), and each right hand child as A014580(n), when the parent contains n:
                                     |
                  ...................1...................
                 4                                       2
       8......../ \.......11                   5......../ \........3
      / \                 / \                 / \                 / \
     /   \               /   \               /   \               /   \
    /     \             /     \             /     \             /     \
  14       31         17       47          9       13          6       7
21  61   42  185    24  87   62  319     15 37   20  59      10 19   12 25
etc.
Because 2 is the only even term in A014580, it implies that, apart from a(3)=2, all other odd positions contain an odd number. There are also odd numbers in the even bisection, precisely all the terms of A246156 in some order, together with all even numbers larger than 2 that are also there. See also comments in A246201.

Inverse: A246201.
Similar or related permutations: A245702, A246162, A246164, A246204, A237126, A003188, A054429, A193231, A260422, A260426.
Cf. A014580, A091242, A091225, A246156.

allocatemem((2^31)+(2^30));
uplim = (2^25) + (2^24);
v014580 = vector(2^24);
v091242 = vector(uplim);
isA014580(n)=polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ This function from Charles R Greathouse IV
i=0; j=0; n=2; while((n < uplim), if(isA014580(n), i++; v014580[i] = n, j++; v091242[j] = n); n++)
A246202(n) = if(1==n, 1, if(0==(n%2), v091242[A246202(n/2)], v014580[A246202((n-1)/2)]));
for(n=1, 638, write("b246202.txt", n, " ", A246202(n)));
\\ Works with PARI Version 2.7.4. - Antti Karttunen, Jul 25 2015
(Scheme, with memoization-macro definec)
(definec (A246202 n) (cond ((< n 2) n) ((odd? n) (A014580 (A246202 (/ (- n 1) 2)))) (else (A091242 (A246202 (/ n 2))))))

a(1) = 1, a(2n) = A091242(a(n)), a(2n+1) = A014580(a(n)).
As a composition of related permutations:
a(n) = A245702(A054429(n)).
a(n) = A246162(A003188(n)).
a(n) = A193231(A246204(n)).
a(n) = A246164(A193231(n)).
a(n) = A260426(A260422(n)).
Other identities:
For all n > 1, A091225(a(n)) = A000035(n). [After 1, maps even numbers to binary representations of reducible GF(2) polynomials and odd numbers to the corresponding representations of irreducible polynomials, in some order. A246204 has the same property].

A246158 Odious reducible polynomials over GF(2), coded in binary. (Polynomials with an odd number of nonzero terms that are reducible over GF(2)).

Original entry on oeis.org

4, 8, 14, 16, 21, 22, 26, 28, 32, 35, 38, 42, 44, 49, 50, 52, 56, 62, 64, 69, 70, 74, 76, 79, 81, 82, 84, 88, 93, 94, 98, 100, 104, 107, 110, 112, 118, 121, 122, 124, 127, 128, 133, 134, 138, 140, 146, 148, 151, 152, 155, 158, 161, 162, 164, 168, 173, 174, 176, 179, 181, 182, 186, 188, 194, 196, 199, 200

Offset: 1

Antti Karttunen, Aug 20 2014

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

Each term belongs into a distinct infinite cycle in permutations like A246161/A246162 and A246163/A246164 apart from 4, which is in a finite cycle (3 4) of A246161/A246162 and 4 and 8 which both are in the same (infinite) cycle of A246163/A246164.

			4, which is 100 in binary, encodes polynomial x^2, which factorizes as (x)(x) over GF(2), (4 = A048720(2,2)), thus it is reducible in that polynomial ring. It also has an odd number of nonzero terms present (equally: odd number of 1-bits in its code), in this case just one, thus 4 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 A000069 (odious numbers).
A238186 and A246157 are subsequences.
Cf. also A048720, A246156, A193231, A246161, A246162, A246163, A246164.

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.

A246203 Permutation of natural numbers: a(n) = A246201(A193231(n)).

Original entry on oeis.org

1, 7, 3, 6, 2, 14, 15, 24, 8, 30, 13, 28, 5, 12, 4, 10, 56, 60, 29, 26, 16, 112, 48, 96, 9, 32, 52, 58, 120, 20, 31, 128, 208, 232, 50, 36, 61, 114, 384, 960, 17, 464, 22, 160, 896, 248, 27, 62, 240, 40, 224, 64, 104, 116, 25, 124, 80, 480, 11, 192, 57, 448, 18, 1536, 98, 456, 21, 928, 200, 512, 832, 3584, 121, 244, 144

Offset: 1

Antti Karttunen, Aug 19 2014

nonn

This permutation has the same cycle structure as A246163 has because this is its A193231-conjugate.
On the other hand, it shares with A246201 the following property:
Because 2 is the only even term in A014580, it implies that, apart from a(2)=7, odd numbers occur in odd positions only (along with many even numbers that also occur in odd positions).
Note that for any value k in A246156, "Odd reducible polynomials over GF(2)": 5, 9, 15, 17, 21, 23, ..., a(k) will be even, and apart from 2, all other even numbers are mapped to some even number, so all those terms reside in infinite cycles, and apart from 5 and 15, all of them reside in separate cycles. The infinite cycle containing 5 and 15 goes as: ..., 14523, 3889, 103, 59, 11, 13, 5, 2, 7, 15, 4, 6, 14, 12, 28, 58, 480, 3728, 3932416, ... and it is only because a(2) = 7, that it can temporarily switch back from even terms to odd terms, until right after a(15) = 4 it is finally doomed to the eternal evenness.
See also comments at A246161 and A246163.

Inverse: A246204.
Related permutations: A193231, A246201, A246161, A246163.
Cf. also A000035, A091225, A246156.

(define (A246203 n) (A246201 (A193231 n)))

a(n) = A246201(A193231(n)).
a(n) = A193231(A246163(A193231(n))).
Other identities:
For all n > 1, A000035(a(n)) = A091225(n). [After 1 maps binary representations of reducible GF(2) polynomials to even numbers and the corresponding representations of irreducible polynomials to odd numbers, in some order].

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A246201 Permutation of natural numbers: a(1) = 1, a(A014580(n)) = (2*a(n))+1, a(A091242(n)) = 2*a(n), where A014580(n) = binary code for n-th irreducible polynomial over GF(2), A091242(n) = binary code for n-th reducible polynomial over GF(2).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A246202 Permutation of natural numbers: a(1) = 1, a(2n) = A091242(a(n)), a(2n+1) = A014580(a(n)), where A091242(n) = binary code for n-th reducible polynomial over GF(2) and A014580(n) = binary code for n-th irreducible polynomial over GF(2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A246158 Odious reducible polynomials over GF(2), coded in binary. (Polynomials with an odd number of nonzero terms that are reducible over GF(2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

A246203 Permutation of natural numbers: a(n) = A246201(A193231(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

Formula

A246201 Permutation of natural numbers: a(1) = 1, a(A014580(n)) = (2a(n))+1, a(A091242(n)) = 2a(n), where A014580(n) = binary code for n-th irreducible polynomial over GF(2), A091242(n) = binary code for n-th reducible polynomial over GF(2).