22

In many programming problems (e.g. some Project Euler problems) we are asked to report the answer as the remainder left after dividing the answer by 1,000,000,007.

Why not any other number?

Edit: 2 years later, here's what I know: the number is a big prime, and any answer to such a question is so large that it makes sense to report a remainder instead (as the number may be too large for a native datatype to handle).

Soham Chowdhury
  • 2,125
  • 2
  • 18
  • 29

1 Answers1

23

Let me play a telepathist. 1000...7 are prime numbers and 1000000007 is the biggest one that fits in 32-bit integer. Since prime numbers are used to calculate hash (by finding the remainder of the division by prime), 1000000007 is good for calculating 32-bit hash.

Community
  • 1
  • 1
Dmitry Fedorkov
  • 4,301
  • 1
  • 21
  • 30
  • What is the purpose of this operation, though? – Soham Chowdhury Sep 25 '12 at 08:10
  • @soham-chowdhury, hash function has many purposees. See http://en.wikipedia.org/wiki/Hash_function – Dmitry Fedorkov Sep 25 '12 at 08:16
  • 6
    It's by no means the largest prime that would fit in a signed 32-bit integer! That would start with a `2`, after all. It is however the smallest ten-digit prime. – AakashM Sep 25 '12 at 15:04
  • 1
    @AakashM, surely. Actually the largest is 2^31-1 (for signed int). Any suggestions for use of the smallest 10-digit prime number? P. S. I demand for "telepathist" badge! :) – Dmitry Fedorkov Sep 25 '12 at 15:11
  • 2
    I think competitions might use it for a combination of reasons: Primes are more natural candidates for doing modular arithmetic; using a large prime forces the codes to *think*; the first prime with `n` digits is an obvious choice for 'a prime with `n` digits' :) – AakashM Sep 25 '12 at 15:23