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

Investigating the primality of numbers of the form 2n2-1 题号:216 难度: 45 中英对照

Consider numbers t(n) of the form t(n) = 2n2-1 with n > 1.
The first such numbers are 7, 17, 31, 49, 71, 97, 127 and 161.
It turns out that only 49 = 7*7 and 161 = 7*23 are not prime.
For n ≤ 10000 there are 2202 numbers t(n) that are prime.

How many numbers t(n) are prime for n ≤ 50,000,000 ?

Solution

此问题中$t(n)$定义为 $t(n)=2n^2-1(1< n\leq 50,000,000)$,因此$t(n)\geq 7$,并且是个严格递增的序列,我们要找到其中素数的个数。 解决的思路如下: 1. 生成可变的整数序列$seq$ ,将它初始化为$( t(2),t(3),t(4), ... , t(5000000) )$,各元素对应的数组下标为$( 2 , 3, 4 , ... , 5000000)$。($seq[0]$和$seq[1]$对后续操作无作用) 2. 对于每个下标$i=( 2 , 3 ,4 , ... , 5000000)$,按升序分别进行以下操作: a)如果$seq[i] == t(i)$,那么$t(i)$一定是个素数,计数加1(下面引理3中给出证明)。接着执行b) b) 如果$seq[i]>1$,那么令$p=seq[i]$。对于所有满足 $j\, mod\, p=i$ 或者 $j\, mod\, p=-i$ 的下标 j(即$1< j=k*p\pm i\leq5000000,(k\in Z)$),用 $p$ 不断地去除$seq[j]$,直到它们互质。(下面引理2给出证明,为什么只需对这些下标进行操作) c) 如果如果$seq[i]==1$,什么都不做 3. 遍历完所有下标 $i=( 2 , 3 ,4 , ... , 5000000)$,输出素数的计数。 #### 引理1:$t(n)$中所有的项都不能被2,3,5整除。 证明: 1. 对于所有的n,因为 $t(n)=2n^2-1 $都是奇数,所以显然都不能被2整除 2. 对于任意的n,因为$n\, mod\, 3=\{0,1,2\}$ ,相应地 $2*n^2-1\,mod \, 3=\{2,1,1\}$,所以$t(n)$都不能被3整除 3. 对于任意的n,因为$n\, mod\, 5=\{0,1,2,3,4\}$ ,相应地 $2*n^2-1\,mod \, 5=\{4,1,2,2,1\}$,所以$t(n)$都不能被5整除 #### 引理2:如果$\,p\,$(可是素数,也可是合数)能整除某个项t(i),那么$\,p\,$也可以整除项$t(j=k*p\pm i)$,只要$\,j\,$是个合法的下标。其中,$\,k\,$是任意整数。 证明: 如果 $\,p\,$ 能整除$\,t(i)\,$,即 $2*n^2-1\,mod \, p=0$ 要找到所有满足$\,p\,$能整除$\,t(j)\,$的下标$\,p\,$,有, $$ t(j)\,mod\,p=0\,<=>\,2j^2-1\,mod\,p=0\,<=>\,2j^2-1\,mod\,p=2i^2-1\,mod\,p $$ $$ <=>2j^2\,mod\,p=2i^2\,mod\,p\,<=>2(j^2-i^2)\,mod\,p=0<=>2(j-i)(j+i)\,mod\,p=0 $$ 所以, $j\,mod\,p =i$ 或者$j\,mod\,p =-i$,即在合法坐标范围内,满足$\,j=k*p\pm i\,(k\in Z)$的坐标$\,j\,$。引理得证。 且如果$\,p\,$不能整除$\,t(i)\,$,那么上述证明的初始条件就会不成立。因此,当$\,p\,$能整除项$\,t(i)\,$时,在合法坐标范围内,满足$\,j=k*p\pm i\,(k\in Z)$的坐标$\,j\,$,是$\,p\,$能整除$\,t(j)\,$的充分必要条件 #### 引理3:在算法的主循环中(解决思路的2),对于每个下标$\,i\,$,当它们被遍历到时,$\,seq[i]\,$的值要么是1,要么是个素数: 证明:对于$i=(2,3,4)$的情况,显然$t(i)$是个素数。对于其他$\,t(i)\,$,设想一些素数$\,p\,$能够整除seq[i],那么它们会使什么取值: - 当$\,p< i\,$:应用引理2,那么$\,p\,$同样能整除$t(i-p)$。因为$\,p< i\,$,知$\,i-p\geq1$。我们将证明$i-p=1$是不可能的。因为如果成立,则$\,i=p+1\,$,$t(i)=2i^2-1=2(p+1)^2-1=2p^2+4p+1 =1\,mod\,p$,可它并不是$\,p\,$的倍数。因此, $i-p\geq2$。这意味着,此种情况下的$\,p\,$是某些$\,seq[j]\,$的值,$j< i$。而这些$\,p\,$值已经在之前的遍历中除过seq[i]了。 - 当$p=i$:这也是不可能的,因为$t(i)=2i^2-1=-1\,mod\,p$,并且$\,seq[i]\,$不可能除以过这样的p值。 - 当$i< p< 2i$:应用引理2,p能到整除$t(p-i)$。因为$\,i< p\,$,知$\,p-1\geq1$。我们将证明$p-i=1$是不可能的。因为如果成立,则$\,i=p-1\,$,且$t(i)=2i^2-1=2(p-1)^2-1=2p^2-4p+1=1\,mod\,p$,它并不是 p的倍数。因此$p-i\geq2$,即$i+2\leq p< 2i< 2i^2-1$。这意味着,此种情况下的$\,p\,$是某些seq[j]的值,$j< i$。而这些$\,p\,$值已经在之前的遍历除过$\,seq[i]\,$了 - 当$2i< p$:如果$\,seq[i]\,$它本身是个素数,没有问题。否则如果$\,seq[i]\,$不是素数,那么它至少将有两个质因子$p,q>2i$,但这意味着 $pq>4i^2>2i^>2i^2-1=t(i)>=seq[i]$,出现矛盾。因此当$2i< p$ 时,$\,seq[i]\,$是个素数 因此,综上所述,当遍历到下标$\,i\,$时,$\,seq[i]\,$的值要么为1,要么它是个素数

Code

public final class p216 {
	
	private static int LIMIT;
	
	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() {
		LIMIT =	50000000;
		// 产生整个2*n^2-1的数字序列
		long[] sequence = new long[LIMIT + 1];
		sequence[0] = sequence[1] = -1;
		for (int i = 2; i < sequence.length; i++)
			sequence[i] = 2L * i * i - 1;
		
		int count = 0;
		for (int i = 2; i < sequence.length; i++) {

			long term = sequence[i];
			//遍历到下标i时,如果该项sequence[i]的值为t(i),那么t(i)就是素数,计数加1
			if (term == 2L * i * i - 1)
				count++;
			
			//以下操作跳过那些下标 j > LIMIT*2的项,在Solution的引理3中说明
			if (1 < term && term <= LIMIT * 2) {
				
				//访问后续序列中的特定项,除以它们的因子p
				int p = (int)term;
				
				//使用p去除下标满足j mod p = i 的sequence[j]
				for (int j = i + p; j < sequence.length; j += p) {
					
					while (sequence[j] % p == 0)
						sequence[j] /= p;
				}
				//使用p去除下标满足j mod p = -i的sequence[j]
				for (int j = i + (p - i) * 2 % p; j < sequence.length; j += p) {
					while (sequence[j] % p == 0)
						sequence[j] /= p;
				}
			}
		}
		return count;
	}
	
}
5437849
8462ms