O'Reilly logo

Art of Computer Programming, Volume 4A, The: Combinatorial Algorithms, Part 1 by Donald E. Knuth

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

The first important case occurs when m is a prime number, and f is the almost linear recurrence

Image

Here the coefficients (c1, . . ., cn) must be such that

Image

is a primitive polynomial modulo m, in the sense discussed following Eq. 3.2.2–(9). The number of such polynomials is φ(mn – 1)/n, large enough to allow us to find one in which only a few of the c’s are nonzero. [This construction goes back to a pioneering paper of Willem Mantel, Nieuw Archief voor Wiskunde (2) 1 (1897), 172–184.]

For example, suppose m = 2. We can generate binary n-tuples with ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required