### Composites with prime repunit property题号：130 难度： 45 中英对照

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 by n, 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).

### Solution

- 设A(n)=k,那么R(k)%n，如何求满足条件的最小的k值 方法如下： 可通过下面公式计算$$R(k)\%n=(R(k-1)\%n+10^{k-1}\%n)\%n$$对于每一个n，k从1开始递增，直到第一个满足R(k)%n=0时的k即为该n下最小的k值 另外，可被形如111...这样的数，不可能被2和5的倍数整除 因为$$3\times7=21，9\times9=81$$而2和5的倍数和其他任意数的乘积都不可能存在尾数为1的情况 - 求满足5 < i < 25，GCD(i,10)==1,(n-1)%k==0这三个条件的i之和

### Code

public final class p130 {
private static final int LIMIT = (int) Math.pow(10, 6);
public static void main(String[] args){
long start=System.nanoTime();
long result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}
public static long run(){
long sum = 0;
int found = 0;
for (int i = 7; found < 25; i += 2) {	//因为题设要求i>5，并且2和5的倍数和其他任意数的乘积都不可能存在尾数为1的情况，所以是i+=2
if (i % 5 != 0 && !isPrime(i) && (i - 1) % findLeastDivisibleRepunit(i) == 0) {
sum += i;
found++;
}
}
return sum;
}
public static boolean isPrime(int x) {
if (x < 0)
throw new IllegalArgumentException("Negative number");
if (x == 0 || x == 1)
return false;
else if (x == 2)
return true;
else {
if (x % 2 == 0)
return false;
for (int i = 3, end = (int)Math.sqrt(x); i <= end; i += 2) {
if (x % i == 0)
return false;
}
return true;
}
}
private static int findLeastDivisibleRepunit(long n) {
if (n % 2 == 0 || n % 5 == 0)
return 0;
if (n > Integer.MAX_VALUE / 10)
throw new IllegalArgumentException("Arithmetic overflow");

long sum = 1;  // 表示R(k) mod n
long pow = 1;  // 表示10^(k-1) mod n
int k = 1;
while (sum % n != 0) {
k++;
pow = pow * 10 % n;
sum = (sum + pow) % n;
}

return k;
}

}

149253
390ms