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

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.

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, a(n) <= A032742(n).

Example

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.

Prog

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

Crossrefs

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

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

Sequence in context: A353271 A326139 A325641 * A159353 A032742 A060654

Adjacent sequences: A325560 A325561 A325562 * A325564 A325565 A325566

Keyword

nonn

Author

Antti Karttunen, May 11 2019

Status

approved