What's significant about the number choice 1000000007?

Great find indeed. There were plenty of well thought-out challenges and I just wish I had more time to dedicate to them.

One curious question, though… (Google has failed me)
For many of the challenges, there was a note to output the results modulo 1000000007. (to prevent overflow, apparently) What I don’t understand is:
What does that even accomplish? I would reason that is no better an answer than % 1000000007.
What’s significant about the number choice 1000000007?

10 Likes

It is the first 10-digital prime number. In some of such problems to compute the result modular inverses are needed and it helps very much that this number is prime. Also this number should be large enough since otherwise modular inverses technique may fail in some situations.

In fact any prime number less then 2^30 will be fine in order to prevent possible overflows. But this one can be easily written as 10^9+7.

This reasoning almost uniquely determined this number :slight_smile:

31 Likes

i didnt get you anton_lunyov !
what do you mean by modular inverses

Hi @pc9292, read more here - http://discuss.codechef.com/questions/1440/algorithm-to-find-inverse-modulo-m hope it helps.

do fibonacci terms have any relation with modular inverses?

inverse is used in “divide” operation, you do not need that operation for Fibonacci numbers, so no, these two topics are not directly related…

There’s one more interesting fact about this number -

1000000007 is also an emirp. That is, its reversal is also a prime. In fact, this number is largest emirp of the form 10…07

Ref: https://primes.utm.edu/curios/page.php/1000000007.html

1 Like