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

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.

Links

Antti Karttunen, Table of n, a(n) for n = 1..16384

Index entries for sequences related to polynomials in ring GF(2)[X]

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

Example

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.

Prog

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

Crossrefs

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

Sequence in context: A020639 A092067 A214606 * A353270 A356838 A079879

Adjacent sequences: A325640 A325641 A325642 * A325644 A325645 A325646

Keyword

nonn

Author

Antti Karttunen, May 11 2019

Status

approved