cp's OEIS Frontend

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

%I A325643 #16 May 11 2019 18:33:44
%S A325643 1,2,3,2,5,2,7,2,3,2,11,2,13,2,3,2,17,2,19,2,7,2,23,2,25,2,3,2,29,2,
%T A325643 31,2,3,2,7,2,37,2,3,2,41,2,43,2,3,2,47,2,7,2,3,2,53,2,55,2,3,2,59,2,
%U A325643 61,2,3,2,5,2,67,2,69,2,71,2,73,2,3,2,77,2,79,2,81,2,83,2,5,2,87,2,89,2,91,2,31,2,5,2,97,2,3,2,101,2,103,2,3
%N A325643 a(1) = 1; for n > 1, a(n) is the least divisor d > 1 of n such that A048720(d,k) = n for some k.
%C A325643 For n > 1, a(n) is 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). See the example.
%H A325643 Antti Karttunen, <a href="/A325643/b325643.txt">Table of n, a(n) for n = 1..16384</a>
%H A325643 <a href="/index/Ge#GF2X">Index entries for sequences related to polynomials in ring GF(2)[X]</a>
%F A325643 a(2n) = 2.
%F A325643 For all n >= 1, a(A325559(n)) = A325559(n).
%F A325643 For all n >= 1, n = a(n) * A325641(n) = A048720(a(n), A325642(n)).
%e A325643 For n = 21 = 3*7, 3 is not the answer because X^1 + 1 does not divide X^4 + X^2 + 1 (21 is "10101" in binary) over GF(2). However, the next larger divisor 7 works because X^4 + X^2 + 1 = (X^2 + X^1 + 1)^2 when multiplication is done over GF(2) (note that A048720(7,7) = 21). Thus a(21) = 7.
%o A325643 (PARI) A325643(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(d)))));
%Y A325643 Cf. A048720, A325559 (fixed points after 1), A325563, A325641, A325642.
%K A325643 nonn
%O A325643 1,2
%A A325643 _Antti Karttunen_, May 11 2019