cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-4 of 4 results.

A178908 GF(2) sum of divisors of n.

Original entry on oeis.org

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

Views

Author

Franklin T. Adams-Watters, Jun 22 2010

Keywords

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

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

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

Views

Author

Antti Karttunen, Jan 09 2017

Keywords

Comments

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.

Examples

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

Links

Crossrefs

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

Programs

Formula

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

A280494 Rows of triangular table A280499 read in reverse order.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Jan 09 2017

Keywords

Comments

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

Examples

			The first 17 rows of the triangle:
1
1 2
1 0 3
1 0 2 4
1 0 3 0 5
1 0 0 2 3 6
1 0 0 0 0 0 7
1 0 0 0 2 0 4 8
1 0 3 0 0 0 7 0 9
1 0 0 0 3 2 0 6 5 10
1 0 0 0 0 0 0 0 0 0 11
1 0 0 0 0 0 2 0 3 4 6 12
1 0 0 0 0 0 0 0 0 0 0 0 13
1 0 0 0 0 0 0 2 0 0 0 0 7 14
1 0 0 0 0 0 0 0 0 0 3 0 5 0 15
1 0 0 0 0 0 0 0 2 0 0 0 4 0 8 16
1 0 3 0 0 0 0 0 0 0 0 0 5 0 15 0 17

Links

Crossrefs

Cf. A048720, A127013, A280499, A280500, A280493 (the row sums).

Programs

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

Views

Author

Rémy Sigrist, Sep 29 2021

Keywords

Comments

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

Examples

			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]

Links

Crossrefs

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

Programs

  • PARI
    See Links section.

Formula

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).
Showing 1-4 of 4 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.