# 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.

×