A268389 a(n) = greatest k such that polynomial (X+1)^k divides the polynomial (in polynomial ring GF(2)[X]) that is encoded in the binary expansion of n. (See the comments for details).

0, 0, 1, 0, 2, 1, 0, 0, 1, 2, 0, 1, 0, 0, 3, 0, 4, 1, 0, 2, 0, 0, 1, 1, 0, 0, 2, 0, 1, 3, 0, 0, 1, 4, 0, 1, 0, 0, 2, 2, 0, 0, 1, 0, 3, 1, 0, 1, 0, 0, 5, 0, 1, 2, 0, 0, 2, 1, 0, 3, 0, 0, 1, 0, 2, 1, 0, 4, 0, 0, 1, 1, 0, 0, 3, 0, 1, 2, 0, 2, 0, 0, 1, 0, 6, 1, 0, 0, 1, 3, 0, 1, 0, 0, 2, 1, 0, 0, 2, 0, 1, 5, 0, 0, 3, 1, 0, 2, 0, 0, 1, 0, 1, 2, 0, 1, 0, 0, 4, 3

Offset

1,5

Comments

a(n) gives the number of iterations of map k -> A006068(k)/2 that are required (when starting from k = n) until k is an odd number.

A001317 gives the record positions and particularly, A001317(n) gives the first occurrence of n in this sequence.

When polynomials over GF(2) are encoded in the binary representation of n in a natural way where each polynomial b(n)*X^n+...+b(0)*X^0 over GF(2) is represented by the binary number b(n)*2^n+...+b(0)*2^0 in N (each coefficient b(k) is either 0 or 1), then a(n) = the number of times polynomial X+1 (encoded by 3, "11" in binary) divides the polynomial encoded by n.

Links

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

Index entries for sequences operating on GF(2)[X]-polynomials

Formula

If A006068(n) is odd, then a(n) = 0, otherwise a(n) = 1 + a(A006068(n)/2).

Other identities. For all n >= 0:

a(A001317(n)) = n. [The sequence works as a left inverse of A001317.]

A048720(A268669(n),A048723(3,a(n))) = A048720(A268669(n),A001317(a(n))) = n.

A048724^a(n) (A268669(n)) = n. [The a(n)-th fold application (power) of A048724 when applied to A268669(n) gives n back.]

a(n) = A007949(A235042(n)).

a(A057889(n)) = a(n).

Example

For n = 5 ("101" in binary) which encodes polynomial x^2 + 1, we see that it can be factored over GF(2) as (X+1)(X+1), and thus a(5) = 2.
For n = 8 ("1000" in binary) which encodes polynomial x^3, we see that it is not divisible in ring GF(2)[X] by polynomial X+1, thus a(8) = 0.
For n = 9 ("1001" in binary) which encodes polynomial x^3 + 1, we see that it can be factored over GF(2) as (X+1)(X^2 + X + 1), and thus a(9) = 1.

Mathematica

f[n_] := Which[n == 1, 0, OddQ@ #, 0, EvenQ@ #, 1 + f[#/2]] &@ Fold[BitXor, n, Quotient[n, 2^Range[BitLength@ n - 1]]]; Array[f, {120}] (* Michael De Vlieger, Feb 12 2016, after Jan Mangaldan at A006068 *)

Prog

(PARI) a(n) = {my(b = binary(n), p = Pol(binary(n))*Mod(1, 2), k = poldegree(p)); while (type(p/(x+1)^k*Mod(1, 2)) != "t_POL", k--); k; } \\ Michel Marcus, Feb 12 2016
(Scheme)
;; This employs the given recurrence and uses memoization-macro definec:
(definec (A268389 n) (if (odd? (A006068 n)) 0 (+ 1 (A268389 (/ (A006068 n) 2)))))
(define (A268389 n) (let loop ((n n) (s 0)) (let ((k (A006068 n))) (if (odd? k) s (loop (/ k 2) (+ 1 s)))))) ;; Computed in a loop, no memoization.

Crossrefs

Cf. A001317, A006068, A007949, A048720, A048723, A048724, A057889, A268384, A235042, A268670.

Cf. A268669 (quotient left after (X+1)^a(n) has been divided out).

Cf. A268395 (partial sums).

Cf. A000069 (positions of zeros), A268679 (this sequence without zeros).

Cf. also A037096, A037097, A136386.

Sequence in context: A051777 A262709 A107628 * A288969 A305355 A218380

Adjacent sequences: A268386 A268387 A268388 * A268390 A268391 A268392

Keyword

nonn,base

Author

Antti Karttunen, Feb 10 2016

Status

approved