A278233 Filter-sequence for GF(2)[X]-factorization: sequence that gives the least natural number with the same prime signature that (0, 1)-polynomial encoded in the binary expansion of n has when it is factored over GF(2).

1, 2, 2, 4, 4, 6, 2, 8, 6, 12, 2, 12, 2, 6, 8, 16, 16, 30, 2, 36, 4, 6, 6, 24, 2, 6, 12, 12, 6, 24, 2, 32, 6, 48, 6, 60, 2, 6, 12, 72, 2, 12, 6, 12, 24, 30, 2, 48, 6, 6, 32, 12, 6, 60, 2, 24, 12, 30, 2, 72, 2, 6, 12, 64, 36, 30, 2, 144, 4, 30, 6, 120, 2, 6, 24, 12, 6, 60, 6, 144, 4, 6, 30, 36, 64, 30, 2, 24, 6, 120, 2, 60, 6, 6, 12, 96, 2, 30, 12, 12, 30, 96, 2

Offset

1,2

Comments

a(n) = the least number with the same prime signature as A091203(n).

This sequence works as an A046523-analog in the polynomial ring GF(2)[X] and can be used as a filter which matches with (and thus detects) any sequence in the database where a(n) depends only on the exponents of irreducible factors when the polynomial corresponding to n (via base-2 encoding) is factored over GF(2). These sequences are listed in the Crossrefs section, "Sequences that partition N into ...".

Matching in this context means that the sequence a matches with the sequence b iff for all i, j: a(i) = a(j) => b(i) = b(j). In other words, iff the sequence b partitions the natural numbers to the same or coarser equivalence classes (as/than the sequence a) by the distinct values it obtains.

Links

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

Index entries for sequences computed from exponents in factorization of n

Index entries for sequences operating on polynomials in ring GF(2)[X]

Formula

a(n) = A046523(A091203(n)) = A046523(A091205(n)) = A046523(A235042(n)). [Because of the "sorting" essentially performed by A046523, any map from GF(2)[X] to Z can be used, as long as it is fully (cross-)multiplicative and preserves also the exponents intact.]

Other identities. For all n >= 1:

a(A014580(n)) = 2.

a(n) = a(A057889(n)) = a(A193231(n)).

a(A000695(n)) = A278238(n).

a(A277699(n)) = A278239(n).

Example

3 is "11" in binary, encodes polynomial x + 1, and 7 is "111" in binary, encodes polynomial x^2 + x + 1, both which are irreducible over GF(2). We can multiply their codes with carryless multiplication A048720 as A048720(3,7) = 9, A048720(9,3) = 27, A048720(9,7) = 63. Now a(27) = a(63) because the exponents occurring in both codes 27 and 63 are one 1 and two 2's, and their order is not significant when computing prime signature. Moreover a(27) = a(63) = 12 because that is the least number with a prime signature (1,2) in the more familiar domain of natural numbers.
a(25) = 2, because 25 is "11001" in binary, encoding polynomial x^4 + x^3 + 1, which is irreducible in the ring GF(2)[X], i.e., 25 is in A014580, whose initial term is 2.

Prog

(PARI) A278233(n) = { my(p=0, f=vecsort((factor(Pol(binary(n))*Mod(1, 2))[, 2]), , 4)); prod(i=1, #f, (p=nextprime(p+1))^f[i]); }; \\ Antti Karttunen, Jun 10 2018
(Scheme) (define (A278233 n) (A046523 (A091203 n)))

Crossrefs

Cf. A014580 (gives the positions of 2's), A048720, A057889, A091203, A091205, A193231, A235042, A278231, A278238, A278239.

Similar filtering sequences: A046523, A278222, A278226, A278236, A278243.

Sequences that partition N into same or coarser equivalence classes: A091220, A091221, A091222, A106493, A106494.

Cf. also A304529, A304751, A305788 (rgs-transform), A305789.

Sequence in context: A097264 A339810 A324104 * A354753 A377225 A354755

Adjacent sequences: A278230 A278231 A278232 * A278234 A278235 A278236

Keyword

nonn

Author

Antti Karttunen, Nov 16 2016

Status

approved