A027385 Number of primitive polynomials of degree n over GF(3).

1, 2, 4, 8, 22, 48, 156, 320, 1008, 2640, 7700, 13824, 61320, 170352, 401280, 983040, 3796100, 7838208, 30566592, 62304000, 229686912, 670824000, 2003046356, 3583180800, 15403487000, 48881851200, 128672022528, 314657860608, 1163185915872, 2340264960000, 9947788640064

Offset

1,2

Comments

Second row of the array T(n,k) = phi(p^k-1)/k, p=prime(n), which starts

1, 1, 2, 2, 6, 6, 18, 16, ... A011260

1, 2, 4, 8, 22, 48, 156, 320, ... here

2, 4, 20, 48, 280, 720, 5580, 14976, ... A027741

2, 8, 36, 160, 1120, 6048, 37856, 192000, ... A027743

4, 16, 144, 960, 12880, 62208, 1087632, 7027200, ... A319166

4, 24, 240, 1536, 24752, 224640, 2988024, 21934080, ...

8, 48, 816, 5376, 141984, 1057536, 29309904, 224501760, ...

- R. J. Mathar, Aug 24 2011

From Joerg Arndt, Oct 03 2012: (Start)

Number of base-3, length-n Lyndon words w such that gcd(w, 3^n-1)==1 (where w is interpreted as a radix-3 number); replacing 3 by any prime p gives the analogous statement for GF(p).

The statement above is the consequence of the following.

Let p be a prime and g be a generator of GF(p^n). If w is a base-p, length-n Lyndon word then f=g^w (where w is interpreted as a radix-p number) has an irreducible characteristic polynomial C (over GF(p)) and, if gcd(w,p^n-1)==1 then C is primitive.

(End)

Links

Vaclav Kotesovec, Table of n, a(n) for n = 1..200 (terms 1..100 from Seiichi Manyama)

Eric W. Weisstein, MathWorld: Totient Function

Wikipedia, Euler's totient function

Maple

A027385 := proc(n) numtheory[phi](3^n-1)/n; end proc:

Mathematica

Table[EulerPhi[3^n - 1]/n, {n, 1, 30}] (* Vaclav Kotesovec, Nov 23 2017 *)

Prog

(PARI) a(n) = eulerphi(3^n-1)/n; /* Joerg Arndt, Aug 25 2011 */

Crossrefs

Sequence in context: A027713 A155765 A217975 * A158324 A002075 A337720

Adjacent sequences: A027382 A027383 A027384 * A027386 A027387 A027388

Keyword

nonn

Author

Frank Ruskey

Status

approved