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 N i N_i from 0 0 to 999 999
  • At each round, everyone replaces their number N i N_i with N i N'_i where N i 1000 ( m o d N i ) N'_i \equiv 1000 \pmod {N_i} and 0 N i < N i 0 \leq N'_i < N_i
  • A player loses when they reach 0 0 (i.e. when 1000 ( m o d N i ) 0 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 0 to 999 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 23 , on the first round you would replace 23 23 with 1000 ( m o d 23 ) = 11 1000 \pmod {23} = 11 , on the second round you would replace 11 11 with 1000 ( m o d 11 ) = 10 1000 \pmod {11} = 10 , and on the third round you would replace 10 10 with 1000 ( m o d 10 ) = 0 1000 \pmod {10} = 0 , so 23 23 would last 3 3 rounds.


The answer is 649.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

6 solutions

Ahaan Rungta
Dec 22, 2013

Done by Sreejato Bhattacharya and I:

 def numberofrounds (n): 
  count=0
  value= n
  while value>0:
    value= 1000%value
    count+=1
  return count

m = max([numberofrounds(n) for n in range (500, 750)])
for n in range (500, 750): 
  if numberofrounds(n) == m: 
    print n

Do you realise that this is number theory, not computer science?

minimario minimario - 7 years, 5 months ago

Log in to reply

Logan Dymod, the creator of this problem, intended to make this a CS problem. In fact, he claims there is no number theoretic solution.

Ahaan Rungta - 7 years, 5 months ago

Log in to reply

I am going to kill him for making me work a lot on this problem.I even proved that no integer exists for which there would be an infinite number of rounds.

Rahul Saha - 7 years, 5 months ago

Most of the Number Theory problems can be solved using CS. So it doesn't really matter.

Aryan Gaikwad - 6 years, 2 months ago
Aryan Gaikwad
Mar 6, 2015

Java solution -

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public static void main(String args[]){
    int n = 0, re = 0, cur = 0, gre = 0;        
    for(int i = 1; i <= 999; i++){
        cur = i;
        while(1000 % cur != 0){
            cur = 1000 % cur;
            re++;
        }
        if(re > gre){
            gre = re;
            n = i;
        }
        re = 0;
    }
    System.out.println(n);
}

Execution time - 0.000288341 secs

Santanu Banerjee
Dec 16, 2013

I did using the following program ::::

import java.io.*;

import java.math.*;

public class TheLongestSequenceOfMods

{

long j=0;

public static void main(String args[])

{

    TheLongestSequenceOfMods obj=new TheLongestSequenceOfMods();

    long i=0,j=0,m=0,n=0;

    for(i=1;i<1000;i++)

    {

m=obj.fun(i,0);

        if(m>j)

        {

            j=m;

            n=i;

        }

    }

    System.out.println(n);

}

long fun(long h,long k)

{

    j=1000%h;

    ++k;

    if(j==0)

        return k;

    else

        return fun(j,k);

}

}

OUTPUT :: 649

Although is like cheating, I used this program in C to solve the problem. I hope to find a solution better than mine.

int n, numero, resto, contatore, volte_max, unico;
n=1000;
numero=1;
volte_max=0;
while(numero<1000)
{
    resto=numero;
    contatore=0;
    while(resto!=0)
    {
        resto=n%resto;
        contatore++;
    }
    if(contatore>volte_max)
    {
        volte_max=contatore;
        unico=numero;
    }
    numero++;
}
printf("Il max è %d e compare %d volte\n",unico, volte_max);
return EXIT_SUCCESS;

unico=649, volte_max=9.

Alex Letizia - 7 years, 5 months ago

There has to be a purely mathematical solution.Since I couldn't solve the whole problem,I will just say what I did,lest anyone should benefit from my works.

1)I found out the number of remainders after dividing 1000 by positive integers smaller than it.The exact number,I believe is 500.

2)I proved that no integer exists such that there would be an infinite number of rounds.We can use induction.

That's all I did..It's not much,but perhaps it will help.

Rahul Saha - 7 years, 5 months ago
Chuck Jerian
Mar 19, 2015

I wrote something similar to David Holcer that worked: Wrote a loop to do max, I guess I need to learn more python to not loop to find the max. I was thinking of remembering the old mod values, but calculating mod is just as fast I think as looking it up so dynamic programming wouldn't help much here.

#brute force method
ra = [None]*1000
ra[0]=0
for i in range(1,1000):
    rounds = 0
    r = 1000 % i
    while (r):
        r = 1000 % r
        rounds +=1

    ra[i] = rounds
    #print (i, rounds)
i = 0
maxi = -1
maxrnd = -1
for j in ra:
    if j > maxrnd:
        maxi = i
        maxrnd = j
    i += 1
print(maxi,maxrnd)
David Holcer
Mar 16, 2015
1
2
3
4
5
6
7
8
rounds=[]
for i in range(1,1000):
    round=0
    while (1000%i)!=0:
        i=1000%i
        round+=1
    rounds.append(round)
print rounds.index(max(rounds))+1

I love the troll "from 0 to 999", you cant do 1000 mod 0, it should be "from 0 to 1000 both not inclusive."

Haskell:

1
2
3
4
5
6
7
chain :: Integral a => a -> [a]
chain 0 = [0]
chain n = n: chain (1000 `mod` n)

f a b = if (length(chain a)) > (length(chain b)) then a else b

main = print $ foldl f 1 [1..1000]

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...