The Longest Sequence of Mods

You and some friends journey to the convenience store to buy some Slurpees. While you are enjoying your delicious treat you suddenly realize that the total bill for all of the Slurpees comes out to be a whopping $1,000. Being the clever mathematician you are, you suggest that rather than splitting the bill evenly, you guys will play a game to decide who pay for the entire bill. The rules are:

  • Everyone picks a different integer NiN_i from 00 to 999999
  • At each round, everyone replaces their number NiN_i with NiN'_i where Ni1000(modNi)N'_i \equiv 1000 \pmod {N_i} and 0Ni<Ni0 \leq N'_i < N_i
  • A player loses when they reach 00 (i.e. when 1000(modNi)01000 \pmod {N_i} \equiv 0)

Since your mother would get very angry if she found out that you had to pay the $1,000 bill, you decide to choose the unique integer from 00 to 999999 that lasts the highest number of rounds. What integer do you choose?

Details and assumptions

As an explicit example, f you chose the number 2323, on the first round you would replace 2323 with 1000(mod23)=111000 \pmod {23} = 11, on the second round you would replace 1111 with 1000(mod11)=101000 \pmod {11} = 10, and on the third round you would replace 1010 with 1000(mod10)=01000 \pmod {10} = 0, so 2323 would last 33 rounds.

×

Problem Loading...

Note Loading...

Set Loading...