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.

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, 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, 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

Offset: 1

Author

Antti Karttunen, May 11 2019

Keywords

• nonn

Comments

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.

Examples

			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.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..16384
• Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537
• Index entries for sequences related to polynomials in ring GF(2)[X]

Crossrefs

Cf. A032742, A048720, A325560, A325564, A325567, A325643.

Cf. A325559 (positions of ones, after the initial 1).

Programs

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)))));

PARI

A048720(b,c) = fromdigits(Vec(Pol(binary(b))*Pol(binary(c)))%2, 2);
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)

Formula

For all n, a(n) <= A032742(n).