A325642 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.

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

Offset: 1

Author

Antti Karttunen, May 11 2019

Keywords

• nonn

Comments

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.

Examples

			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.
		

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. A048720, A325641, A325643.

Programs

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

Formula

For all n >= 1, A048720(a(n), A325643(n)) = n.