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,2

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

Links

Antti Karttunen, Table of n, a(n) for n = 1..2047

Index entries for sequences operating on polynomials in ring GF(2)[X]

Formula

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

Example

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

Prog

(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

Crossrefs

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

Sequence in context: A075701 A016603 A199183 * A198552 A120633 A095353

Adjacent sequences: A178905 A178906 A178907 * A178909 A178910 A178911

Keyword

nonn

Author

Franklin T. Adams-Watters, Jun 22 2010

Status

approved