cp's OEIS Frontend

A178908 GF(2) sum of divisors of n.

%I A178908 #18 Jan 13 2019 05:57:54
%S A178908 1,3,2,7,7,6,6,15,12,9,10,14,12,10,8,31,25,20,18,21,19,30,24,30,24,20,
%T A178908 18,18,20,24,30,63,60,43,40,36,36,54,54,45,40,53,48,54,48,40,46,62,60,
%U A178908 40,42,36,36,54,54,34,36,60,58,56,60,34,38,127,121,68,66,79,79,120,120
%N A178908 GF(2) sum of divisors of n.
%C A178908 Take the n-th GF(2) polynomial, compute its sum of divisors, and find the index of that polynomial in the list of GF(2) polynomials.
%C A178908 If 2^k <= n < 2^(k+1), then also 2^k <= a(n) < 2^(k+1), since any proper divisor of a GF(2) polynomial has lower degree.
%C A178908 Numbers whose binary representations correspond to the divisors occur as the nonzero terms on row n of A280499, and they are XORed together to obtain a(n). A280493 gives another GF(2)[X]-analog of A000203. - _Antti Karttunen_, Jan 11 2017
%H A178908 Antti Karttunen, <a href="/A178908/b178908.txt">Table of n, a(n) for n = 1..2047</a>
%H A178908 <a href="/index/Ge#GF2X">Index entries for sequences operating on polynomials in ring GF(2)[X]</a>
%F A178908 For all n >= 0, a(2^n) = A000203(2^n) = A280493(2^n) = A000225(1+n). - _Antti Karttunen_, Jan 11 2017
%e A178908 5 => x^2 + 1 = (x+1)^2. sigma((x+1)^2) = (x+1)^2 + x+1 + 1 = x^2 + x + 1 => 7, so a(5) = 7. (All polynomials here are over GF(2).)
%o A178908 (PARI) a(n)={local(p,fm,r,k);
%o A178908 while(n>0,p+=Mod(n,2)*x^k;n\=2;k++);
%o A178908 r=Mod(1,2);fm=factor(p);for(k=1,matsize(fm)[1],r*=(fm[k,1]^(fm[k,2]+1)-1)/(fm[k,1]-1));
%o A178908 subst(lift(r),x,2)}
%o A178908 (PARI) a(n) = {my(s = vecsum(divisors(Mod(1,2)*Pol(binary(n))))); subst(lift(s), x, 2);} \\ _Michel Marcus_, Jan 13 2019
%o A178908 (Scheme)
%o A178908 ;; A003987bi implements the 2-argument bitwise-XOR function (A003987).
%o A178908 ;; A091255bi implements the 2-argument GF(2)[X] GCD-function (A091255) which is used for checking that k is a divisor of n.
%o A178908 (define (A178908 n) (let loop ((k n) (s 0)) (if (zero? k) s (loop (- k 1) (A003987bi s (if (= k (A091255bi n k)) k 0))))))
%o A178908 ;; _Antti Karttunen_, Jan 11 2017
%Y A178908 Cf. A000203, A000225, A003987, A091220, A091255, A178909, A178910, A280493, A280499.
%K A178908 nonn
%O A178908 1,2
%A A178908 _Franklin T. Adams-Watters_, Jun 22 2010