A178908 - OEIS

%I #18 Jan 13 2019 05:57:54

%S 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 18,18,20,24,30,63,60,43,40,36,36,54,54,45,40,53,48,54,48,40,46,62,60,

%U 40,42,36,36,54,54,34,36,60,58,56,60,34,38,127,121,68,66,79,79,120,120

%N GF(2) sum of divisors of n.

%C 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 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 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 Antti Karttunen, <a href="/A178908/b178908.txt">Table of n, a(n) for n = 1..2047</a>

%H <a href="/index/Ge#GF2X">Index entries for sequences operating on polynomials in ring GF(2)[X]</a>

%F For all n >= 0, a(2^n) = A000203(2^n) = A280493(2^n) = A000225(1+n). - _Antti Karttunen_, Jan 11 2017

%e 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 (PARI) a(n)={local(p,fm,r,k);

%o while(n>0,p+=Mod(n,2)*x^k;n\=2;k++);

%o 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 subst(lift(r),x,2)}

%o (PARI) a(n) = {my(s = vecsum(divisors(Mod(1,2)*Pol(binary(n))))); subst(lift(s), x, 2);} \\ _Michel Marcus_, Jan 13 2019

%o (Scheme)

%o ;; A003987bi implements the 2-argument bitwise-XOR function (A003987).

%o ;; A091255bi implements the 2-argument GF(2)[X] GCD-function (A091255) which is used for checking that k is a divisor of n.

%o (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 ;; _Antti Karttunen_, Jan 11 2017

%Y Cf. A000203, A000225, A003987, A091220, A091255, A178909, A178910, A280493, A280499.

%K nonn

%O 1,2

%A _Franklin T. Adams-Watters_, Jun 22 2010