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

%I A236850 #26 Feb 10 2025 03:12:34
%S A236850 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,
%T A236850 27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,44,45,46,47,48,49,51,
%U A236850 52,53,54,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71
%N 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).
%C A236850 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.
%C A236850 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.)
%C A236850 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.)
%C A236850 Also by similar to above reasoning, positions where A234742(n) = A236837(n).
%C A236850 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.
%H A236850 Antti Karttunen, <a href="/A236850/b236850.txt">Table of n, a(n) for n = 1..14166</a>
%H A236850 <a href="/index/Ge#GF2X">Index entries for sequences operating on polynomials over GF(2)</a>
%e A236850 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.
%e A236850 27 is included, as it factors as 5 x 7, and both factors are present in A091206.
%e A236850 37 is included, as it is a member of A091206 (irreducible in both Z and GF(2)[X]).
%e A236850 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.
%o A236850 (Scheme, with _Antti Karttunen_'s IntSeq-library, three different variants)
%o A236850 (define A236850 (MATCHING-POS 1 0 (lambda (n) (or (zero? n) (every (lambda (p) (= 1 (A010051 p) (A091225 p))) (GF2Xfactor n))))))
%o A236850 (define A236850v2 (FIXED-POINTS 1 0 A236851))
%o A236850 (define A236850v3 (ZERO-POS 1 0  (lambda (n) (- (A234742 n) (A236837 n)))))
%Y A236850 Subsequence of A236841.
%Y A236850 Subsequence: A235032.
%Y A236850 Cf. A236860, A236851, A234741, A234742, A236851.
%K A236850 nonn
%O A236850 1,3
%A A236850 _Antti Karttunen_, Feb 02 2014