cp's OEIS Frontend

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

%I A325563 #20 May 11 2019 18:33:16
%S A325563 1,1,1,2,1,3,1,4,3,5,1,6,1,7,5,8,1,9,1,10,7,11,1,12,1,13,9,14,1,15,1,
%T A325563 16,3,17,7,18,1,19,3,20,1,21,1,22,15,23,1,24,7,25,17,26,1,27,1,28,3,
%U A325563 29,1,30,1,31,21,32,5,33,1,34,1,35,1,36,1,37,15,38,1,39,1,40,1,41,1,42,17,43,1,44,1,45,1,46,31,47,19,48,1,49,33,50
%N A325563 a(1) = 1; for n > 1, a(n) is the largest proper divisor d of n such that A048720(d,k) = n for some k.
%C A325563 For n > 1, a(n) is the largest proper divisor d of n 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 polynomial division is done over field GF(2). See the example.
%H A325563 Antti Karttunen, <a href="/A325563/b325563.txt">Table of n, a(n) for n = 1..16384</a>
%H A325563 Antti Karttunen, <a href="/A325563/a325563.txt">Data supplement: n, a(n) computed for n = 1..65537</a>
%H A325563 <a href="/index/Ge#GF2X">Index entries for sequences related to polynomials in ring GF(2)[X]</a>
%F A325563 For all n, a(n) <= A032742(n).
%e A325563 For n = 39 = 3*13, A032742(39) = 13, but 13 is not the answer because X^3 + X^2 + 1 does not divide X^5 + X^2 + X + 1 (39 is "100111" in binary) over GF(2). However, the next smaller divisor 3 works because X^5 + X^2 + X + 1 = (X^1 + 1)(X^4 + X^3 + X^2 + 1) when multiplication is done over GF(2). Note that 39 = A048720(3,29), where 29 is "11101" in binary. Thus a(39) = 3.
%o A325563 (PARI) A325563(n) = if(1==n,n, my(p = Pol(binary(n))*Mod(1, 2)); fordiv(n,d,if((d>1),my(q = Pol(binary(n/d))*Mod(1, 2)); if(0==(p%q), return(n/d)))));
%o A325563 (PARI)
%o A325563 A048720(b,c) = fromdigits(Vec(Pol(binary(b))*Pol(binary(c)))%2, 2);
%o A325563 A325563(n) = if(1==n,n,fordiv(n,d,if((d>1),for(t=1,n,if(A048720(n/d,t)==n,return(n/d)))))); \\ (Slow)
%Y A325563 Cf. A032742, A048720, A325560, A325564, A325567, A325643.
%Y A325563 Cf. A325559 (positions of ones, after the initial 1).
%K A325563 nonn
%O A325563 1,4
%A A325563 _Antti Karttunen_, May 11 2019