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.

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

Offset: 1

Author

Antti Karttunen, May 11 2019

Keywords

• nonn

Comments

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.

Examples

			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.
		

Links

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

Crossrefs

Cf. A048720, A325559 (fixed points after 1), A325563, A325641, A325642.

Programs

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

Formula

a(2n) = 2.

For all n >= 1, a(A325559(n)) = A325559(n).

For all n >= 1, n = a(n) * A325641(n) = A048720(a(n), A325642(n)).