login
Number of primitive polynomials of degree n over GF(2).
10

%I #30 Sep 23 2020 15:01:49

%S 2,1,2,2,6,6,18,16,48,60,176,144,630,756,1800,2048,7710,7776,27594,

%T 24000,84672,120032,356960,276480,1296000,1719900,4202496,4741632,

%U 18407808,17820000,69273666,67108864,211016256,336849900,929275200,725594112,3697909056

%N Number of primitive polynomials of degree n over GF(2).

%C The initial 2 should really be a 1. See A011260 for official version.

%D E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, NY, 1968, p. 84.

%D T. L. Booth, An analytical representation of signals in sequential networks, pp. 301-3240 of Proceedings of the Symposium on Mathematical Theory of Automata. New York, N.Y., 1962. Microwave Research Institute Symposia Series, Vol. XII; Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, N.Y. 1963 xix+640 pp. See p. 303.

%D W. W. Peterson and E. J. Weldon, Jr., Error-Correcting Codes. MIT Press, Cambridge, MA, 2nd edition, 1972, p. 476.

%D M. P. Ristenblatt, Pseudo-Random Binary Coded Waveforms, pp. 274-314 of R. S. Berkowitz, editor, Modern Radar, Wiley, NY, 1965; see p. 296.

%H David W. Wilson, <a href="/A000020/b000020.txt">Table of n, a(n) for n = 1..400</a>

%H R. Church, <a href="http://www.jstor.org/stable/1968675">Tables of irreducible polynomials for the first four prime moduli</a>, Annals Math., 36 (1935), 198-209.

%H S. V, Duzhin and D. V. Pasechnik, <a href="ftp://pdmi.ras.ru/pub/publicat/znsl/v421/p081.pdf">Groups acting on necklaces and sandpile groups</a>, 2014. See p. 92. - _N. J. A. Sloane_, Jun 30 2014

%t Table[If[n==1,2,EulerPhi[2^n-1]/n],{n,1,50}] (* _Vladimir Joseph Stephan Orlovsky_, Jan 24 2012 *)

%o (PARI) a(n)=if(n==1,2,eulerphi(2^n-1)/n) \\ Hauke Worpel (thebigh(AT)outgun.com), Jun 10 2008

%Y Cf. A058947, A011260 (with initial term 1).

%K nonn

%O 1,1

%A _N. J. A. Sloane_