This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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). 15
 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 (list; graph; refs; listen; history; text; internal format)
 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 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 19 13:38 EDT 2018. Contains 316361 sequences. (Running on oeis4.)