404 Notes on Explorationsthen y belongs to S if and only if y is a positive value assumed by the
polynomial g(y,x). A survey article on Diophantine decision problems by
Julia Robinson appears in W.J. LeVeque (ed.), Studies in number theory,- Studies in Mathematics 6 Math. Assoc. of America, 1969.
The following references are also relevant: M. Davis, H. Putman & J.
Robinson, The decision problem for exponential diophantine equations,
Ann. Math. (2) 74 (1961), 425-436, MR24 # A3061; and Ju. V. Mati-
jasevic, The Diophantineness of enumerable sets, Dokl. Akad. Nauk SSSR
191 (1970), 279-282 = Soviet Math. Dokl. 11 (1970), 354-358, MR41 #
- E.15. Since a polynomial is irreducible along with every positive multiple
of itself, it is enough to look at manic polynomials; the total number of
irreducibles will be p - 1 times the number of manic irreducibles. Clearly,
there are p manic irreducibles of degree 1: t, t + 1, t + 2,... ,t + (p - 1).
To determine the number of irreducibles of higher degree, subtract from
the total number of polynomials of that degree the number obtainable as
products of polynomials of lower degree. For example, there are
P2- (P+ (;)) =(P2-P)/2manic irreducible quadratics. For p = 2, the only possibility is t2 + t + 1,
while for p = 3, there are t2 + 1, t2 + t + 2, t2 + 2t + 2.
There are (p3-p)/3 manic irreducible cubits. For p = 2, they are t3+t+ 1
and t3 + t2 + 1. There are p(p - 1)2(p + 8)/8 manic irreducible quartics.
See Markus Nijmeijer & Mike Staring, A formula that produces all, and
nothing but, irreducible polynomials in Z,[x], Mathematics Magazine 61
(1988), 41-44.
E.16. A thorough discussion of this problem can be found in Donald E.
Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algo-
rithms, (Addison Wesley) pages 441-446.
E.17. Horner’s table for the expansion of tn in terms oft - 1 is1 0 0 0 0 .*. 0 0 0 0
1 1 1 1 ... 1 1 1 11 11 1 1 *** 1 1 1 1
1 2 3 4 .” n-3 n-2 n-l1 2 3 4 5 ..a n-2 n-l n
1 3 6 10 ...(^1 3 6 10 15) ...
...