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

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.

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]

Formula

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

Example

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.

Prog

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

Crossrefs

Cf. A048720, A325641, A325643.

Sequence in context: A050382 A197956 A054072 * A110977 A295785 A069230

Adjacent sequences: A325639 A325640 A325641 * A325643 A325644 A325645

Keyword

nonn

Author

Antti Karttunen, May 11 2019

Status

approved