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,3

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.

Links

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

Index entries for sequences operating on polynomials over GF(2)

Example

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

Prog

(Scheme, with Antti Karttunen's IntSeq-library, three different variants)
(define A236850 (MATCHING-POS 1 0 (lambda (n) (or (zero? n) (every (lambda (p) (= 1 (A010051 p) (A091225 p))) (GF2Xfactor n))))))
(define A236850v2 (FIXED-POINTS 1 0 A236851))
(define A236850v3 (ZERO-POS 1 0  (lambda (n) (- (A234742 n) (A236837 n)))))

Crossrefs

Subsequence of A236841.

Subsequence: A235032.

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

Sequence in context: A296867 A228144 A236841 * A263028 A044921 A260423

Adjacent sequences: A236847 A236848 A236849 * A236851 A236852 A236853

Keyword

nonn

Author

Antti Karttunen, Feb 02 2014

Status

approved