2731

This number is a prime.

If 2731 people are chosen at random, then the probability that at least 17 of them share the same birthday is greater than 50%. By chance, 2731 is a Wagstaff prime, i.e., a prime of the form (2^p + 1)/3. Note that (2^17 + 1)/3 is also a Wagstaff prime.