login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Remultiply n first "downward", from N to GF(2)[X], and then remultiply that result back "upward", from GF(2)[X] to N: a(n) = A234742(A234741(n)).
4

%I #20 Aug 02 2018 08:00:10

%S 0,1,2,3,4,9,6,7,8,9,18,11,12,13,14,27,16,81,18,19,36,21,22,39,24,81,

%T 26,27,28,33,54,31,32,33,162,63,36,37,38,39,72,41,42,75,44,81,78,47,

%U 48,49,162,243,52,57,54,99,56,57,66,59,108,61,62,63,64,117,66,67,324

%N Remultiply n first "downward", from N to GF(2)[X], and then remultiply that result back "upward", from GF(2)[X] to N: a(n) = A234742(A234741(n)).

%C This sequence appears to be completely multiplicative with a(p) = A234742(p) although neither A234741 or A234742 are even multiplicative. Terms tested up to n = 10^7. - _Andrew Howroyd_, Aug 01 2018

%C Yes, this is true. Consider for example n = p*q*r*r, where p, q, r are primes in N. Then A234741(n) = p1 x q1 x q2 x q3 x r1 x r2 x r1 x r2, where p1, q1, r1, ..., are the irreducible factors of p, q, r when factored over GF(2), and x stands for multiplication in ring GF(2)[X] (A048720). [Note that these irreducible factors are not necessarily primes in N, except p1 (= p), which must be a term of A091206. Also, A234741(p) = p for any prime p.] Next, a(n) = A234742(p1 x q1 x q2 x q3 x r1 x r2 x r1 x r2) = p1 * q1 * q2 * q3 * r1 * r2 * r1 * r2, which can be obtained also as a(p)*a(q)*a(r)*a(r), thus proving the multiplicativity. - _Antti Karttunen_, Aug 02 2018

%H Antti Karttunen, <a href="/A236852/b236852.txt">Table of n, a(n) for n = 0..8192</a>

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

%F a(n) = A234742(A234741(n)).

%e From _Antti Karttunen_, Aug 02 2018: (Start)

%e For n = 3, we have A234741(3) = 3 = 11 in binary, which encodes a (0,1)-polynomial x+1, which is irreducible over GF(2) thus A234742(3) = 3 and a(3) = 3.

%e For n = 5, we have A234741(5) = 5 = 101 in binary, which encodes a (0,1)-polynomial x^2 + 1, which factorizes as (x+1)(x+1) when factored over GF(2), that is 5 = A048720(3,3), thus it follows that A234742(5) = 3*3 = 9, and a(5) = 9.

%e For n = 9 = 3*3, we have A234741(9) = A048720(3,3) = 5, and A234742(5) = 9 as shown above. Also by multiplicativity, we have a(3*3) = a(3)*a(3) = 3*3 = 9.

%e (End)

%o (Scheme) (define (A236852 n) (A234742 (A234741 n)))

%Y Fixed points: A236860.

%Y Cf. A048720, A234741, A234742, A236851, A236836-A236837, A236846-A236847.

%K nonn,mult

%O 0,3

%A _Antti Karttunen_, Feb 02 2014

%E Keyword mult added after _Andrew Howroyd_'s observation. - _Antti Karttunen_, Aug 02 2018