[C/C++] Project Euler #52 - Permuted Multiples

Problem 52 is so famous that I was able to find the answer without even writing a program after just reading the problem.

This problem is related to recurring decimals and prime numbers.

The problem itself is not difficult, so you can solve it one way or another. It’s a 5% difficulty problem. (Problem 51 had briefly jumped to 15% difficulty.)

A number like 125874, when multiplied by 2, becomes 251748, simply rearranging the digits.
The task is to find the smallest positive integer x such that x, 2x, 3x, 4x, 5x, and 6x all contain the same digits, just rearranged.

---

If you want to solve this by brute force, you can check whether the digits are the same after sorting them.
However, that could take a long time. But actually, with today’s computers, even brute-forcing would solve the problem very quickly.

To solve it more elegantly, you can consider the fraction 1/7.
The key point is whether 10 is a primitive root modulo 7.
This is important because it affects whether the repeating cycle length will be 6 digits or not.
For example, for 1/3, even though the Euler’s totient function of 3 is 2, 10 is not a primitive root modulo 3.
(10 mod 3 = 1, so it’s not a primitive root.)

The repeating decimal 076923076923 is created by 1/13.
This number also satisfies the same conditions as above.
Although it’s unfortunate that it starts with a 0, it still fits the pattern.

153846153846 is obtained by multiplying that number by 2.
This number also satisfies the same condition.

Now, for 7:
10 mod 7 = 3, and 3 is a primitive root of 7.
Therefore, the decimal created by 1/7, which is 142857, perfectly fits the kind of number required by the problem.
However, this number is a cyclic number with 6 digits rotating — it belongs to a smaller set than the original problem’s requirement.

---

cycle numbers

Thus, just to verify, I solved the problem using brute force.

//------------------------------------------------
//    Project Euler #52 - Permuted Multiples
//        - by Aubrey Choi
//        - created at 2015-03-31
//------------------------------------------------
#include <stdio.h>
#include <memory.h>

bool IsSameOrder(int a, int b, int digit);
int main()
{
    for( int digit = 2 ; digit < 8 ; digit++ )
    {
        int m = 1;
        for( int i = 1 ; i < digit ; i++, m *= 10 );
        for( int i = m ; i < 3*m ; i++ )
        {
            int k;
            for( k = 2 ; k <= 6 && IsSameOrder(i, k*i, digit) ; k++ );
            if( k > 6 )
            {
                printf("ans = %d\n", i);
                return 0;
            }
        }
    }
}

bool IsSameOrder(int a, int b, int digit)
{
    char check[2][10];
    memset(check, 0, sizeof(check));
    int s = 1;
    for( int i = 0 ; i < digit ; i++, s*=10 )
    {
        check[0][(a/s)%10]++;
        check[1][(b/s)%10]++;
    }
    return memcmp(check[0], check[1], 10) == 0;
}