[C/C++] Project Euler #26 Reciprocal Cycles

This problem is about finding the longest recurring cycle. In fact, recurring cycles boil down to Euler’s totient function. The totient function can be defined and calculated as follows:

If
\[ n = \prod_{p_k \mid n} p_k^{a_k} \]
then Euler’s totient function is given by:
\[ \phi(n) = \prod_{p_k \mid n} (p - 1)p^{a_k - 1} \]

In other words, if  n  is a composite number, the value of the totient function decreases significantly. If  n  is a prime number, then  \( \phi(n) = n - 1 \).

However, when finding the longest recurring cycle, we cannot rely solely on the totient function. If 10 is a primitive root of  n , the length of the recurring cycle is equal to the value of \( \phi(n) \). If it is not a primitive root, the length of the recurring cycle will be one of the divisors of \( \phi(n) \).

For numbers  n , multiples of 2 and 5 create non-recurring cycles, so the numbers we need to check are of the form 10k + 1, 3, 7, 9. Numbers outside of this set generate non-recurring cycles.

For example, if the length of the recurring cycle for 600 is  k , the length of the recurring cycle for 300 is also  k . Since 2 and 5 are divisors of 10, the recurring cycle length for 600 is the same as for 3. Thus, there is no need to check numbers ending in even digits or 5.

Now, consider the computational efficiency. Calculating the lengths of recurring cycles for numbers less than 1000 may not feel slow, but what happens when the numbers increase significantly? In such cases, checking only 4 out of every 10 numbers speeds up the process, and non-recurring cycles no longer need to be considered.

Additionally, to further improve speed, the program calculates from the largest number downward. If the current maximum recurring cycle length exceeds the number being checked, the program terminates.

 

reciprocal cycles

The presented program is for reference only.

//------------------------------------------------
//    Project Euler #26 - Reciprocal Cycles
//        - by Aubrey Choi
//        - created at 2015-01-26
//------------------------------------------------
#include <stdio.h>

int main()
{
    int f[4] = { 1, 3, 7, 9 };
    int max = 6, v = 7;

    for( int i = 1000 ; i >= 10 ; i -= 10 )
    {
        if( i <= max ) break;
        for( int j = 0 ; j < 4 ; j++ )
        {
            int c = i-f[j];
            int k;
            int t = 10;
            for( k = 1 ; t != 1 ; k++ )
            {
                t = (t*10)%c;
            }
            if( k > max ) { max = k; v = c; }
        }
    }

    printf("Ans = %d(%d)\n", v, max);
}

 

This program calculates the number less than 1000 that produces the longest recurring cycle in its decimal fraction when divided by 1 (reciprocal cycles). The implementation uses specific optimizations for efficiency. Here’s how the program works step by step:

1. Initialization:
• The array f[4] = {1, 3, 7, 9} represents the valid digits for numbers of the form  10k + 1, 3, 7, 9  (numbers not divisible by 2 or 5).
• Variables max and v store the maximum cycle length and the corresponding number, initialized to max = 6 and v = 7.

 

2. Outer Loop:
• Starts from 1000 and decrements by 10 (only considers numbers ending in valid digits).
• If the current number i is less than or equal to the maximum cycle length (max), the loop terminates early.

 

3. Inner Loop:
• Subtracts the valid digit f[j] from i to calculate a candidate number c.
• Initializes k (cycle length) and t (remainder tracker).

 

4. Cycle Length Calculation:
• Uses modular arithmetic to determine the cycle length  k  of  1/c .
• Repeatedly calculates  t = (t \times 10) \% c  until the remainder t returns to 1, indicating the start of the cycle.

 

5. Update Maximum Cycle:
• If the calculated cycle length k exceeds the current maximum (max), updates max and v with the new cycle length and its corresponding number.

 

6. Output:
• Prints the result: the number v and its cycle length max.