A236860 -id:A236860 - cp's OEIS frontend

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).

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.

A236842 Numbers that occur as results of remultiplication (GF(2)[X] -> N) of some number; A234742 sorted and duplicates removed.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 18, 19, 21, 22, 24, 25, 26, 27, 28, 31, 32, 33, 36, 37, 38, 39, 41, 42, 44, 47, 48, 49, 50, 52, 54, 55, 56, 57, 59, 61, 62, 63, 64, 66, 67, 72, 73, 74, 75, 76, 77, 78, 81, 82, 84, 87, 88, 91, 93, 94, 96, 97, 98, 99, 100, 103

Offset: 1

Antti Karttunen, Jan 31 2014

nonn

This sequence gives the range of A234742.
After 0 and 1 these are numbers n that have such a multiset of prime divisors p, q, ..., w (p * q * ... * w = n, with p, q, ..., w not necessarily distinct) that it can be arranged so that in at least one subset of divisors of n: (p, q, w), (pq, w), (pw, q), (p, qw), (pqw), ..., all divisors (for example, in the second case: pq and w) encode by their binary representations irreducible factors of polynomial ring over GF(2) (i.e., all occur in A014580) and their (ordinary) product is n.
Above condition implies that none of the terms of A091209 occur here.

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

Complement: A236844. A236860 is a subsequence.
Positions of nonzero terms in A236853.
Cf. A234742, A236841.

Use the characteristic function A236862(n) to determine whether n is a term of this sequence or not.
Specifically:
All numbers encoding an irreducible polynomial in GF(2)[X] (A014580) occur in this sequence. This means that a prime is in this sequence if and only if it is in A091206.
On the other hand, a composite integer n is in this sequence if and only if it is either in A014580 or it has such a proper factor k (1

A236848 Numbers that have at least one prime divisor encoding a reducible polynomial in ring GF(2)[X]; multiples of terms of A091209.

Original entry on oeis.org

5, 10, 15, 17, 20, 23, 25, 29, 30, 34, 35, 40, 43, 45, 46, 50, 51, 53, 55, 58, 60, 65, 68, 69, 70, 71, 75, 79, 80, 83, 85, 86, 87, 89, 90, 92, 95, 100, 101, 102, 105, 106, 107, 110, 113, 115, 116, 119, 120, 125, 127, 129, 130, 135, 136, 138, 139, 140, 142, 145, 149, 150

Offset: 1

Antti Karttunen, Jan 31 2014

nonn

Numbers that are divisible by at least one prime whose binary representation encodes a polynomial which is reducible in polynomial ring GF(2)[X].

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

Disjoint union of A236844 and A236849.
Complement: A236860.
Cf. A091209, A236838.

A236849 Numbers that occur as results of remultiplication (GF(2)[X] -> N) of some number and have at least one prime divisor encoding a reducible polynomial in ring GF(2)[X].

Original entry on oeis.org

25, 50, 55, 75, 87, 100, 110, 115, 145, 150, 165, 174, 175, 185, 200, 203, 213, 220, 225, 230, 253, 261, 275, 285, 290, 299, 300, 301, 319, 325, 330, 345, 348, 350, 355, 357, 370, 375, 385, 391, 395, 400, 406, 415, 425, 426, 435, 440, 445, 450, 460, 475, 477, 495, 505, 506, 515, 522, 525, 529, 535, 545, 550, 555

Offset: 1

Antti Karttunen, Jan 31 2014

nonn

Terms of A236842 (A234742) that are divisible by at least one of the primes in A091209.

a(4)=75, is the first term here which does not occur in A236834. On the other hand, A236834(5)=91 is the first of its terms that does not occur here.

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

Setwise difference A236848 \ A236844, and also A236842 \ A236860.

Cf. A091209, A234742, A236842, A236848, A236834.

A236852 Remultiply n first "downward", from N to GF(2)[X], and then remultiply that result back "upward", from GF(2)[X] to N: a(n) = A234742(A234741(n)).

Original entry on oeis.org

0, 1, 2, 3, 4, 9, 6, 7, 8, 9, 18, 11, 12, 13, 14, 27, 16, 81, 18, 19, 36, 21, 22, 39, 24, 81, 26, 27, 28, 33, 54, 31, 32, 33, 162, 63, 36, 37, 38, 39, 72, 41, 42, 75, 44, 81, 78, 47, 48, 49, 162, 243, 52, 57, 54, 99, 56, 57, 66, 59, 108, 61, 62, 63, 64, 117, 66, 67, 324

Offset: 0

Antti Karttunen, Feb 02 2014

This sequence appears to be completely multiplicative with a(p) = A234742(p) although neither A234741 or A234742 are even multiplicative. Terms tested up to n = 10^7. - Andrew Howroyd, Aug 01 2018

Yes, this is true. Consider for example n = p*q*r*r, where p, q, r are primes in N. Then A234741(n) = p1 x q1 x q2 x q3 x r1 x r2 x r1 x r2, where p1, q1, r1, ..., are the irreducible factors of p, q, r when factored over GF(2), and x stands for multiplication in ring GF(2)[X] (A048720). [Note that these irreducible factors are not necessarily primes in N, except p1 (= p), which must be a term of A091206. Also, A234741(p) = p for any prime p.] Next, a(n) = A234742(p1 x q1 x q2 x q3 x r1 x r2 x r1 x r2) = p1 * q1 * q2 * q3 * r1 * r2 * r1 * r2, which can be obtained also as a(p)*a(q)*a(r)*a(r), thus proving the multiplicativity. - Antti Karttunen, Aug 02 2018

			From _Antti Karttunen_, Aug 02 2018: (Start)
For n = 3, we have A234741(3) = 3 = 11 in binary, which encodes a (0,1)-polynomial x+1, which is irreducible over GF(2) thus A234742(3) = 3 and  a(3) = 3.
For n = 5, we have A234741(5) = 5 = 101 in binary, which encodes a (0,1)-polynomial x^2 + 1, which factorizes as (x+1)(x+1) when factored over GF(2), that is 5 = A048720(3,3), thus it follows that A234742(5) = 3*3 = 9, and a(5) = 9.
For n = 9 = 3*3, we have A234741(9) = A048720(3,3) = 5, and A234742(5) = 9 as shown above. Also by multiplicativity, we have a(3*3) = a(3)*a(3) = 3*3 = 9.
(End)

Antti Karttunen, Table of n, a(n) for n = 0..8192
Index entries for sequences related to polynomials in ring GF(2)[X]

Fixed points: A236860.

Cf. A048720, A234741, A234742, A236851, A236836-A236837, A236846-A236847.

(define (A236852 n) (A234742 (A234741 n)))

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

Keyword mult added after Andrew Howroyd's observation. - Antti Karttunen, Aug 02 2018

Showing 1-5 of 5 results.

cp's OEIS Frontend

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

A236842 Numbers that occur as results of remultiplication (GF(2)[X] -> N) of some number; A234742 sorted and duplicates removed.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A236848 Numbers that have at least one prime divisor encoding a reducible polynomial in ring GF(2)[X]; multiples of terms of A091209.

Views

Author

Keywords

Comments

Links

Crossrefs

A236849 Numbers that occur as results of remultiplication (GF(2)[X] -> N) of some number and have at least one prime divisor encoding a reducible polynomial in ring GF(2)[X].

Views

Author

Keywords

Comments

Links

Crossrefs

A236852 Remultiply n first "downward", from N to GF(2)[X], and then remultiply that result back "upward", from GF(2)[X] to N: a(n) = A234742(A234741(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Scheme

Formula

Extensions