A Much Longer Sequence of Mods

Level pending

20 years ago, you outsmarted your friends into paying a 1000 dollar slurpee bill at the convenience store with a simple game of mods. They are still bitter about that, so they challenge you to a rematch with much higher stakes. After everyone buys their own convenience store, the total comes out to 10 million and 1 dollars. So to decide who pays, everyone plays a game with the following rules:

  • Everyone picks a different integer \(N_i\) from \(1\) to \(10,000,000\), inclusive

  • At each round, everyone replaces their number \(N_i\) with \(N'_i\), where \(N'_i \equiv {10,000,001} \pmod {N_i}\) and \(0 \leq N'_i < N_i\)

  • A player loses when they reach \(0\) (i.e. when \(10,000,000 \pmod {N_i} \equiv 0\))

Since your mother would get much angrier if she found out that you had to pay the $10,000,001 bill, you decide to choose the unique integer from \(0\) to \(10,000,000\) that lasts the highest number of rounds. What are the last 3 digits of the integer you choose?

Details and assumptions

As an explicit example, if you chose the number \(23\) , on the first round you would replace \(23\) with \(10,000,001 \pmod {23} \equiv 15\) , on the second round you would replace \(15\) with \(10,000,001 \pmod {15} \equiv 11\), and on the third round you would replace \(11\) with \(10,000,001 \pmod {11} \equiv 0\) , so \(23\) would last \(3\) rounds.


Problem Loading...

Note Loading...

Set Loading...