login
a(n) is the base-2 carryless product of the prime factors of n; Encoding of the product of the polynomials over GF(2) represented by the prime factors of n (with multiplicity).
32

%I #35 May 11 2019 01:44:19

%S 1,2,3,4,5,6,7,8,5,10,11,12,13,14,15,16,17,10,19,20,9,22,23,24,17,26,

%T 15,28,29,30,31,32,29,34,27,20,37,38,23,40,41,18,43,44,17,46,47,48,21,

%U 34,51,52,53,30,39,56,53,58,59,60,61,62,27,64,57,58,67

%N a(n) is the base-2 carryless product of the prime factors of n; Encoding of the product of the polynomials over GF(2) represented by the prime factors of n (with multiplicity).

%C "Encoding" means the number whose binary representation is given by the coefficients of the polynomial, e.g., 13=1101[2] encodes X^3+X^2+1. The product is the usual multiplication of polynomials in GF(2)[X] (or binary multiplication without carry-bits, cf. A048720).

%C a(n) <= n. [As all terms of the table A061858 are nonnegative]

%H Antti Karttunen, <a href="/A234741/b234741.txt">Table of n, a(n) for n = 1..16384</a>

%H Antti Karttunen, <a href="/A234741/a234741.txt">Data supplement: n, a(n) computed for n = 1..65537</a>

%H <a href="/index/Ge#GF2X">Index entries for sequences related to polynomials in ring GF(2)[X]</a>

%F a(0)=0, a(1)=1, and for n > 1, a(n) = A048720(A020639(n),a(n/A020639(n))). [A048720 used as a bivariate function]

%F Equally, for n with its unique prime factorization n = p_1 * ... * p_k, with the p_i not necessarily distinct primes, a(n) = p_1 x ... x p_k, where x stands for carryless multiplication defined in A048720, which is isomorphic to multiplication in GF(2)[X].

%F a(2n) = 2*a(n).

%F More generally, if A061858(x,y) = 0, then a(x*y) = a(x)*a(y).

%F a(A235034(n)) = A235034(n).

%F A236378(n) = n - a(n).

%e a(9) = a(3*3) = 5, as when we multiply 3 ('11' in binary) with itself, and discard the carry-bits, using XOR (A003987) instead of normal addition, we get:

%e 11

%e 110

%e -----

%e 101

%e that is, 5, as '101' is its binary representation. In other words, a(9) = a(3*3) = A048720(3,3) = 5.

%e Alternatively, 9 = 3*3, and 3=11[2] encodes the polynomial X+1, and (X+1)*(X+1) = X^2+1 in GF(2)[X], which is encoded as 101[2] = 5, therefore a(9) = 5. - _M. F. Hasler_, Feb 16 2014

%o (Scheme, with _Antti Karttunen_'s IntSeq-library)

%o (definec (A234741 n) (if (< n 2) n (A048720bi (A020639 n) (A234741 (/ n (A020639 n)))))) ;; A048720bi is a bivariate-function for A048720.

%o (PARI) A234741(n)={n=factor(n);n[,1]=apply(t->Pol(binary(t)),n[,1]);sum(i=1,#n=Vec(factorback(n))%2,n[i]<<(#n-i))} \\ _M. F. Hasler_, Feb 18 2014

%Y A235034 gives the k for which a(k)=k.

%Y A236833(n) gives the number of times n occurs in this sequence.

%Y A236841 gives the same sequence sorted and duplicates removed, A236834 gives the numbers that do not occur here, A236835 gives numbers that occur more than once.

%Y A325562(n) gives the number of iterations needed before one of the fixed points (terms of A235034) is reached.

%Y Cf. also A048720, A061858, A234742, A236378, A091202/A091203, A235041/A235042, A266195, A325561, A325562.

%K nonn

%O 1,2

%A _Antti Karttunen_, Jan 22 2014

%E Term a(0) = 0 removed and a new primary definition added by _Antti Karttunen_, May 10 2019