IBM Research | Ponder This | October 2004 challenges
Skip to main content

Ponder This

October 2004

<<September October November>>

Ponder This Challenge:

Puzzle for October 2004.

This month's puzzle is from IQSTAR.
Solutions to one or several parts are okay, but should be accompanied by a proof that your list contains all the possible values and only those, and should be original.

Part 1:
A polynomial is called "primitive" if all the coefficients are integers with their greatest common divisor (GCD) equal to 1. Let P(x) be a primitive polynomial of degree m in x. V(P) is the set of all P(n) where n takes all the integral values. G(P) is the GCD of the elements of V(P). For fixed m, what values can G(P) have?

Part 2:
Let P(x,y,z) be a primitive polynomial of total degree m in (x,y,z). (It involves monomials (x^i*y^j*z^k) where i,j,k are nonnegative integers with i+j+k bounded by m.) V(P) is the set of all P(n1,n2,n3) where n1,n2,n3 take on all the integral values. G(P) is the GCD of the elements of V(P). For fixed m, what values can G(P) have?

Part 3:

What if P(x,y,z) is of degree m separately in each variable? (For each nonzero coefficient, i,j,k are each bounded by m.)

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the

If you have any problems you think we might enjoy, please send them in. All replies should be sent to:


Challenge: 10/01/2004 @ 9:00 AM ET
Solution: 11/01/2004 @ 8:30 AM ET
List Updated: 10/01/2004 @ 9:00 AM ET

People who answered correctly:

Dan Dima 1,2,3 (10.01.2004 @11:29:07 AM EDT)
Mark J. Tilford 1,2,3 (10.02.2004 @12:17:01 PM EDT)
Luke Pebody 1,2,3 (10.02.2004 @02:12:42 PM EDT)
Jose H. Nieto 1,2,3 (10.02.2004 @09:28:22 PM EDT)
Patrick J. LoPresti 1,2,3 (10.02.2004 @08:46:41 AM EDT)
Daniel Bitin 1,2,3 (10.04.2004 @06:16:06 PM EDT)
Dharmadeep Muppalla 1,2,3 (10.06.2004 @08:07:43 AM EDT)
Libin Shen 1,2,3 (10.06.2004 @02:54:46 PM EDT)
Michael Brand 1,2,3 (10.06.2004 @10:08:27 PM EDT)
Vincent Vermaut 1,2,3 (10.07.2004 @02:35:54 AM EDT)
Raicho Tchalkov 1 (10.07.2004 @05:17:21 PM EDT)
Amit Sinha 1,2,3 (10.08.2004 @10:40:41 AM EDT)
Wolfgang Kais 1,2,3 (10.11.2004 @10:07:45 AM EDT)
Hagen von Eitzen 1,2,3 (10.12.2004 @12:30:21 PM EDT)
Stephen Lesko 1,2,3 (10.25.2004 @03:14:01 PM EDT)
Vineet Kumar D 1 (10.26.2004 @05:09:22 AM EDT)
Satish Vedantam 1,3 (10.29.2004 @09:44:10 PM EDT)
Divyesh Dixit 1,3 (10.30.2004 @04:29:16 PM EDT)

Attention: If your name is posted here and you wish it removed please send email to the