A178908 -id:A178908 - cp's OEIS frontend

A178910 Binary XOR of divisors of n.

1, 3, 2, 7, 4, 6, 6, 15, 11, 12, 10, 14, 12, 10, 8, 31, 16, 29, 18, 28, 16, 30, 22, 30, 29, 20, 16, 18, 28, 24, 30, 63, 40, 48, 32, 49, 36, 54, 40, 60, 40, 48, 42, 54, 44, 58, 46, 62, 55, 39, 32, 36, 52, 48, 56, 34, 40, 36, 58, 56, 60, 34, 38, 127, 72, 120, 66, 112, 80, 96, 70

Offset: 1

Franklin T. Adams-Watters, Jun 22 2010

If 2^k <= n < 2^(k+1), then also 2^k <= a(n) < 2^(k+1), since any proper divisor of n is < 2^k.

Reinhard Zumkeller, Table of n, a(n) for n = 1..8191

Cf. A000203, A178908, A178911, A003987.

Cf. A027750, A072594; subsequences A028982 (odd), A028982 (even).

import Data.Bits (xor)
a178910 = foldl1 xor . a027750_row :: Integer -> Integer
-- Reinhard Zumkeller, Nov 17 2012

a(n)=local(ds,r);ds=divisors(n);for(k=1,#ds,r=bitxor(r,ds[k]));r

from sympy import divisors
def A178910(n):
    res = 1
    for divisor in divisors(n)[1:]: res ^= divisor
    return res # Karl-Heinz Hofmann, May 30 2025

A280493 Sum of GF(2)[X] divisors of n: the sum is ordinary sum of integers, the summands being all the natural numbers whose binary expansions encode such (0,1)-polynomials that divide the (0,1)-polynomial encoded by n when the polynomial factorization is done over the field GF(2).

Original entry on oeis.org

1, 3, 4, 7, 9, 12, 8, 15, 20, 27, 12, 28, 14, 24, 24, 31, 41, 60, 20, 63, 29, 36, 40, 60, 26, 42, 52, 56, 44, 72, 32, 63, 68, 123, 56, 140, 38, 60, 88, 135, 42, 87, 72, 84, 112, 120, 48, 124, 68, 78, 92, 98, 76, 156, 56, 120, 102, 132, 60, 168, 62, 96, 104, 127, 201, 204, 68, 287, 81, 168, 136, 300, 74, 114, 192, 140, 140, 264, 112, 279, 95, 126, 192, 203

Offset: 1

Antti Karttunen, Jan 09 2017

nonn

This is roughly a GF(2)[X]-analog of A000203. A178908 gives another, maybe a more consistent analog.

			9 ("1001" in binary) encodes polynomial X^3 + 1, which is factored over GF(2) as (X+1)(X^2 + X + 1), where polynomial X + 1 is encoded by 3 ("11" in binary), and polynomial X^2 + X + 1 by 7 ("111" in binary), and furthermore (like all polynomials) it is also divisible by 1 and itself, thus a(9) = 1 + 3 + 7 + 9 = 20.

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

Row sums of triangles A280494 and A280499.
Cf. A000225, A000203, A178908.
Cf. A014580 (gives the positions where a(n) = n+1).

(define (A280493 n) (let loop ((k n) (s 0)) (if (zero? k) s (loop (- k 1) (+ s (if (= k (A091255bi n k)) k 0))))))
;; A091255bi implements the 2-argument GF(2)[X] GCD-function (A091255) which is used for checking that k is a divisor of n.
;; Another version:
(define (A280493 n) (add A280494 (+ 1 (A000217 (- n 1))) (A000217 n)))
(define (add intfun lowlim uplim) (let sumloop ((i lowlim) (res 0)) (cond ((> i uplim) res) (else (sumloop (+ 1 i) (+ res (intfun i)))))))

For all n >= 0, a(2^n) = A000203(2^n) = A178908(2^n) = A000225(1+n).

A280499 Triangular table for division in ring GF(2)[X]: T(n,k) = n/k, or 0 if k is not a divisor of n, where the binary expansion of each number defines the corresponding (0,1)-polynomial.

Original entry on oeis.org

1, 2, 1, 3, 0, 1, 4, 2, 0, 1, 5, 0, 3, 0, 1, 6, 3, 2, 0, 0, 1, 7, 0, 0, 0, 0, 0, 1, 8, 4, 0, 2, 0, 0, 0, 1, 9, 0, 7, 0, 0, 0, 3, 0, 1, 10, 5, 6, 0, 2, 3, 0, 0, 0, 1, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 12, 6, 4, 3, 0, 2, 0, 0, 0, 0, 0, 1, 13, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 14, 7, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 1, 15, 0, 5, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

Offset: 1

Antti Karttunen, Jan 09 2017

This is GF(2)[X] analog of A126988, using "carryless division in base-2" instead of ordinary division.

The triangular table T(n,k), n=1.., k=1..n is read by rows: T(1,1), T(2,1), T(2,2), T(3,1), T(3,2), T(3,3), etc.

			The first 17 rows of the triangle:
   1
   2 1
   3 0 1
   4 2 0 1
   5 0 3 0 1
   6 3 2 0 0 1
   7 0 0 0 0 0 1
   8 4 0 2 0 0 0 1
   9 0 7 0 0 0 3 0 1
  10 5 6 0 2 3 0 0 0 1
  11 0 0 0 0 0 0 0 0 0 1
  12 6 4 3 0 2 0 0 0 0 0 1
  13 0 0 0 0 0 0 0 0 0 0 0 1
  14 7 0 0 0 0 2 0 0 0 0 0 0 1
  15 0 5 0 3 0 0 0 0 0 0 0 0 0 1
  16 8 0 4 0 0 0 2 0 0 0 0 0 0 0 1
  17 0 15 0 5 0 0 0 0 0 0 0 0 0 3 0 1
  -----------------------------------
7 ("111" in binary) encodes polynomial X^2 + X + 1, which is irreducible over GF(2) (7 is in A014580), so it is divisible only by itself and 1, and thus T(7,1) = 7, T(7,k) = 0 for k=2..6 and T(7,7) = 1.
9 ("1001" in binary) encodes polynomial X^3 + 1, which is factored over GF(2) as (X+1)(X^2 + X + 1), and thus T(9,3) = 7 and T(9,7) = 3 because the polynomial X + 1 is encoded by 3 ("11" in binary).

Lower triangular region of square array A280500.
Transpose: A280494.
Cf. A014580, A048720, A126988, A178908, A280500, A280493 (the row sums).

(define (A280499 n) (A280500bi (A002024 n) (A002260 n))) ;; Code for A280500bi given in A280500.

T(n,k) = the unique d such that A048720(d,k) = n, provided that such d exists, otherwise zero.

A178909 Indices of perfect polynomials over GF(2).

Original entry on oeis.org

1, 6, 36, 54, 120, 2470, 2640, 3144, 3780, 32640, 41280, 52632, 67184, 1098176, 1157904, 2147450880

Offset: 1

Franklin T. Adams-Watters, Jun 22 2010

Numbers k such that k = A178908(k); sum of divisors of k-th GF(2) polynomial is the polynomial itself.

a(17) > 5*10^9. - Amiram Eldar, Oct 28 2019

Cf. A178908, A091220, A000396, A178911.

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

a(14)-a(15) from Amiram Eldar, Jan 13 2019

a(16) from Amiram Eldar, Oct 28 2019

A346795 Irregular triangle T(n, k), n > 0, k = 1..A091220(n), read by rows; the n-th row gives, in ascending order, the distinct integers k such that A048720(k, m) = n for some m.

Original entry on oeis.org

1, 1, 2, 1, 3, 1, 2, 4, 1, 3, 5, 1, 2, 3, 6, 1, 7, 1, 2, 4, 8, 1, 3, 7, 9, 1, 2, 3, 5, 6, 10, 1, 11, 1, 2, 3, 4, 6, 12, 1, 13, 1, 2, 7, 14, 1, 3, 5, 15, 1, 2, 4, 8, 16, 1, 3, 5, 15, 17, 1, 2, 3, 6, 7, 9, 14, 18, 1, 19, 1, 2, 3, 4, 5, 6, 10, 12, 20, 1, 7, 21

Offset: 1

Rémy Sigrist, Sep 29 2021

The n-th row corresponds to the divisors of the n-th GF(2)[X]-polynomial.
The greatest value both in the n-th row and in the k-th row corresponds to A091255(n, k).
The index of the first row containing both n and k corresponds to A091256(n, k).

			The triangle starts:
      1:   [1]
      2:   [1, 2]
      3:   [1, 3]
      4:   [1, 2, 4]
      5:   [1, 3, 5]
      6:   [1, 2, 3, 6]
      7:   [1, 7]
      8:   [1, 2, 4, 8]
      9:   [1, 3, 7, 9]
     10:   [1, 2, 3, 5, 6, 10]
     11:   [1, 11]
     12:   [1, 2, 3, 4, 6, 12]
     13:   [1, 13]
     14:   [1, 2, 7, 14]
     15:   [1, 3, 5, 15]

Rémy Sigrist, Table of n, a(n) for n = 1..9228 (first 1024 rows flattened)
Rémy Sigrist, PARI program for A346795
Index entries for sequences operating on GF(2)[X]-polynomials

Cf. A048720, A091220, A091255, A091256, A091257, A178908, A280493, A348135.

PARI
```
See Links section.
```

T(n, 1) = 1.
T(n, A091220(n)) = n.
Sum_{k = 1..A091220(n)} T(n, k) = A280493(n).
T(n, 1) XOR ... XOR T(n, A091220(n)) = A178908(n) (where XOR denotes the bitwise XOR operator).

cp's OEIS Frontend

A178910 Binary XOR of divisors of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

PARI

Python

A280493 Sum of GF(2)[X] divisors of n: the sum is ordinary sum of integers, the summands being all the natural numbers whose binary expansions encode such (0,1)-polynomials that divide the (0,1)-polynomial encoded by n when the polynomial factorization is done over the field GF(2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Scheme

Formula

A280499 Triangular table for division in ring GF(2)[X]: T(n,k) = n/k, or 0 if k is not a divisor of n, where the binary expansion of each number defines the corresponding (0,1)-polynomial.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Scheme

Formula

A178909 Indices of perfect polynomials over GF(2).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Extensions

A346795 Irregular triangle T(n, k), n > 0, k = 1..A091220(n), read by rows; the n-th row gives, in ascending order, the distinct integers k such that A048720(k, m) = n for some m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula