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

Author

Antti Karttunen, Feb 02 2014

Keywords

• nonn

Comments

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.

Examples

			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.
		

Links

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

Crossrefs

Subsequence of A236841.

Subsequence: A235032.

Cf. A236860, A236851, A234741, A234742, A236851.