当前位置:首页 » Project Euler » 详细页

Repunit nonfactors 题号:133 难度: 50 中英对照

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.

Let us consider repunits of the form R(10n).

Although R(10), R(100), or R(1000) are not divisible by 17, R(10000) is divisible by 17. Yet there is no value of n for which R(10n) will divide by 19. In fact, it is remarkable that 11, 17, 41, and 73 are the only four primes below one-hundred that can be a factor of R(10n).

Find the sum of all the primes below one-hundred thousand that will never be a factor of R(10n).

Solution

设$R(k)=\frac{10^k-1}{9}$ **第一步** 设正整数$m,a$,有: $$\frac{R(am)}{R(a)}=\frac{\frac{10^{am}-1}{0}}{R(a)}$$ 由$10^{am}={\left( 9R(a)+1 \right)}^m$得: $$\frac{{\left( 9R(a)+1 \right)}^m-1}{9R(a)}$$ 显然${\left( 9R(a)+1 \right)}^m-1$可以被$9R(a)$整除。 这意味着$n< m$时$p|R(10^n) \rightarrow p|R(10^m)$($a|b$表示$a$能整除$b$)。 **第二步** 对于$x=2^a\times 5^b$,那么对于拥有足够大的$n$的$10^n$可以满足$x|10^n\quad (x<10^n)$,则$p|R(x)\rightarrow p|R(10^n)$。 只需要枚举$0< x< LIMIT\quad (LIMIT=10^5)$来判断,于是可以得到$a,b$的范围只需要在$[1,16]$即可($2^{16}>LIMIT$)

Code

import java.math.BigInteger;

public final class p133 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }	
    static public String run(){
		long sum = 0;
		for (int i = 2; i <= 100000; i++) {
			if (!isPrime(i)) continue;
			if (i == 2 || i == 5 || !hasDivisibleRepunit(i))
				sum += i;
		}
		return Long.toString(sum);
	}

	private static final BigInteger EXPONENT = BigInteger.TEN.pow(16);
	
	// Tests whether there exists a k such that R(10^k) is a multiple of p
	private static boolean hasDivisibleRepunit(int p) {
		return (BigInteger.TEN.modPow(EXPONENT, BigInteger.valueOf(p * 9)).intValue() - 1) / 9 % p == 0;
	}
	
    static private boolean isPrime(int i){
    	if(i<=1) return false;
    	if(i==2) return true;
    	if((i&1)==0) return false;
    	for(int j=3;j<=i/j;j++)
    		if(i%j==0) return false;
    	return true;
    }
}
453647705
161ms