A235032 -id:A235032 - cp's OEIS frontend

A014580 Binary irreducible polynomials (primes in the ring GF(2)[X]), evaluated at X=2.

2, 3, 7, 11, 13, 19, 25, 31, 37, 41, 47, 55, 59, 61, 67, 73, 87, 91, 97, 103, 109, 115, 117, 131, 137, 143, 145, 157, 167, 171, 185, 191, 193, 203, 211, 213, 229, 239, 241, 247, 253, 283, 285, 299, 301, 313, 319, 333, 351, 355, 357, 361, 369, 375

Offset: 1

David Petry (petry(AT)accessone.com)

nonn

Or, binary irreducible polynomials, interpreted as binary vectors, then written in base 10.
The numbers {a(n)} are a subset of the set {A206074}. - Thomas Ordowski, Feb 21 2014
2^n - 1 is a term if and only if n = 2 or n is a prime and 2 is a primitive root modulo n. - Jianing Song, May 10 2021
For odd k, k is a term if and only if binary_reverse(k) = A145341((k+1)/2) is. - Joerg Arndt and Jianing Song, May 10 2021

			x^4 + x^3 + 1 -> 16+8+1 = 25. Or, x^4 + x^3 + 1 -> 11001 (binary) = 25 (decimal).

A.H.M. Smeets, Table of n, a(n) for n = 1..20000 (first 1377 terms from T. D. Noe)
Index entries for sequences operating on GF(2)[X]-polynomials

Written in binary: A058943.
Number of degree-n irreducible polynomials: A001037, see also A000031.
Multiplication table: A048720.
Characteristic function: A091225. Inverse: A091227. a(n) = A091202(A000040(n)). Almost complement of A091242. Union of A091206 & A091214 and also of A091250 & A091252. First differences: A091223. Apart from a(1) and a(2), a subsequence of A092246 and hence A000069.
Table of irreducible factors of n: A256170.
Irreducible polynomials satisfying particular conditions: A071642, A132447, A132449, A132453, A162570.
Factorization sentinel: A278239.
Sequences analyzing the difference between factorization into GF(2)[X] irreducibles and ordinary prime factorization of the corresponding integer: A234741, A234742, A235032, A235033, A235034, A235035, A235040, A236850, A325386, A325559, A325560, A325563, A325641, A325642, A325643.
Factorization-preserving isomorphisms: A091203, A091204, A235041, A235042.
See A115871 for sequences related to cross-domain congruences.
Functions based on the irreducibles: A305421, A305422.

fQ[n_] := Block[{ply = Plus @@ (Reverse@ IntegerDigits[n, 2] x^Range[0, Floor@ Log2@ n])}, ply == Factor[ply, Modulus -> 2] && n != 2^Floor@ Log2@ n]; fQ[2] = True; Select[ Range@ 378, fQ] (* Robert G. Wilson v, Aug 12 2011 *)
Reap[Do[If[IrreduciblePolynomialQ[IntegerDigits[n, 2] . x^Reverse[Range[0, Floor[Log[2, n]]]], Modulus -> 2], Sow[n]], {n, 2, 1000}]][[2, 1]] (* Jean-François Alcover, Nov 21 2016 *)

is(n)=polisirreducible(Pol(binary(n))*Mod(1,2)) \\ Charles R Greathouse IV, Mar 22 2013

A235035 Numbers n for which A234742(n) = n: numbers n whose binary representation encodes a GF(2)[X]-polynomial such that when its irreducible factors are multiplied together as ordinary integers (with carry-bits), the result is n.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, 19, 22, 24, 25, 26, 28, 31, 32, 37, 38, 41, 44, 47, 48, 50, 52, 55, 56, 59, 61, 62, 64, 67, 73, 74, 76, 82, 87, 88, 91, 94, 96, 97, 100, 103, 104, 109, 110, 111, 112, 115, 117, 118, 122, 123, 124, 128, 131, 134, 137

Offset: 1

Antti Karttunen, Jan 02 2014

nonn

Gives the positions of zeros in A236379, i.e., n such that A234742(n) = n.
An intersection with A235034 gives A235032. Contains A014580 as a subsequence.
Cf. A235036, A235032-A235033, A234742.

A235034 Numbers whose prime divisors, when multiplied together without carry-bits (as encodings of GF(2)[X]-polynomials, with A048720), produce the original number; numbers for which A234741(n) = n.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 22, 23, 24, 26, 28, 29, 30, 31, 32, 34, 37, 38, 40, 41, 43, 44, 46, 47, 48, 51, 52, 53, 56, 58, 59, 60, 61, 62, 64, 67, 68, 71, 73, 74, 76, 79, 80, 82, 83, 85, 86, 88, 89, 92, 94, 95, 96, 97, 101

Offset: 1

Antti Karttunen, Jan 02 2014

nonn

If n is present, then 2n is present also, as shifting binary representation left never produces any carries.

			All primes occur in this sequence as no multiplication -> no need to add any intermediate products -> no carry bits produced.
Composite numbers like 15 are also present, as 15 = 3*5, and 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.

Gives the positions of zeros in A236378, i.e., n such that A234741(n) = n.
Intersection with A235035 gives A235032.
Other subsequences: A000040 (A091206 and also A091209), A045544 (A004729), A093641, A235040 (gives odd composites in this sequence), A235050, A235490.
Cf. A048720, A061858, A234741.

A235033 Numbers which are factored to a different set of primes in Z as to the irreducible polynomials in GF(2)[X].

Original entry on oeis.org

5, 9, 10, 15, 17, 18, 20, 21, 23, 25, 27, 29, 30, 33, 34, 35, 36, 39, 40, 42, 43, 45, 46, 49, 50, 51, 53, 54, 55, 57, 58, 60, 63, 65, 66, 68, 69, 70, 71, 72, 75, 77, 78, 79, 80, 81, 83, 84, 85, 86, 87, 89, 90, 91, 92, 93, 95, 98, 99, 100, 101, 102, 105, 106

Offset: 1

Antti Karttunen, Jan 02 2014

nonn

If a term is included in this sequence, then all its ordinary multiples as well as any "A048720-multiples" are included as well. (Cf. the characteristic function A235046.)

The sequence which gives all such n that A001222(n) differs from A091222(n) is a subsequence of this sequence.

			5 is included in this sequence, because, although it is prime, its binary representation '101' encodes a polynomial x^2 + 1, which is reducible in polynomial ring GF(2)[X] as (x+1)(x+1), i.e., 5 = A048720(3,3).
9 is included in this sequence, as it factors as 3*3 in Z, the corresponding polynomial (bin.repr. '1001'): x^3 + 1 factors as (x+1)(x^2+x+1), i.e., 9 = A048720(3,7), so even although the number of prime/irreducible factors is the same, the factors themselves (i.e., their binary codes) are not exactly the same, thus 9 is included here.
On the other hand, none of 2, 3, 4, 11 and 111 are included in this sequence because they occur in the complement sequence, A235032 (please see examples there).

Gives the positions of nonzeros in A236380, i.e., n such that A234741(n) <> A234742(n).
Characteristic function: A235046.
Complement: A235032. Subsets: A091209, A091214.

A236850 After 0 and 1, numbers n whose binary representation encodes such a polynomial over GF(2) that all its irreducible factors (their binary codes) are primes in N (terms of A091206).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Feb 02 2014

nonn

To determine whether n belongs to this sequence: first find a unique multiset of terms i, j, ..., k (terms not necessarily distinct) from A014580 for which i x j x ... x k = n, where x stands for the carryless multiplication (A048720). If and only if NONE of those i, j, ..., k is a composite (in other words, if all are primes in N, i.e. terms of A091206), then n is a member.
Equally, numbers which can be constructed as p x q x ... x r, where p, q, ..., r are terms of A091206. (Compare to the definition of A236860.)
Also fixed points of A236851(n). Proof: if k is a term of this sequence, the operation described in A236851 reduces to an identity operation. On the other hand, if k is not a term of this sequence, then it contains at least one irreducible GF(2)[X]-factor which is a composite in N, which is thus "broken" by A236851 to two or more separate GF(2)[X]-factors (either irreducible or not), and because the original factor was irreducible, and GF(2)[X] is a unique factorization domain, the new product computed over the new set of factors (with one or more "broken" pieces) cannot be equal to the original k. (Compare this to how primes are "broken" in a similar way in A235027, also A235145.)
Also by similar to above reasoning, positions where A234742(n) = A236837(n).
This is a subsequence of A236841, from which this differs for the first time at n=43, where A236841(43)=43, while from here 43 is missing, and a(43)=44.

			25 is the first term not included, as although it encodes an irreducible polynomial in GF(2)[X]: X^4 + X^3 + 1 (binary code 11001), it is composite in Z, thus not in A091206, but in A091214.
27 is included, as it factors as 5 x 7, and both factors are present in A091206.
37 is included, as it is a member of A091206 (irreducible in both Z and GF(2)[X]).
43 is NOT included because, even although it is a prime in Z, it factors as 3 x 25 in GF(2)[X]. Of these, only 3 is a term of A091206, while 25 belongs to A091214, as it further divides to 5*5.

Antti Karttunen, Table of n, a(n) for n = 1..14166
Index entries for sequences operating on polynomials over GF(2)

Subsequence of A236841.
Subsequence: A235032.
Cf. A236860, A236851, A234741, A234742, A236851.

A235045 Fixed points of permutations A235041/A235042.

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, 135, 137, 146, 148, 152, 157, 159, 164, 167

Offset: 1

Antti Karttunen, Jan 02 2014

nonn

			In the following examples, X stands for the carryless multiplication of GF(2)[X] polynomials (A048720):
3 is a member, because it is in A091206, thus by definition fixed by A235041/A235042.
41 is a member for the same reason.
123 is a member, because 123 = 3*41, thus A235041(123) = A235041(3) X A235041(41) = 3 X 41 = A048720(3,41) = 123. That is, we happen to get the same result back as 3, '11' in binary, and 41, '101001' in binary, can be multiplied together to 123, '1111011' in binary, without producing any carries.
135 is a member, because 135 = 3*3*3*5, thus A235041(135) = A235041(3) X A235041(3) X A235041(3) X A235041(5) = 3 X 3 X 3 X 25 = 15 X 25 = 135.

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

The sequence differs from its subsequence A235032 for the first time at n=54, where a(54)=135, while A235032(54)=137.
A091206 gives the prime terms.
Cf. A235041, A235042.

A236380 Difference between value of n, when remultiplied "upward", from GF(2)[X] to N, and when remultiplied "downward", from N to GF(2)[X]: a(n) = A234742(n) - A234741(n).

Original entry on oeis.org

0, 0, 0, 0, 0, 4, 0, 0, 0, 16, 8, 0, 0, 0, 0, 12, 0, 64, 32, 0, 16, 40, 0, 16, 0, 8, 0, 48, 0, 4, 24, 0, 0, 64, 128, 64, 64, 0, 0, 76, 32, 0, 80, 32, 0, 172, 32, 0, 0, 56, 16, 192, 0, 4, 96, 16, 0, 64, 8, 0, 48, 0, 0, 120, 0, 384, 128, 0, 256, 64, 128, 112, 128, 0, 0, 300, 0, 128, 152, 96, 64, 152, 0, 148, 160, 644, 64

Offset: 0

Antti Karttunen, Jan 24 2014

nonn

All terms are divisible by 4.

a(n) = 0 iff both A236378(n) and A236379(n) are zero, or in other words, iff A234741(n)=n and A234742(n)=n, which means that A235032 gives all such n, that a(n) = 0.

Antti Karttunen, Table of n, a(n) for n = 0..8191

A235032 gives the positions of zeros, A235033 the positions of nonzeros.

Cf. also A234741, A234742, A236378, A236379, A236851, A061858.

a(n) = A234742(n) - A234741(n).

a(n) = A236378(n) + A236379(n).

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.

A235490 Numbers such that none of their prime factors share common 1-bits in the same bit-position and when added (or "ored" or "xored") together, yield a term of A000225 (a binary "repunit").

Original entry on oeis.org

1, 3, 7, 10, 26, 31, 58, 122, 127, 1018, 2042, 8186, 8191, 32762, 131071, 524287, 2097146, 8388602, 33554426, 1073741818, 2147483647, 2305843009213693951, 618970019642690137449562111, 39614081257132168796771975162, 162259276829213363391578010288127, 166153499473114484112975882535043066

Offset: 1

Antti Karttunen, Jan 22 2014

a(1) = 1 is included on the grounds that it has no prime factors, thus A001414(1)=0, and 0 is one of the terms of A000225, marking the "repunit of length zero".

After 1, the sequence is a union of A000668 (Mersenne primes) and semiprimes of the form 2*A050415. The terms were constructed from the data given in those two entries.

			7 is included, because it is a prime, and repunit in base-2: '111'.
10 is included, as 10=2*5, and when we add 2 ('10' in binary) and 5 ('101' in binary), we also get 7 ('111' in binary), without producing any carries.

Subsequence of A235050.
Cf. A000225, A000668, A050415, A001414, A072593, A178910, A227843.
Cf. also A235488, A230492, A235032, A050376.

cp's OEIS Frontend

A014580 Binary irreducible polynomials (primes in the ring GF(2)[X]), evaluated at X=2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A235035 Numbers n for which A234742(n) = n: numbers n whose binary representation encodes a GF(2)[X]-polynomial such that when its irreducible factors are multiplied together as ordinary integers (with carry-bits), the result is n.

Views

Author

Keywords

Links

Crossrefs

A235034 Numbers whose prime divisors, when multiplied together without carry-bits (as encodings of GF(2)[X]-polynomials, with A048720), produce the original number; numbers for which A234741(n) = n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A235033 Numbers which are factored to a different set of primes in Z as to the irreducible polynomials in GF(2)[X].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A236850 After 0 and 1, numbers n whose binary representation encodes such a polynomial over GF(2) that all its irreducible factors (their binary codes) are primes in N (terms of A091206).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A235045 Fixed points of permutations A235041/A235042.

Views

Author

Keywords

Examples

Links

Crossrefs

A236380 Difference between value of n, when remultiplied "upward", from GF(2)[X] to N, and when remultiplied "downward", from N to GF(2)[X]: a(n) = A234742(n) - A234741(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

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

A235490 Numbers such that none of their prime factors share common 1-bits in the same bit-position and when added (or "ored" or "xored") together, yield a term of A000225 (a binary "repunit").

Views

Author

Keywords

Comments

Examples

Crossrefs