cp's OEIS Frontend

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

%I A268389 #45 Feb 13 2016 23:15:09
%S A268389 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,
%T A268389 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,
%U A268389 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
%N 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).
%C A268389 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.
%C A268389 A001317 gives the record positions and particularly, A001317(n) gives the first occurrence of n in this sequence.
%C A268389 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.
%H A268389 Antti Karttunen, <a href="/A268389/b268389.txt">Table of n, a(n) for n = 1..65537</a>
%H A268389 <a href="/index/Ge#GF2X">Index entries for sequences operating on GF(2)[X]-polynomials</a>
%F A268389 If A006068(n) is odd, then a(n) = 0, otherwise a(n) = 1 + a(A006068(n)/2).
%F A268389 Other identities. For all n >= 0:
%F A268389 a(A001317(n)) = n. [The sequence works as a left inverse of A001317.]
%F A268389 A048720(A268669(n),A048723(3,a(n))) = A048720(A268669(n),A001317(a(n))) = n.
%F A268389 A048724^a(n) (A268669(n)) = n. [The a(n)-th fold application (power) of A048724 when applied to A268669(n) gives n back.]
%F A268389 a(n) = A007949(A235042(n)).
%F A268389 a(A057889(n)) = a(n).
%e A268389 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.
%e A268389 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.
%e A268389 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.
%t A268389 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 *)
%o A268389 (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
%o A268389 (Scheme)
%o A268389 ;; This employs the given recurrence and uses memoization-macro definec:
%o A268389 (definec (A268389 n) (if (odd? (A006068 n)) 0 (+ 1 (A268389 (/ (A006068 n) 2)))))
%o A268389 (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.
%Y A268389 Cf. A001317, A006068, A007949, A048720, A048723, A048724, A057889, A268384, A235042, A268670.
%Y A268389 Cf. A268669 (quotient left after (X+1)^a(n) has been divided out).
%Y A268389 Cf. A268395 (partial sums).
%Y A268389 Cf. A000069 (positions of zeros), A268679 (this sequence without zeros).
%Y A268389 Cf. also A037096, A037097, A136386.
%K A268389 nonn,base
%O A268389 1,5
%A A268389 _Antti Karttunen_, Feb 10 2016