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.

The answer is 726.

1 solution

Mark Mottian
Dec 22, 2013

This is the Python programme that I wrote. It takes a bit of time before it returns an answer, but it works.

counter = 0
Max = 0
Max2 = 0

for i in xrange(1,10000001):
  a = i

  while a > 0:
    a = 10000001 % a
    counter = counter + 1

if counter > Max:
    Max = counter
    Max2 = i
    counter = 0
else:
    counter = 0

print Max2

The programme returns 6320726 (last three digits are 726) as the number that will last the highest number of rounds. If anybody has a way of optimising this programme, with regards to speed, please share your knowledge.

You are the only one to solve my problem!

Well, my script should be a lot faster than going through the entire game for each number up to $10,000,001$ . The trick is to store the length of the sequence in a dictionary so when you reach a number twice from 2 different numbers, you don't have to go through the sequence again. For example, after checking the sequence for $15$ you find that $15$ lasts for $2$ rounds. When you check $23$ , you see that your next number is $15$ , and you already found that $15$ lasts for $2$ rounds, so $23$ lasts for $2+1 = 3$ rounds. You found this number without checking the sequence for $15$ twice. Likewise, when you check $149$ , you get $15$ again so you know immediately $149$ returns $3$ .

Here's my code:

mods = {0:0}

def GenerateSequence(n,k):
    if n in mods:
        return mods[n]
    else:
        mods[n] = GenerateSequence(k%n,k)+1
        return mods[n]

def LongestSequence(k):
    for i in range(k):
        GenerateSequence(i,k)
    maxm = 0
    for key in mods:
        if mods[key] > maxm:
            maxm = mods[key]
    allmaxes = []
    for key in mods:
       if mods[key] == maxm:
            allmaxes.append(key)
    return allmaxes

print LongestSequence(10**7+1)

runs in ~ 7 seconds

Logan Dymond - 7 years, 5 months ago

Also in my script my Longest Sequence function finds the max number of rounds and then goes back and finds all numbers that last that many rounds. That's because when I was designing the problem I wasn't guaranteed to get a unique answer depending on the bound (for example, had I used $10^7$ rather than $10^7+1$ , there would have been 19 answers).

Rather than doing what I did in my script, if you knew there was a unique answer you could just keep track of the number that returned the highest sequence and overwrite it when you found a number that returned a longer sequence.

Logan Dymond - 7 years, 5 months ago

Very nice! I definitely learnt a lot from you. By the way, this problem rocked! Keep posting your fantastic problems.

Mark Mottian - 7 years, 5 months ago

A Much Longer Sequence of Mods

The answer is 726.

1 solution

0 pending reports