A300628 -id:A300628 - cp's OEIS frontend

A054660 Number of monic irreducible polynomials over GF(4) of degree n with fixed nonzero trace.

1, 2, 5, 16, 51, 170, 585, 2048, 7280, 26214, 95325, 349520, 1290555, 4793490, 17895679, 67108864, 252645135, 954437120, 3616814565, 13743895344, 52357696365, 199911205050, 764877654105, 2932031006720, 11258999068416

Offset: 1

N. J. A. Sloane, Apr 18 2000

Also number of Lyndon words of length n with trace 1 over GF(4).
Let x = RootOf( z^2+z+1 ) and y = 1+x. Also number of Lyndon words of length n with trace x over GF(4). Also number of Lyndon words of length n with trace y over GF(4).
Also number of 4-ary Lyndon words (i.e., Lyndon words over Z_4) of length n with trace 1 (mod 4). Also the same with trace 3 (mod 4). - Andrey Zabolotskiy, Dec 19 2020

			a(3; y)=5 since the five Lyndon words over GF(4) of trace y and length 3 are { 00y, 01x, 0x1, 11y, xxy }; the five Lyndon words over Z_4 of trace 1 (mod 4) and length 3 are { 001, 023, 032, 113, 122 }.

Seiichi Manyama, Table of n, a(n) for n = 1..1000
F. Ruskey, Number of monic irreducible polynomials over GF(q) with given trace
F. Ruskey, Number of q-ary Lyndon words with given trace mod q
F. Ruskey, Number of Lyndon words over GF(q) with given trace

Cf. A000048, A051841, A046211, A046209, A054661, etc.
Cf. A008683, A054661, A027377, A300628, A074033, A074034, A074035, A074448, A074449, A074450.
Cf. A074406, A074407, A074408, A074409.

From Seiichi Manyama, Mar 11 2018: (Start)
a(n) = A000048(2*n) = (1/(4*n)) * Sum_{odd d divides n} mu(d)*4^(n/d), where mu is the Möbius function A008683.
a(n+1) = A300628(n,n) for n >= 0. (End)
From Andrey Zabolotskiy, Dec 19 2020: (Start)
a(n) = A074033(n) + A074034(n) + 2 * A074035(n).
a(n) = A074448(n) + A074449(n) + 2 * A074450(n).
a(n) = A074406(n) + A074407(n) + A074408(n) + A074409(n). (End)

More terms from James Sellers, Apr 19 2000

A053633 Triangular array T(n,k) giving coefficients in expansion of Product_{j=1..n} (1+x^j) mod x^(n+1)-1.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 2, 2, 2, 2, 4, 3, 3, 3, 3, 6, 5, 5, 6, 5, 5, 10, 9, 9, 9, 9, 9, 9, 16, 16, 16, 16, 16, 16, 16, 16, 30, 28, 28, 29, 28, 28, 29, 28, 28, 52, 51, 51, 51, 51, 52, 51, 51, 51, 51, 94, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 172, 170, 170, 172, 170, 170, 172

Offset: 0

N. J. A. Sloane, Mar 22 2000

T(n,k) = number of binary vectors (x_1,...,x_n) satisfying Sum_{i=1..n} i*x_i = k (mod n+1) = size of Varshamov-Tenengolts code VT_k(n).

			Triangle begins:
  k  0    1    2    3    4    5    6    7    8    9
n
0    1;
1    1,   1;
2    2,   1,   1;
3    2,   2,   2,   2;
4    4,   3,   3,   3,   3;
5    6,   5,   5,   6,   5,   5;
6   10,   9,   9,   9,   9,   9,   9;
7   16,  16,  16,  16,  16,  16,  16,  16;
8   30,  28,  28,  29,  28,  28,  29,  28,  28;
9   52,  51,  51,  51,  51,  52,  51,  51,  51,  51;
    ...
[Edited by _Seiichi Manyama_, Mar 11 2018]

B. D. Ginsburg, On a number theory function applicable in coding theory, Problemy Kibernetiki, No. 19 (1967), pp. 249-252.

Seiichi Manyama, Rows n = 0..139, flattened
F. J. van de Bult, D. C. Gijswijt, J. P. Linderman, N. J. A. Sloane and Allan Wilks, A Slow-Growing Sequence Defined by an Unusual Recurrence, J. Integer Sequences, Vol. 10 (2007), #07.1.2.
F. J. van de Bult, D. C. Gijswijt, J. P. Linderman, N. J. A. Sloane and Allan Wilks, A Slow-Growing Sequence Defined by an Unusual Recurrence [pdf, ps].
N. J. A. Sloane, On single-deletion-correcting codes
Index entries for sequences related to subset sums modulo m
Index entries for sequences related to Gijswijt's sequence

Cf. A053632, A063776, A300328, A300628. Leading coefficients give A000016, next column gives A000048.

with(numtheory): A053633 := proc(n,k) local t1,d; t1 := 0; for d from 1 to n do if n mod d = 0 and d mod 2 = 1 then t1 := t1+(1/(2*n))*2^(n/d)*phi(d)*mobius(d/gcd(d,k))/phi(d/gcd(d,k)); fi; od; t1; end;

Flatten[ Table[ CoefficientList[ PolynomialMod[ Product[1+x^j, {j,1,n}], x^(n+1)-1], x], {n,0,11}]] (* Jean-François Alcover, May 04 2011 *)

The Maple code gives an explicit formula.

A298983 Triangle read by rows T(n,k) giving coefficients in expansion of Product_{j=1..n} (1-x^j)^2 mod x^(n+1)-1.

Original entry on oeis.org

1, 2, -2, 6, -3, -3, 8, 0, -8, 0, 20, -5, -5, -5, -5, 12, 6, -6, -12, -6, 6, 42, -7, -7, -7, -7, -7, -7, 32, 0, 0, 0, -32, 0, 0, 0, 54, 0, 0, -27, 0, 0, -27, 0, 0, 40, 10, -10, 10, -10, -40, -10, 10, -10, 10, 110, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11

Offset: 0

Seiichi Manyama, Mar 10 2018

			Triangle begins:
  k   0    1    2    3    4    5    6
n
0     1;
1     2,  -2;
2     6,  -3,  -3;
3     8,   0,  -8,   0;
4    20,  -5,  -5,  -5,  -5;
5    12,   6,  -6, -12,  -6,   6;
6    42,  -7,  -7,  -7,  -7,  -7,  -7;

Seiichi Manyama, Rows n = 0..139, flattened

Cf. A002618, A055615, A282634, A300628.

T(n,k) = (n+1) * Sum_{d | gcd(n+1,n+1-k)} d*mu((n+1)/d) for 0 <= k <= n.

So T(n,0) = A002618(n+1) and T(n,n) = A055615(n+1).

A300668 a(n) = A000016(2*n).

Original entry on oeis.org

1, 1, 2, 6, 16, 52, 172, 586, 2048, 7286, 26216, 95326, 349536, 1290556, 4793492, 17895736, 67108864, 252645136, 954437292, 3616814566, 13743895360, 52357696956, 199911205052, 764877654106, 2932031008768, 11258999068468, 43303842570872, 166799986203766, 643371375338656, 2484744621997516

Offset: 0

Seiichi Manyama, Mar 10 2018

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..1667

Cf. A000010 (phi), A000016, A300628.

a[n_] := DivisorSum[n, EulerPhi[#] * 4^(n/#) &, OddQ[#] &] / (4*n); a[0] = 1; Array[a, 30, 0] (* Amiram Eldar, Oct 04 2023 *)

a(n) = if (n==0, 1, sumdiv(n, d, if (d % 2, eulerphi(d)*4^(n/d)))/(4*n));  \\ Michel Marcus, Mar 11 2018

a(n) = (1/(4*n)) * Sum_{odd d divides n} phi(d)*4^(n/d) for n > 0.

a(n+1) = A300628(n,0).

cp's OEIS Frontend

A054660 Number of monic irreducible polynomials over GF(4) of degree n with fixed nonzero trace.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A053633 Triangular array T(n,k) giving coefficients in expansion of Product_{j=1..n} (1+x^j) mod x^(n+1)-1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A298983 Triangle read by rows T(n,k) giving coefficients in expansion of Product_{j=1..n} (1-x^j)^2 mod x^(n+1)-1.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A300668 a(n) = A000016(2*n).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula