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

Author

Frank Ruskey

Keywords

• nonn

Comments

Second row of the array A158502(n, k) = phi(p^k-1)/k, p=prime(n). - 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

Programs

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

PARI

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