A370717 Arithmetic derivative of elements of GF(2)[x], evaluated at x=2.

0, 0, 1, 1, 0, 0, 1, 1, 4, 4, 5, 1, 4, 1, 5, 5, 0, 0, 1, 1, 0, 0, 9, 14, 4, 1, 15, 5, 4, 8, 5, 1, 16, 28, 17, 10, 16, 1, 17, 5, 20, 1, 21, 26, 4, 20, 11, 1, 16, 12, 27, 17, 4, 16, 17, 1, 20, 5, 13, 1, 20, 1, 29, 21

Offset

0,9

Comments

The indices of this sequence are sorted by evaluation at x=2, i.e. 0, 1, x, x+1, x^2, x^2+1, etc. Generalization of arithmetic derivative is as described by Victor Ufnarovski and Bo Ahlander. For a general UFD this requires a choice of canon primes for which p' = 1. However, GF(2)[x] has only one unit, so there is a unique arithmetic derivative over this UFD.

The arithmetic derivative of a square polynomial in GF(2)[x] is 0 so square polynomials act like units: given f, g in GF(2)[x], (f*f*g)' = f*f*(g'). The arithmetic derivative of a positive degree squarefree polynomial in GF(2)[x] is always nonzero.

Links

Table of n, a(n) for n=0..63.

Victor Ufnarovski and Bo Ahlander, How to Differentiate a Number, J. Integer Seqs., Vol. 6, 2003.

Example

To find a(9), first convert 9 into its corresponding GF(2) polynomial x^3 + 1. Then find its arithmetic derivative, x^2. Finally, convert to an integer via evaluation at x=2, giving a(9) = 4.

Prog

(SageMath)
P.<x> = GF(2)[]
def AD(p):
  F = list(p.factor())
  f = [f[0] for f in F for _ in range(f[1])]
  return SymmetricFunctions(P).e()([len(f)-1, 0]).expand(len(f))(f)
def more(l):
  return [x*p for p in l]+[x*p+1 for p in l]
L = [x, x+1]
L = L + more(L) + more(more(L)) + more(more(more(L))) + more(more(more(more(L))))
L.sort()
', '.join(map(str, ([0, 0]+[AD(p).change_ring(ZZ)(2) for p in L])))

Crossrefs

Cf. A003415, A099379, A099380.

Sequence in context: A200694 A021696 A006581 * A255902 A019922 A092171

Adjacent sequences: A370714 A370715 A370716 * A370718 A370719 A370720

Keyword

nonn

Author

Keith J. Bauer, Feb 27 2024

Status

approved