prob130: Composites with prime repunit property

드디어 한 문제를 풀었습니다... 이게 다 오버워치때문이야

A number consisting entirely of ones is called a repunit. We shall define R(k) to be a repunit of length k; for example, R(6) = 111111.

Given that n is a positive integer and GCD(n, 10) = 1, it can be shown that there always exists a value, k, for which R(k) is divisible byn, and let A(n) be the least such value of k; for example, A(7) = 6 and A(41) = 5.

You are given that for all primes, p > 5, that p − 1 is divisible by A(p). For example, when p = 41, A(41) = 5, and 40 is divisible by 5.

However, there are rare composite values for which this is also true; the first five examples being 91, 259, 451, 481, and 703.

Find the sum of the first twenty-five composite values of n for which

GCD(n, 10) = 1 and n − 1 is divisible by A(n).

1로만 이루어진 수를 repunit이라고 하라네요. R(n)은 1이 n개 있는 수고(e.g R(6)=111111)

그리고, n이 나눌 수 있는 최소의 R(k)에 대해, A(n)=k라 합시다. 그러니까 A(7)=6이라는 의미는 7로 나누어 떨어지는 최소의 repunit은, 1이 6개일 경우고, A(41)=5라는 건, 41로 나누어 떨어지는 최소의 repunit이 1이 5개일 경우고..

자 그러면, A(p)=p-1이 성립합니다. 왜냐하면 10^(p-1)는 mod p에서 1과 합동이라서..(fermat's little theorem에 의해) 그런데 경우에 따라서 n이 합성수인데도 불구하고 n-1이 A(n)에 의해 나누어 떨어질 때가 있다네요. 

그래서 구하고자 하는건, 10과 서로소인 n에 대해, A(n)으로 n-1을 나눌 수 있는 합성수 n을 작은 순서대로 25개 구해서 더한 값입니다. 

약간의 brutal force를 썼습니다. 문제에서 91이 위 조건을 만족시키는 최소의 수래서 91부터 시작해서 하나씩 수를 늘려가면서 조건에 맞는지 파악했는데요, 일단 

1)n이 소수인지 아닌지를 파악하고 n이 합성수이면 다음 단계를 진행했습니다.

2)n의 euler-phi함수를 구하고 n-1과 서로소인지 아닌지를 파악하고, 서로소가 아니면 다음 단계를 진행했ㅅ브니다.

3)n의 euler-phi함수값의 약수 중에서 n-1을 나누는 약수에 대해, 10^(약수)가 9*n과 1에서 합동인지 아닌지 파악해서 

4)3까지 다 통과하면 조건에 맞는 수로 채택을 해 answerlists에 집어넣었습니다.

5)answerlists의 갯수를 number이란 변수에 저장을 해서 25가 되는 순간 1~4의 process를 중단시켰습니다.

number=0

n=90

answerlists=[]

import factor,math,divisors,time

st=time.time()

while number!=25:

    n+=1

    temp=factor.factor(n)

    if len(temp)!=1:

        euler=n

        for i in temp:

            euler*=(i-1)/i

        if math.gcd(int(euler),n-1)!=1:

            templ=divisors.divisors(euler)

            for j in templ:

                if (n-1)%j==0:

                    if 10**j%(n*9)==1:

                        number+=1

                        answerlists.append(n)

                        break

print(sum(answerlists))

et=time.time()

print(et-st)

약 12초 정도 걸리네요