A027385 -id:A027385 - cp's OEIS frontend

A369291 Array read by antidiagonals: T(n,k) = phi(k^n-1)/n, where phi is Euler's totient function (A000010), n >= 1, k >= 2.

1, 1, 1, 2, 2, 2, 2, 4, 4, 2, 4, 4, 12, 8, 6, 2, 12, 20, 32, 22, 6, 6, 8, 56, 48, 120, 48, 18, 4, 18, 36, 216, 280, 288, 156, 16, 6, 16, 144, 160, 1240, 720, 1512, 320, 48, 4, 30, 96, 432, 1120, 5040, 5580, 4096, 1008, 60, 10, 16, 216, 640, 5400, 6048, 31992, 14976, 15552, 2640, 176

Offset: 1

Andrew Howroyd, Jan 28 2024

For k a prime power, T(n,k) is the number of primitive polynomials of degree n over GF(k). See A011260, A027385 for additional information.

			Array begins:
n\k|  2   3    4     5      6      7      8       9 ...
---+---------------------------------------------------
 1 |  1   1    2     2      4      2      6       4 ...
 2 |  1   2    4     4     12      8     18      16 ...
 3 |  2   4   12    20     56     36    144      96 ...
 4 |  2   8   32    48    216    160    432     640 ...
 5 |  6  22  120   280   1240   1120   5400    5280 ...
 6 |  6  48  288   720   5040   6048  23328   27648 ...
 7 | 18 156 1512  5580  31992  37856 254016  340704 ...
 8 | 16 320 4096 14976 139968 192000 829440 1966080 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 antidiagonals)
Eric Weisstein's World of Mathematics, Totient Function.
Wikipedia, Euler's totient function.

Rows n=1..3 and 5 are A000010(k-1), A319210, A319213, A319214.
Columns 2..11 are A011260, A027385, A027695, A027741, A295496, A027743, A027744, A027745, A295497, A319166.
Cf. A319183.

A369291[n_, k_] := EulerPhi[k^n - 1]/n;
Table[A369291[k, n-k+2], {n, 15}, {k, n}] (* Paolo Xausa, Jun 17 2024 *)

PARI
```
T(n,k) = eulerphi(k^n-1)/n
```

A295500 a(n) = phi(3^n-1), where phi is Euler's totient function (A000010).

Original entry on oeis.org

1, 4, 12, 32, 110, 288, 1092, 2560, 9072, 26400, 84700, 165888, 797160, 2384928, 6019200, 15728640, 64533700, 141087744, 580765248, 1246080000, 4823425152, 14758128000, 46070066188, 85996339200, 385087175000, 1270928131200, 3474144608256, 8810420097024

Offset: 1

Seiichi Manyama, Nov 22 2017

nonn

Max Alekseyev, Table of n, a(n) for n = 1..690
Eric Weisstein's World of Mathematics, Totient Function
Wikipedia, Euler's totient function

Cf. A000010, A024023, A027385.

phi(k^n-1): A053287 (k=2), this sequence (k=3), A295501 (k=4), A295502 (k=5), A366623 (k=6), A366635 (k=7), A366654 (k=8), A366663 (k=9), A295503 (k=10), A366685 (k=11), A366711 (k=12).

EulerPhi[3^Range[30] - 1] (* Paolo Xausa, Jun 18 2024 *)

PARI
```
{a(n) = eulerphi(3^n-1)}
```

a(n) = n*A027385(n).

a(n) = A000010(A024023(n)). - Michel Marcus, Jun 18 2024

A192507 Number of conjugacy classes of primitive elements in GF(3^n) which have trace 0.

Original entry on oeis.org

0, 0, 1, 2, 7, 14, 52, 104, 333, 870, 2571, 4590, 20440, 56736, 133782, 327558, 1265391, 2612694, 10188836, 20769420, 76562106

Offset: 1

Joerg Arndt, Jul 03 2011

Also number of primitive polynomials of degree n over GF(3) whose second-highest coefficient is 0.

Cf. A152049 (GF(2^n)), A192507 (GF(5^n)), A192509 (GF(7^n)), A192510 (GF(11^n)), A192511 (GF(13^n)).

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

p := 3;
a := function(n)
    local q, k, cnt, x;
    q:=p^n;  k:=GF(p, n);  cnt:=0;
    for x in k do
        if Trace(k, GF(p), x)=0*Z(p) and Order(x)=q-1 then
            cnt := cnt+1;
        fi;
    od;
    return cnt/n;
end;
for n in [1..16] do  Print (a(n), ", ");  od;

# much more efficient
p=3; # choose characteristic
for n in range(1,66):
    F = GF(p^n, 'x')
    g = F.multiplicative_generator() # generator
    vt = vector(ZZ,p) # stats: trace
    m = p^n - 1 # size of multiplicative group
    # Compute all irreducible polynomials via Lyndon words:
    for w in LyndonWords(p,n): # digits of Lyndon words range form 1,..,p
        e = sum( (w[j]-1) * p^j for j in range(0,n) )
        if gcd(m, e) == 1: # primitive elements only
            f = g^e
            t = f.trace().lift(); # trace (over ZZ)
            vt[t] += 1
    print(vt[0]) # choose index 0,1,..,p-1 for different traces
# Joerg Arndt, Oct 03 2012

a(n) = A192212(n) / n.

Added terms >=2571, Joerg Arndt, Oct 03 2012

a(18)-a(21) from Robin Visser, Apr 26 2024

A295496 a(n) = phi(6^n-1)/n, where phi is Euler's totient function (A000010).

Original entry on oeis.org

4, 12, 56, 216, 1240, 5040, 31992, 139968, 828576, 3720000, 25238048, 104509440, 803499840, 3687014016, 24373440000, 110630707200, 790546192128, 3463116249600, 25522921047520, 108957312000000, 816244048599840, 3924124012353600, 26682733370563200

Offset: 1

Seiichi Manyama, Nov 22 2017

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..100
Eric Weisstein's World of Mathematics, Totient Function.
Wikipedia, Euler's totient function.

Column k=6 of A369291.

phi(k^n-1)/n: A011260 (k=2), A027385 (k=3), A027695 (k=4), A027741 (k=5), this sequence (k=6), A027743 (k=7), A027744 (k=8), A027745 (k=9), A295497 (k=10), A319166 (k=11).

Array[EulerPhi[6^# - 1]/# &, 25] (* Paolo Xausa, Jun 17 2024 *)

PARI
```
{a(n) = eulerphi(6^n-1)/n}
```

A295497 a(n) = phi(10^n-1)/n, where phi is Euler's totient function (A000010).

Original entry on oeis.org

6, 30, 216, 1500, 12960, 77760, 948192, 7344000, 72071856, 589032000, 6060314304, 38491200000, 496775732544, 4309959326400, 40676940288000, 345599944704000, 3921566733817776, 24555273410096640, 350877192982456140, 2915072245440000000

Offset: 1

Seiichi Manyama, Nov 22 2017

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..50
Eric Weisstein's World of Mathematics, Totient Function.
Wikipedia, Euler's totient function.

Column k=10 of A369291.

phi(k^n-1)/n: A011260 (k=2), A027385 (k=3), A027695 (k=4), A027741 (k=5), A295496 (k=6), A027743 (k=7), A027744 (k=8), A027745 (k=9), this sequence (k=10), A319166 (k=11).

Array[EulerPhi[10^# - 1]/# &, 25] (* Paolo Xausa, Jun 17 2024 *)

PARI
```
{a(n) = eulerphi(10^n-1)/n}
```

A319166 Number of primitive polynomials of degree n over GF(11).

Original entry on oeis.org

4, 16, 144, 960, 12880, 62208, 1087632, 7027200, 85098816, 691398400, 10374307328, 49985372160, 1061265441600, 7064952935040, 90426613939200, 708867057254400, 11892871258806912, 65078340559220736, 1287559798913990448, 8819554320783360000, 111715065087913437696

Offset: 1

Seiichi Manyama, Sep 12 2018

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..50
Eric Weisstein's World of Mathematics, Totient Function.
Wikipedia, Euler's totient function.

Column k=11 of A369291.
phi(k^n-1)/n: A011260 (k=2), A027385 (k=3), A027695 (k=4), A027741 (k=5), A295496 (k=6), A027743 (k=7), A027744 (k=8), A027745 (k=9), A295497 (k=10), this sequence (k=11).
Cf. A000010.

Array[EulerPhi[11^# - 1]/# &, 25] (* Paolo Xausa, Jun 17 2024 *)

PARI
```
{a(n) = eulerphi(11^n-1)/n}
```

a(n) = phi(11^n - 1)/n where phi is A000010.

A158502 Array T(n,k) read by antidiagonals: number of primitive polynomials of degree k over GF(prime(n)).

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 2, 4, 4, 2, 4, 8, 20, 8, 6, 4, 16, 36, 48, 22, 6, 8, 24, 144, 160, 280, 48, 18, 6, 48, 240, 960, 1120, 720, 156, 16, 10, 48, 816, 1536, 12880, 6048, 5580, 320, 48, 12, 80, 756, 5376, 24752, 62208, 37856, 14976, 1008, 60, 8, 96, 1560, 8640, 141984, 224640, 1087632, 192000, 99360

Offset: 1

R. J. Mathar, Aug 29 2011

			The array starts in row n=1 with columns k>=1 as
1, 1,  2,     2,     6,      6,     18,     16,      48,       60,  A011260
1, 2,  4,     8,    22,     48,    156,    320,    1008,     2640,  A027385
2, 4,  20,   48,   280,    720,   5580,  14976,   99360,   291200,  A027741
2, 8,  36,  160,  1120,   6048,  37856, 192000, 1376352,  8512000,  A027743
4,16, 144,  960, 12880,  62208,1087632,7027200,85098816,691398400,  A319166
4,24, 240, 1536, 24752, 224640,2988024,21934080

Vincenzo Librandi, Rows n = 1..50, flattened

Cf. A000010, A000040.

A := proc(n,k) local p ; p := ithprime(n) ; if k = 0 then 1; else numtheory[phi](p^k-1)/k ; end if;end proc:

t[n_, k_] := If[k == 0, 1, p = Prime[n]; EulerPhi[p^k - 1]/k]; Flatten[ Table[t[n - k + 1, k], {n, 1, 11}, {k, 1, n}]] (* Jean-François Alcover, Jun 04 2012, after Maple *)

T(n,k) = A000010(p^k-1)/k = A369291(k, p) with p=A000040(n).

A163303 a(n) = n^3 + 73*n^2 + n + 67.

Original entry on oeis.org

67, 142, 369, 754, 1303, 2022, 2917, 3994, 5259, 6718, 8377, 10242, 12319, 14614, 17133, 19882, 22867, 26094, 29569, 33298, 37287, 41542, 46069, 50874, 55963, 61342, 67017, 72994, 79279, 85878, 92797, 100042, 107619, 115534, 123793, 132402

Offset: 0

Vincenzo Librandi, Jul 24 2009, Jul 25 2009

Sequences generated by primitive polynomial J(p)=J(1031), for k=3.
Comment (entirely taken from Cugiani's text - see References) from Vincenzo Librandi , Aug 23 2011: (Start)
This deals with primitive polynomials in GF_k(p). There are p^k monic k-th order polynomials J(p) = x^k + a(k-1)*x^(k-1) + ... + a(0), because there are k independent coefficients a(.), each restricted modulo the prime p. phi(p^k-1)/k of these polynomials are primitive, where phi=A000010. [Example for p=7 and k=2: phi(7^2-1)/2 =  phi(48)/2 = 16/2=8. See A011260 for p=2, A027385 for p=3, A027741 for p=5 etc.] Of these sets of primitive polynomials we select with p=1031 the polynomial x^3+73*x^2+x+67 for k=3 in A163303 and x^4+984*x^3+90*x^2+394-x+858 for k=4 in A163304 by the following criteria (This could be extended to k=5, 6,...): Let r = (p^k -1)/(p-1). We demand (see Theorem 1 in Hansen-Mullen)
  i) (-1)^k a(0) is a primitive element of J(p).
  ii) The remainder of the division of x^r through the polynomial equals (-1)^k a(0).
  iii) The remainder of the division of x^(r/q) through the polynomial must have positive degree for each prime divisor q|r.
(End)

Marco Cugiani, Metodi numerico statistici (Collezione di Matematica applicata n.7), UTET Torino, 1980, pp. 78-84

Vincenzo Librandi, Table of n, a(n) for n = 0..10000
Tom Hansen, G. L. Mullen, Primitive Polynomials over finite fields, Math. Comp. 59 (200) (1992) 639
Sean E. O'Connor, Computing primitive Polynomials - Theory and Algorithm
Eric Weisstein, MathWorld: Primitive Polynomial
Wikipedia, Primitive Polynomial
Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Cf. A163304.

Magma
```
[n^3+73*n^2+n+67: n in [0..40]];
```

I:=[67,142,369,754]; [n le 4 select I[n] else 4*Self(n-1)-6*Self(n-2)+4*Self(n-3)-Self(n-4): n in [1..60]]; // Vincenzo Librandi, Sep 13 2015

Table[n^3 + 73 n^2 + n + 67, {n, 0, 60}] (* or *) LinearRecurrence[{4, -6, 4, -1}, {67, 142, 369, 754}, 50] (* Vincenzo Librandi, Sep 13 2015 *)

first(m)=vector(m,i,i--;i^3 + 73*i^2 + i + 67) \\ Anders Hellström, Sep 13 2015

G.f.: ( 67-126*x+203*x^2-138*x^3 ) / (x-1)^4 . - R. J. Mathar, Aug 21 2011
a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4). - Vincenzo Librandi, Sep 13 2015
E.g.f: (67 + 75*x + 76*x^2 + x^3)*exp(x). - G. C. Greubel, Dec 18 2016

A163304 a(n) = n^4 + 984n^3 + 902n^2 + 394*n + 858.

Original entry on oeis.org

858, 3139, 13142, 36807, 80098, 149003, 249534, 387727, 569642, 801363, 1088998, 1438679, 1856562, 2348827, 2921678, 3581343, 4334074, 5186147, 6143862, 7213543, 8401538, 9714219, 11157982, 12739247, 14464458, 16340083, 18372614, 20568567, 22934482, 25476923

Offset: 0

Vincenzo Librandi, Jul 24 2009

Comment (entirely taken from Cugiani's text - see References) from Vincenco Librandi, Aug 23 2011: (Start)
This deals with primitive polynomials in GF_k(p). There are p^k monic k-th order polynomials J(p) = x^k + a(k-1)*x^(k-1) + ... + a(0), because there are k independent coefficients a(.), each restricted modulo the prime p. phi(p^k-1)/k of these polynomials are primitive, where phi=A000010. [Example for p=7 and k=2: phi(7^2-1)/2 =  phi(48)/2 = 16/2=8. See A011260 for p=2, A027385 for p=3, A027741 for p=5 etc.] Of these sets of primitive polynomials we select with p=1031 the polynomial x^3+73*x^2+x+67 for k=3 in A163303 and x^4+984*x^3+90*x^2+394-x+858 for k=4 in A163304 by the following criteria (This could be extended to k=5, 6,...): Let r = (p^k -1)/(p-1). We demand (see Theorem 1 in Hansen-Mullen)
  i) (-1)^k a(0) is a primitive element of J(p).
  ii) The remainder of the division of x^r through the polynomial equals (-1)^k a(0).
  iii) The remainder of the division of x^(r/q) through the polynomial must have positive degree for each prime divisor q|r.
(End)

Marco Cugiani, Metodi numerico statistici (Collezione di Matematica applicata n.7), UTET Torino, 1980, pp.78-84

Vincenzo Librandi, Table of n, a(n) for n = 0..10000
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Cf. A163303.

[n^4+984*n^3+902*n^2+394*n+858: n in [0..30]]; // Vincenzo Librandi, Aug 17 2011

Table[n^4+984n^3+902n^2+394n+858,{n,0,30}] (* Harvey P. Dale, Aug 16 2011 *)

a(n) = n^4+984*n^3+902*n^2+394*n+858 \\ Charles R Greathouse IV, Aug 17 2011

G.f.: (858-1151*x+6027*x^2-6093*x^3+383*x^4)/(1-x)^5. - Bruno Berselli, Aug 24 2011
From G. C. Greubel, Dec 18 2016: (Start)
a(n) = 5*a(n-) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5).
E.g.f.: (858 + 2281*x + 3861*x^2 + 990*x^3 + x^4)*exp(x). (End)

Corrected and extended by Harvey P. Dale, Aug 16 2011

Offset changed from 1 to 0 by Vincenzo Librandi, Aug 17 2011

A319183 a(n) = phi(n^n - 1)/n where phi is A000010.

Original entry on oeis.org

1, 4, 32, 280, 5040, 37856, 829440, 15676416, 589032000, 10374307328, 388566097920, 7619466454080, 390751784579520, 11138729990400000, 575561351791902720, 24328359845627701248, 1640651748984970444800, 34709116765970413844280, 2459108342476800000000000

Offset: 2

Seiichi Manyama, Sep 12 2018

nonn

Main diagonal of the array T(n,k) = phi(n^k-1)/k for n > 1 and k > 1, which starts
    1,   2,   2,    6,     6,     18,     16, ... A011260
    2,   4,   8,   22,    48,    156,    320, ... A027385
    4,  12,  32,  120,   288,   1512,   4096, ... A027695
    4,  20,  48,  280,   720,   5580,  14976, ... A027741
   12,  56, 216, 1240,  5040,  31992, 139968, ... A295496
    8,  36, 160, 1120,  6048,  37856, 192000, ... A027743
   18, 144, 432, 5400, 23328, 254016, 829440, ... A027744

Seiichi Manyama, Table of n, a(n) for n = 2..50
Eric Weisstein's World of Mathematics, Totient Function.
Wikipedia, Euler's totient function.

A diagonal of A369291.

Cf. A000010, A006486, A027385.

Table[EulerPhi[n^n-1]/n,{n,20}] (* Harvey P. Dale, Aug 04 2020 *)

PARI
```
{a(n) = eulerphi(n^n-1)/n}
```

cp's OEIS Frontend

A369291 Array read by antidiagonals: T(n,k) = phi(k^n-1)/n, where phi is Euler's totient function (A000010), n >= 1, k >= 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A295500 a(n) = phi(3^n-1), where phi is Euler's totient function (A000010).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A192507 Number of conjugacy classes of primitive elements in GF(3^n) which have trace 0.

Views

Author

Keywords

Comments

Crossrefs

Programs

GAP

Sage

Formula

Extensions

A295496 a(n) = phi(6^n-1)/n, where phi is Euler's totient function (A000010).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A295497 a(n) = phi(10^n-1)/n, where phi is Euler's totient function (A000010).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A319166 Number of primitive polynomials of degree n over GF(11).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A158502 Array T(n,k) read by antidiagonals: number of primitive polynomials of degree k over GF(prime(n)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A163303 a(n) = n^3 + 73*n^2 + n + 67.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A163304 a(n) = n^4 + 984n^3 + 902n^2 + 394*n + 858.