A178908 GF(2) sum of divisors of n.

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, 18, 18, 20, 24, 30, 63, 60, 43, 40, 36, 36, 54, 54, 45, 40, 53, 48, 54, 48, 40, 46, 62, 60, 40, 42, 36, 36, 54, 54, 34, 36, 60, 58, 56, 60, 34, 38, 127, 121, 68, 66, 79, 79, 120, 120

Offset: 1

Author

Franklin T. Adams-Watters, Jun 22 2010

Keywords

• nonn

Comments

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.

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.

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

Examples

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

Links

• Antti Karttunen, Table of n, a(n) for n = 1..2047
• Index entries for sequences operating on polynomials in ring GF(2)[X]

Crossrefs

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

Programs

PARI

a(n)={local(p,fm,r,k);
while(n>0,p+=Mod(n,2)*x^k;n\=2;k++);
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));
subst(lift(r),x,2)}

PARI

a(n) = {my(s = vecsum(divisors(Mod(1,2)*Pol(binary(n))))); subst(lift(s), x, 2);} \\ Michel Marcus, Jan 13 2019

Scheme

;; A003987bi implements the 2-argument bitwise-XOR function (A003987).
;; A091255bi implements the 2-argument GF(2)[X] GCD-function (A091255) which is used for checking that k is a divisor of n.
(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))))))
;; Antti Karttunen, Jan 11 2017

Formula

For all n >= 0, a(2^n) = A000203(2^n) = A280493(2^n) = A000225(1+n). - Antti Karttunen, Jan 11 2017