|
%I #40 Jun 10 2018 21:14:13
%S 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,
%T 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,
%U 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
%N 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).
%C a(n) = the least number with the same prime signature as A091203(n).
%C 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 ...".
%C 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.
%H Antti Karttunen, <a href="/A278233/b278233.txt">Table of n, a(n) for n = 1..65536</a>
%H <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>
%H <a href="/index/Ge#GF2X">Index entries for sequences operating on polynomials in ring GF(2)[X]</a>
%F 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.]
%F Other identities. For all n >= 1:
%F a(A014580(n)) = 2.
%F a(n) = a(A057889(n)) = a(A193231(n)).
%F a(A000695(n)) = A278238(n).
%F a(A277699(n)) = A278239(n).
%e 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.
%e 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.
%o (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
%o (Scheme) (define (A278233 n) (A046523 (A091203 n)))
%Y Cf. A014580 (gives the positions of 2's), A048720, A057889, A091203, A091205, A193231, A235042, A278231, A278238, A278239.
%Y Similar filtering sequences: A046523, A278222, A278226, A278236, A278243.
%Y Sequences that partition N into same or coarser equivalence classes: A091220, A091221, A091222, A106493, A106494.
%Y Cf. also A304529, A304751, A305788 (rgs-transform), A305789.
%K nonn
%O 1,2
%A _Antti Karttunen_, Nov 16 2016
|
