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

49. We have limzq(zkm + r – 1)/(zlm + r – 1) = 1 when 0 < r < m, and the limit is limzq(kmzkm – 1)/(lmzlm – 1) = k/l when r = 0. So we can pair up factors of the numerator Πnk < an(za – 1) with factors of the denominator Π0 < bk(zb – 1) when ab (modulo m).

Notes: This formula was discovered by G. Olive, AMM 72 (1965), 619. In the special case m = 2, q = –1, the second factor vanishes only when n is even and k is odd.

The formula Image holds for all n ≥ 0, but Image is not always equal to . The reason is that the second factor is zero unless ...

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