The Longest Sequence of Mods

Computer Science Level 4

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 \(N_i\) from \(0\) to \(999\)
  • At each round, everyone replaces their number \(N_i\) with \(N'_i\) where \(N'_i \equiv 1000 \pmod {N_i}\) and \(0 \leq N'_i < N_i\)
  • A player loses when they reach \(0\) (i.e. when \(1000 \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 \(0\) to \(999\) that lasts the highest number of rounds. What integer do you choose?

Details and assumptions

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


Problem Loading...

Note Loading...

Set Loading...