login
a(1) = 1; for n > 1, a(n) = k for the least divisor d > 1 of n such that A048720(d,k) = n for some k.
4

%I #12 May 11 2019 18:33:37

%S 1,1,1,2,1,3,1,4,7,5,1,6,1,7,5,8,1,9,1,10,7,11,1,12,1,13,9,14,1,15,1,

%T 16,31,17,13,18,1,19,29,20,1,21,1,22,27,23,1,24,11,25,17,26,1,27,1,28,

%U 23,29,1,30,1,31,21,32,21,33,1,34,1,35,1,36,1,37,57,38,1,39,1,40,1,41,1,42,17,43,1,44,1,45,1,46,7,47,19

%N a(1) = 1; for n > 1, a(n) = k for the least divisor d > 1 of n such that A048720(d,k) = n for some k.

%C For n > 1, we first find the least divisor d of n that is larger than 1 and for which it holds that when the binary expansion of d is converted to a (0,1)-polynomial (e.g., 13=1101[2] encodes X^3 + X^2 + 1), then that polynomial is a divisor of (0,1)-polynomial similarly converted from n, when the division is done over GF(2). a(n) is then the quotient polynomial converted back to decimal via its binary encoding. See the example.

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

%H Antti Karttunen, <a href="/A325642/a325642.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 For all n >= 1, A048720(a(n), A325643(n)) = n.

%e For n = 9, its least nontrivial divisor is 3, and we find that 3 (in binary "11") corresponds to polynomial X + 1, which in this case is a factor of polynomial X^3 + 1 (corresponding to 9 as 9 is "1001" in binary) as the latter factorizes as (X + 1)(X^2 + X + 1) over GF(2), that is, 9 = A048720(3,7). Thus a(9) = 7.

%o (PARI) A325642(n) = if(1==n,n, my(p = Pol(binary(n))*Mod(1, 2)); fordiv(n,d,if((d>1),my(q = Pol(binary(d))*Mod(1, 2)); if(0==(p%q), return(fromdigits(Vec(lift(p/q)),2))))));

%Y Cf. A048720, A325641, A325643.

%K nonn

%O 1,4

%A _Antti Karttunen_, May 11 2019