A011260 -id:A011260 - cp's OEIS frontend

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

0, 0, 1, 1, 3, 2, 9, 9, 23, 29, 89, 72, 315, 375, 899, 1031, 3855, 3886, 13797, 12000, 42328, 59989, 178529, 138256, 647969, 859841, 2101143, 2370917, 9204061, 8911060, 34636833, 33556537, 105508927, 168423669, 464635937

Offset: 1

David A. Madore, Nov 21 2008

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

Always less than A011260 (and exactly one half of it when 2^n-1 is prime).

			a(3)=1 because of the two primitive degree 3 polynomials over GF(2), namely t^3+t+1 and t^3+t^2+1, only the former has a zero next-to-highest coefficient.
Similarly, a(13)=315, because of half (4096) of the 8192 elements of GF(2^13) have trace 0 and all except 0 (since 1 has trace 1) are primitive, so there are 4095/13=315 conjugacy classes of primitive elements of trace 0.

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

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

a(n) = A192211(n)/n. [Joerg Arndt, Jul 03 2011]

More terms (13797...8911060) by Joerg Arndt, Jun 26 2011.

More terms (34636833...464635937) by Joerg Arndt, Jul 03 2011.

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.

A056742 a(n) = phi(2^n - 1)/2.

Original entry on oeis.org

1, 3, 4, 15, 18, 63, 64, 216, 300, 968, 864, 4095, 5292, 13500, 16384, 65535, 69984, 262143, 240000, 889056, 1320352, 4105040, 3317760, 16200000, 22358700, 56733696, 66382848, 266913216, 267300000, 1073741823, 1073741824

Offset: 2

Robert G. Wilson v, Aug 14 2000

nonn

Amiram Eldar, Table of n, a(n) for n = 2..1206

Cf. A000010, A000225, A011260, A053287.

Table[EulerPhi[(2^n - 1)]/2, {n, 2, 40}]

a(n) = eulerphi(2^n - 1)/2; \\ Amiram Eldar, Jun 09 2024

a(n) = A000010(A000225(n))/2 = A053287(n)/2. - Amiram Eldar, Jun 09 2024

A069925 a(n) = phi(2^n+1)/(2*n).

Original entry on oeis.org

1, 1, 1, 2, 2, 4, 6, 16, 18, 40, 62, 160, 210, 448, 660, 2048, 2570, 5184, 9198, 24672, 32508, 76032, 121574, 344064, 405000, 1005888, 1569780, 4511520, 6066336, 12672000, 23091222, 67004160, 85342752, 200422656, 289531200, 892477440

Offset: 1

Benoit Cloitre, Apr 25 2002

Number of primitive self-reciprocal polynomials of degree 2*n over GF(2). - Joerg Arndt, Jul 04 2012

Amiram Eldar, Table of n, a(n) for n = 1..1090
Joerg Arndt, Matters Computational (The Fxtbook), section 40.8 "Self-reciprocal polynomials", pp. 846-848.
Helmut Meyn and Werner Götz, Self-reciprocal Polynomials Over Finite Fields, Séminaire Lotharingien de Combinatoire, B21d, pp. 82-90, 1989.

Cf. A011260 (degree-n primitive polynomials).
Cf. A000048 (degree-2*n irreducible self-reciprocal polynomials).
Cf. A000010, A000051, A053285.

Table[EulerPhi[2^n+1]/(2n),{n,50}] (* Harvey P. Dale, Nov 15 2011 *)

a(n) = eulerphi(2^n+1)/(2*n); /* Joerg Arndt, Jul 04 2012 */

a(n) = phi(2^n+1)/(2*n).

a(n) = A053285(n)/(2*n). - Amiram Eldar, Jun 02 2022

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

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

GAP

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

A056742 a(n) = phi(2^n - 1)/2.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A069925 a(n) = phi(2^n+1)/(2*n).

Views

Author

Keywords

Comments

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.