A235045 -id:A235045 - cp's OEIS frontend

A091206 Primes whose binary representation encodes a polynomial irreducible over GF(2).

2, 3, 7, 11, 13, 19, 31, 37, 41, 47, 59, 61, 67, 73, 97, 103, 109, 131, 137, 157, 167, 191, 193, 211, 229, 239, 241, 283, 313, 379, 397, 419, 433, 463, 487, 499, 557, 563, 587, 601, 607, 613, 617, 631, 647, 661, 677, 701, 719, 757, 761, 769, 787, 827, 859

Offset: 1

Antti Karttunen, Jan 03 2004

nonn

"Encoded in binary representation" 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 each coefficient a(k) = 0 or 1).

Subsequence with Hamming weight nonprime starts 2, 1019, 1279, 1531, 1663, 1759, 1783, 1789, 2011, 2027, 2543, 2551, ... [Joerg Arndt, Nov 01 2013]. These are now given by A255569. - Antti Karttunen, May 14 2015

Antti Karttunen, Table of n, a(n) for n = 1..10226; all terms up to 1048357, binary length 20
A. Karttunen, Scheme-program for computing this sequence.
Index entries for sequences related to binary encoded polynomials over GF(2)

Intersection of A014580 and A000040.
Apart from a(2) = 3 a subsequence of A027697. The numbers in A027697 but not here are listed in A238186.
Also subsequence of A235045 (its primes. Cf. also A235041-A235042).
Cf. A091209 (Primes whose binary expansion encodes a polynomial reducible over GF(2)), A091212 (Composite, and reducible over GF(2)), A091214 (Composite, but irreducible over GF(2)), A257688 (either 1, prime or irreducible over GF(2)).
Subsequence: A255569.

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

is(n)=polisirreducible( Mod(1,2) * Pol(digits(n,2)) );
forprime(n=2,10^3,if (is(n), print1(n,", ")));
\\ Joerg Arndt, Nov 01 2013

a(n) = A000040(A091207(n)) = A014580(A091208(n)).

A235042 Factorization-preserving bijection from GF(2)[X]-polynomials to nonnegative integers, version which fixes the elements that are irreducible in both semirings.

Original entry on oeis.org

0, 1, 2, 3, 4, 9, 6, 7, 8, 21, 18, 11, 12, 13, 14, 27, 16, 81, 42, 19, 36, 49, 22, 39, 24, 5, 26, 63, 28, 33, 54, 31, 32, 93, 162, 91, 84, 37, 38, 99, 72, 41, 98, 15, 44, 189, 78, 47, 48, 77, 10, 243, 52, 57, 126, 17, 56, 117, 66, 59, 108, 61, 62, 147, 64, 441

Offset: 0

Antti Karttunen, Jan 02 2014

nonn

Like A091203 this is a factorization-preserving isomorphism from GF(2)[X]-polynomials to integers. The former are encoded in the binary representation of n like this: n=11, '1011' in binary, stands for polynomial x^3+x+1, n=25, '11001' in binary, stands for polynomial x^4+x^3+1. However, this version does not map the irreducible GF(2)[X] polynomials (A014580) straight to the primes (A000040), but instead fixes the intersection of those two sets (A091206), and maps the elements in their set-wise difference A014580 \ A000040 (= A091214) in numerical order to the set-wise difference A000040 \ A014580 (= A091209).
The composite values are defined by the multiplicativity. E.g., we have a(A048724(n)) = 3*a(n) and a(A001317(n)) = A000244(n) = 3^n for all n.
This map satisfies many of the same identities as A091203, e.g., we have A091219(n) = A008683(a(n)), A091220(n) = A000005(a(n)), A091221(n) = A001221(a(n)), A091222(n) = A001222(a(n)), A091225(n) = A010051(a(n)) and A091247(n) = A066247(a(n)) for all n >= 1.

			Here (t X u) = A048720(t,u):
a(2)=2, a(3)=3 and a(7)=7, as 2, 3 and 7 are all in A091206.
a(4) = a(2 X 2) = a(2)*a(2) = 2*2 = 4.
a(5) = a(3 X 3) = a(3)*a(3) = 3*3 = 9.
a(9) = a(3 X 7) = a(3)*a(7) = 3*7 = 21.
a(10) = a(2 X 3 X 3) = a(2)*a(3)*a(3) = 2*3*3 = 18.
a(15) = a(3 X 3 X 3) = a(3)^3 = 3^3 = 27.
a(17) = a(3 X 3 X 3 X 3) = a(3)^4 = 3^4 = 81.
a(21) = a(7 X 7) = a(7)*a(7) = 7*7 = 49.
a(25) = 5, as 25 is the first term of A091214 and 5 is the first term of A091209.
a(50) = a(2 X 25) = a(2)*a(25) = 2*5 = 10.

Inverse: A235041. Fixed points: A235045.
Cf. A010051, A004247, A091225, A091209, A235044.
Similar cross-multiplicative permutations: A091203, A091205, A106443, A106445, A106447.

a(0)=0, a(1)=1, a(p) = p for those irreducible GF(2)[X]-polynomials whose binary encoding is a prime (i.e., p is in A091206), and for the rest of irreducible GF(2)[X]-polynomials (those which are encoded by a composite natural number, i.e., q is in A091214), a(q) = A091209(A235044(q)), and for reducible polynomials, a(i X j X k X ...) = a(i) * a(j) * a(k) * ..., where each i, j, k, ... is in A014580, X stands for carryless multiplication of GF(2)[X] polynomials (A048720) and * for the ordinary multiplication of integers (A004247).

A235041 Factorization-preserving bijection from nonnegative integers to GF(2)[X]-polynomials, version which fixes the elements that are irreducible in both semirings.

Original entry on oeis.org

0, 1, 2, 3, 4, 25, 6, 7, 8, 5, 50, 11, 12, 13, 14, 43, 16, 55, 10, 19, 100, 9, 22, 87, 24, 321, 26, 15, 28, 91, 86, 31, 32, 29, 110, 79, 20, 37, 38, 23, 200, 41, 18, 115, 44, 125, 174, 47, 48, 21, 642, 89, 52, 117, 30, 227, 56, 53, 182, 59, 172, 61, 62, 27, 64

Offset: 0

Antti Karttunen, Jan 02 2014

nonn

Like A091202 this is a factorization-preserving isomorphism from integers to GF(2)[X]-polynomials. The latter are encoded in the binary representation of n like this: n=11, '1011' in binary, stands for polynomial x^3+x+1, n=25, '11001' in binary, stands for polynomial x^4+x^3+1. However, this version does not map the primes (A000040) straight to the irreducible GF(2)[X] polynomials (A014580), but instead fixes the intersection of those two sets (A091206), and maps the elements in their set-wise difference A000040 \ A014580 (= A091209) in numerical order to the set-wise difference A014580 \ A000040 (= A091214).
The composite values are defined by the multiplicativity. E.g., we have a(3n) = A048724(a(n)) and a(3^n) = A001317(n) for all n.
This map satisfies many of the same identities as A091202, e.g., we have A000005(n) = A091220(a(n)), A001221(n) = A091221(a(n)), A001222(n) = A091222(a(n)) and A008683(n) = A091219(a(n)) for all n >= 1.

			Here (t X u) = A048720(t,u):
a(2)=2, a(3)=3 and a(7)=7, as 2, 3 and 7 are all in A091206.
a(4) = a(2*2) = a(2) X a(2) = 2 X 2 = 4.
a(9) = a(3*3) = a(3) X a(3) = 3 X 3 = 5.
a(5) = 25, as 5 is the first term of A091209 and 25 is the first term of A091214.
a(10) = a(2*5) = a(2) X a(5) = 2 X 25 = 50.
Similarly, a(17) = 55, as 17 is the second term of A091209 and 55 is the second term of A091214.
a(21) = a(3*7) = a(3) X a(7) = 3 X 7 = 9.

Inverse: A235042. Fixed points: A235045.
Cf. A010051, A048720, A091225, A091214, A235043, A048724, A115857, A115872.
Similar cross-multiplicative permutations: A091202, A091204, A106442, A106444, A106446.

a(0)=0, a(1)=1, a(p) = p for those primes p whose binary representations encode also irreducible GF(2)[X]-polynomials (i.e., p is in A091206), and for the rest of the primes q (those whose binary representation encode composite GF(2)[X]-polynomials, i.e., q is in A091209), a(q) = A091214(A235043(q)), and for composite natural numbers, a(p * q * r * ...) = a(p) X a(q) X a(r) X ..., where p, q, r, ... are primes and X stands for the carryless multiplication (A048720) of GF(2)[X] polynomials encoded as explained in the Comments section.

A235032 Numbers which are factored to the same set of primes in Z as to the binary codes of irreducible polynomials in GF(2)[X].

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, 19, 22, 24, 26, 28, 31, 32, 37, 38, 41, 44, 47, 48, 52, 56, 59, 61, 62, 64, 67, 73, 74, 76, 82, 88, 94, 96, 97, 103, 104, 109, 111, 112, 118, 122, 123, 124, 128, 131, 134, 137, 146, 148, 152, 157, 164, 167, 176, 188

Offset: 1

Antti Karttunen, Jan 02 2014

nonn

This is a subsequence of the sequence which gives all such n that A001222(n) = A091222(n).

			2, 3 and 11 are included in this sequence, because they occur in A091206. That is, they are all primes, and encode irreducible polynomials in ring GF(2)[X] via their binary representations: For 2, '10' in binary, corresponds to polynomial x, and for 3, '11' in binary, corresponds to polynomial x+1, and for 11, '1011' in binary, corresponds to polynomial x^3+x+1, which are all irreducible in GF(2)[X].
4 is included in this sequence, because it factors as 2*2, but also because the corresponding GF(2)[X] polynomial x^2 factors as x*x (with the polynomial x encoded by the number 2).
5 is NOT included in this sequence, because, although it is prime, the corresponding polynomial (5 in binary is '101'): x^2 + 1 is not irreducible in GF(2)[X], but factors as (x+1)(x+1), i.e., we have 5 = A048720(3,3).
111 is included, as it is a product of two primes, 3*37, and these primes encode via their binary representations, '11' and '100101', two polynomials irreducible in GF(2)[X]: x+1 and x^5 + x^2 + 1, whose product, x^6 + x^5 + x^3 + x^2 + x + 1, is encoded by 111's binary representation, '1101111'.

Complement: A235033. Intersection of A235034 & A235035. Union of A091206 & A235036. Subsequence of A235045.
A235036 and A235039 give composite and odd composite (after 1) terms occurring in this sequence.
Gives the positions of zeros in A236380, i.e. such n that A234741(n) = A234742(n).
Cf. also A048720.

A235040 After 1, composite odd numbers, whose prime divisors, when multiplied together without carry-bits (as codes for GF(2)[X]-polynomials, with A048720), yield the same number back.

Original entry on oeis.org

1, 15, 51, 85, 95, 111, 119, 123, 187, 219, 221, 255, 335, 365, 411, 447, 485, 511, 629, 655, 685, 697, 771, 831, 879, 959, 965, 1011, 1139, 1241, 1285, 1405, 1535, 1563, 1649, 1731, 1779, 1799, 1923, 1983, 2005, 2019, 2031, 2045, 2227, 2605, 2735, 2815, 2827

Offset: 0

Antti Karttunen, Jan 02 2014

nonn

Note: Start indexing from n=1 if you want just composite numbers. a(0)=1 is the only nonprime, noncomposite in this list.
The first term with three prime divisors is a(11) = 255 = 3*5*17.
The next terms with three prime divisors are
  255, 3855, 13107, 21845, 24415, 28527, 30583, 31215, 31611, 31695, 32691, 48059, 56283, 56797, 61935, 65365, 87805, 98005, ...
Of these 24415 (= 5*19*257) is the first one with at least one prime factor that is not a Fermat prime (A019434).
The first term with four prime divisors is a(427) = 65535 = 3*5*17*257.
The first terms which are not multiples of any Fermat prime are: 511, 959, 3647, 4039, 4847, 5371, 7141, 7231, 7679, 7913, 8071, 9179, 12179, ... (511 = 7*73, 959 = 7*137, ...)

			15 = 3*5. When these factors (with binary representations '11' and '101') are multiplied as:
   101
  1010
  ----
  1111 = 15
we see that the intermediate products 1*5 and 2*5 can be added together without producing any carry-bits (as they have no 1-bits in the same columns/bit-positions), so A048720(3,5) = 3*5 and thus 15 is included in this sequence.

Odd nonprimes in A235034. A235039 is a subsequence.
The composite terms in A045544 (A004729) all occur also here.
Cf. also A019434, A048720, A235045, A235050, A115857, A115872.

A235036 Nonprime numbers which are factored to the same set of primes in Z as to the irreducible polynomials in GF(2)[X].

Original entry on oeis.org

1, 4, 6, 8, 12, 14, 16, 22, 24, 26, 28, 32, 38, 44, 48, 52, 56, 62, 64, 74, 76, 82, 88, 94, 96, 104, 111, 112, 118, 122, 123, 124, 128, 134, 146, 148, 152, 164, 176, 188, 192, 194, 206, 208, 218, 219, 222, 224, 236, 244, 246, 248, 256, 262, 268, 274, 292, 296, 304

Offset: 0

Antti Karttunen, Jan 02 2014

nonn

Note: Start indexing from n=1 if you want just composite numbers. a(0)=1 is the only nonprime, noncomposite in this list.

These are nonprime (and nonzero) numbers in A235032. Also a subsequence of A235045 and (apart from 1) of A091212. A235039 gives the odd terms.

A235039 Odd numbers which are factored to the same set of primes in Z as to the irreducible polynomials in GF(2)[X]; odd terms of A235036.

Original entry on oeis.org

1, 111, 123, 219, 411, 511, 959, 1983, 2031, 3099, 3459, 3579, 4847, 5371, 6159, 7023, 7131, 7141, 7231, 7899, 7913, 8071, 8079, 9179, 12387, 12783, 13289, 15843, 26223, 27771, 28453, 28903, 31529, 31539, 39007, 45419, 49251, 49659, 51087, 53677, 56137, 57219, 61923

Offset: 0

Antti Karttunen, Jan 02 2014

nonn

These are odd nonprime numbers in A235032. After a(0)=1, the odd composite numbers in A235032.

The terms a(1) - a(42) are all semiprimes. Presumably terms with a larger number of prime factors also exist.

			111 = 3*37. When these two prime factors (both terms of A091206), with binary representations '11' and '100101', are multiplied as:
   100101
  1001010
  -------
  1101111 = 111 in decimal
we see that the intermediate products 1*37 and 2*37 can be added together without producing any carry-bits (as they have no 1-bits in the same columns/bit-positions), so A048720(3,37) = 3*37 and thus 111 is included in this sequence.
Note that unlike in A235040, 15 = 3*5 is not included in this sequence, because its prime factor 5 is not in A091206, but instead decomposes further as A048720(3,3).

A subsequence of A235032, A235036, A235040 and A235045.

cp's OEIS Frontend

A091206 Primes whose binary representation encodes a polynomial irreducible over GF(2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A235042 Factorization-preserving bijection from GF(2)[X]-polynomials to nonnegative integers, version which fixes the elements that are irreducible in both semirings.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A235041 Factorization-preserving bijection from nonnegative integers to GF(2)[X]-polynomials, version which fixes the elements that are irreducible in both semirings.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A235032 Numbers which are factored to the same set of primes in Z as to the binary codes of irreducible polynomials in GF(2)[X].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A235040 After 1, composite odd numbers, whose prime divisors, when multiplied together without carry-bits (as codes for GF(2)[X]-polynomials, with A048720), yield the same number back.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A235036 Nonprime numbers which are factored to the same set of primes in Z as to the irreducible polynomials in GF(2)[X].

Views

Author

Keywords

Comments

Links

Crossrefs

A235039 Odd numbers which are factored to the same set of primes in Z as to the irreducible polynomials in GF(2)[X]; odd terms of A235036.

Views

Author

Keywords

Comments

Examples

Crossrefs