Modified Euclidean Algorithm

If $gcd(n_i,m_i) = n_i$ the process is immediately terminated. Now we attempt to prove that $gcd(n_i,m_i) = gcd(n_{i+1},m_{i+1})$ if $gcd(n_i,m_i) \neq n_i$ . Let $gcd(n_i,m_i) = d_i$ and $m_i = q_in_i+r_i$ where $r_i \neq 0$ . Obviously $d_i | m_{i+1} = n_i$ . Also, $r_i = m_i - q_in_i$ and thus is divisible by $d_i$ as well. Then, we have $d_i | n_i - r_i$ so $d_i | n_{i+1}$ . Thus we conclude that $gcd(n_{i+1},m_{i+1}) \geq d_i = gcd(n_i,m_i)$ . Conversely, we let $gcd(n_{i+1},m_{i+1}) = d_{i+1}$ . $n_{i+1} = r_i$ or $n_i - r_i$ . We note that if $d_{i+1} | m_{i+1} = n_i$ and $d_{i+1} | r_i$ then $d_{i+1} | n_i - r_i$ . Also if $d_{i+1} | m_{i+1} = n_i$ and $d_{i+1} | n_i - r_i$ then $d_{i+1} | r_i$ . Thus in either cases, $d_{i+1} | r_i, n_i-r_i$ . Thus we also have $d_{i+1} | m_i = q_in_i+r_i$ . Therefore we can conclude $gcd(n_i, m_i) \geq d_{i+1} = gcd(n_{i+1},m_{i+1})$ . Hence, $gcd(n_i,m_i) = gcd(n_{i+1},m_{i+1})$ .

Since 101 is prime, aside from $m_0 = 101d$ (where d = 2,3,.., 9), the rest of $101 < m_0 < 1000$ can be reduced to the form $(1, m_k)$ in k steps. From this point on, we only consider $(n_i,m_i)$ where $gcd(n_i, m_i) = 1$ .

From $(n_i,m_i)$ , we now attempt to create the smallest $m_{i-1}$ to form the smallest $(n_{i-1},m_{i-1})$ (we define this as the smallest $n_{i-1} + m_{i-1}$ ) since $n_{i-1} = m_i$ is fixed. We know that $n_{i-1} \leq \frac{1}{2}m_{i-1}$ since $n_{i-1}$ takes the smaller of $r_{i-2}$ and $n_{i-2} - r_{i-2} = m_{i-1} - r_{i-2}$ . Hence $m_{i-1} = 2n_{i-1} + j$ for some integer j. To create $(n_i,m_i)$ from $(n_{i-1}, 2n_{i-1} + j)$ , j only takes values in the form of $an_i$ or $bn_{i-1} - n_i$ (for positive integers a,b). Obviously the smallest j is then $n_i$ (since $n_i \leq m_i - n_i = n_{i-1} - n_i$ ). Smallest $(n_{i-1}, m_{i-1})$ is thus $(m_i, 2m_i + n_i)$ .

Now we let the sequence be $(n_0,m_0), (n_1,m_1),...,(n_k,m_k)$ . The smallest possible $(n_k,m_k) = (1,2)$ , and using our earlier proof, we can construct the smallest $(n_{k-1},m_{k-1}) = (2,5)$ , $(n_{k-2},m_{k-2}) = (5,12)$ , $(n_{k-3},m_{k-3}) = (12,29)$ , $(n_{k-4},m_{k-4}) = (29,70)$ , $(n_{k-5},m_{k-5}) = (70,169)$ , $(n_{k-6},m_{k-6}) = (169,408)$ . From this we see that $(101,m_0)$ takes at most 5 steps before it reaches $(1,m_k)$ . We now consider all such $(101,m_0)$ that requires 5 steps to achieve 5 steps to achieve $(1,m_5)$ .

We know that when $(n_0, m_0) = (101, 101d \pm g)$ then $(n_1,m_1) = (g, 101)$ where g = 1,2..,50 and d=1,2..,10. Every $m_0$ (that is not divisible by 101) can be uniquely expressed as $101d \pm g$ for some d and g, so we only need to consider $(g,101)$ that requires 4 steps to reach $(1,n_5)$ . From our earlier construct, we know that $29 \leq g \leq 50$ .

Consider reducing the 22 cases of $(g,101)$ to $(n_2,g)$ - we only have 8 cases where $n_2 \geq 12$ . They are (14,29), (13,38), (16,39), (19,40), (19,41), (17,42), (15,43), (13, 44). We further reduce them to $(n_3, m_3)$ and consider $n_3 \geq 5$ - they are (7,16), (8,17) and (5, 13). Considering $(n_4,m_4)$ where $n_4 \neq 1$ gives us the only 2 possibilities (2,7) and (2,5). Tracing them back to $(n_1, m_1)$ gives us $(39,101)$ and $(44,101)$ .

For g = 39 and 44, we can produce 36 of $(n_0, m_0) = (101, 101d \pm g)$ where $101 < m_0 < 1000$ , that requires 5 steps to reach $(1, n_5)$ . Also we have 8 of $m_0 = 101d$ (d=2,3,..9) that will result in the process being terminated immediately. Subtracting these 44 cases, we have 854 cases of $m_0$ that will cause the algorithm to terminate in no more than 4 steps with $n_k = 1$ .

First, there are a total of 898 numbers, from 999 to 102, +1 as it's an inclusive set. Clearly, the solution was not any multiple of 101, as that would immediately have yielded 0 as the result of m%n, ending the function immediately. This removes 8 from the solution set immediately.

In addition, all solutions from 101 to 201 would occur 9 times, with a difference of 1 every time, because (x*101+y)%101 would simply be y for all integers x and y. In other words, the total number of exceptions from 101 to 201 could simply be multiplied by 9 and added to the previously mentioned 8 exceptions for the total number of exceptions.

So, the challenge now becomes calculating the exceptions from 102 to 201, or with %101, from 1 to 100. Now, as the values approach the halfway point, the modded value subtracted from the original value will begin to exceed the modded value alone, or the min() function will return a different result. What this means is that there is a "mirror" in this group at the center of the first 101 values, at the center or 51st.

All of this should be quickly determined. The remaining values are 1 to 51. These must be the n 2 's for all of the functions. So, where s is the total number of values from 1 to 51 that satisfy the role as the n 2, there are 898-(18*s+8) solutions.

Now, min(101%x,x-101%x). The final numbers will be notably smaller than the original numbers. The maximal value for the final n value after 4 steps as the new value must be less than half of the original value, using 51 as an upper bound, would be 51\rightarrow 25\rightarrow 12\rightarrow 5. The pattern in m is similar, with 101\rightarrow 51\rightarrow 25\rightarrow 12. This follows theoretical maxima. However, the problem that makes all of these unrealistic is that the greater the value of one level past a certain point, the lesser the resulting value. As with the original Euclidean algorithm, this results in all numbers eventually reaching relative primehood. Conveniently, for values so small like 51, all fourth steps must be not only relatively prime, but also prime. Another good thing, is that by virtue of the path taken by this algorithm, third steps with such small values should also be relatively prime. By this, we can determine that the final n, n 4 , must be 2. As the number n i can never be more than half of the m_i, 2:3 is impossible.

The first value must be greater than 1/4 of 101, by extending the previous 2x rule, and 25-51 is already an awfully small range. In fact, for all of the levels, the rule extends. So, the minimum value for 51 is 12, for 12 is 3. This reestablishes new maxima with all numbers past 44 being excluded by the minimum of 12. All of this reducing should take no more than 10 minutes.

One final reduction, recognizing that values up to about 1/3 for the first are unacceptable, as they will result in numbers that either have a difference equal to a number which would result in a small mod or a difference that would be small already, where the mod would act to reduce it. This approximation is by no means generalized, but serves specifically for this scenario as exceptions are only realistic with far greater original n's. At this point, brute force for numbers between 33 and 44 is simple and looking for the values that will end in 2 will result in two, 39 and 44. 2*18+8=44. 898-44=854 total solutions.

Not the most elegant solution, but I solved it using congruences and modular math. First, any integer $k$ with the same remainder $\pmod {101}$ will take the same number of steps. In addition, since it takes the minimum of $r_i, n_i - r_i$ , we can work with $k \leq 50$ . The first 4 steps of the algorithm gives:

$(101, k) \rightarrow$

$(k, 101) \rightarrow$

$(101 \pmod k, k) \rightarrow$

$(k \pmod {101 \pmod k}, 101 \pmod k) \rightarrow$

$((101 \pmod k) \pmod {k \pmod {101 \pmod k}}, k \pmod {101 \pmod k})$

And then just solve each congruence on the left for $1$ . The first one is just $1$ , the second one is the divisors of $100$ less than $50$ , and from then on it's essentially just brute force. For ease of calculation, solve the simplest congruences first for $k \leq 50$ and then don't bother to try $k$ which has already been proven to work for another congruence.

Next, once you find all $k$ that works, then find all integers $101 < m < 1000$ such that $m \equiv \pm k \pmod {101}$ . There are $854$ such integers.

Frankly speaking I have no idea how to do this manually ; so I did this with a program in Java ::

import java.io.*;

import java.math.*;

public class ModifiedEuclideanAlgorithm

{

public static void main(String[] args)

{

    int i=0,c=0;

    ModifiedEuclideanAlgorithm obj=new ModifiedEuclideanAlgorithm();

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

    {

        if(obj.fun(101,i,0)==1)

            c++;

    }

    System.out.println(" "+c);

}

int fun(int x,int y, int g)

{

    int m=0,h=0;    

    h=y%x;

    if(h==0)

    {

        if((x==1)&&(g<5))

            return 1;

        else return 0;

    }

    m=Math.min(h,x-h);

    return fun(m,x,g+1);

}

}

OUTPUT :: 854