HMMT 二月 2015 · 冲刺赛 · 第 36 题
HMMT February 2015 — Guts Round — Problem 36
题目详情
- [ 25 ] A prime number p is twin if at least one of p + 2 or p − 2 is prime and sexy if at least one of p + 6 and p − 6 is prime. 9 How many sexy twin primes (i.e. primes that are both twin and sexy) are there less than 10 ? Express your answer as a positive integer N in decimal notation; for example, 521495223. If your answer is { ⌋ 1 in this form, your score for this problem will be max 0 , 25 − ⌊ | A − N | } , where A is the actual 10000 answer to this problem. Otherwise, your score will be zero.
解析
- [ 25 ] A prime number p is twin if at least one of p + 2 or p − 2 is prime and sexy if at least one of p + 6 and p − 6 is prime. 9 How many sexy twin primes (i.e. primes that are both twin and sexy) are there less than 10 ? Express your answer as a positive integer N in decimal notation; for example, 521495223. If your answer is { ⌋ 1 in this form, your score for this problem will be max 0 , 25 − ⌊ | A − N | } , where A is the actual 10000 answer to this problem. Otherwise, your score will be zero. Answer: 1462105 The Hardy-Littlewood conjecture states that given a set A of integers, the number of integers x such that x + a is a prime for all a ∈ A is w ( p ; A ) ∏ 1 − x p (1 + o (1)) 1 | A | k (ln x ) (1 − ) p p where w ( p ; A ) is the number of distinct residues of A modulo p and the o (1) term goes to 0 as x goes to infinity. Note that for the 4 tuples of the form (0 , ± 2 , ± 6), w ( p ; A ) = 3, and using the approximation ( ) k 1 − k/p k 1 2 ( ) 2 ≈ 1 − /p ≈ (1 − ) , we have k 2 (1 − 1 /p ) 2 p k k k k ( ) ( ) ( ) ( ) k ( ) ( ) ( ) ( ) ∏ 2 2 2 2 1 − 6 4 9 9 p ≈ · ≈ 1 2 k π 3 8 10 (1 − ) p p> 3 9 Applying this for the four sets A = (0 , ± 2 , ± 6), x = 10 (and approximating ln x = 20 and just taking the p = 2 and p = 3 terms, we get the approximate answer ( ) 3 1 2 9 1 − 1 − 10 9 2 3 4 · = 1640250 1 1 3 3 3 20 10 ( ) ( ) 2 3 One improvement we can make is to remove the double-counted tuples, in particular, integers x such that x, x + 6 , x − 6, and one of x ± 2 is prime. Again by the Hardy-Littlewood conjecture, the number of such x is approximately (using the same approximations) ( ) 6 1 2 9 1 − 1 − 10 9 2 3 2 · ≈ 90000 1 1 4 4 4 20 10 ( ) ( ) 2 3 9 Subtracting gives an estimate of about 1550000. Note that this is still an overestimate, as ln 10 is k 1 − k/p 1 ( ) 2 actually about 20 . 7 and < (1 − ) . 2 k p (1 − 1 /p ) Here is the C++ code that we used to generate the answer: Guts #include<iostream> #include<cstring> // memset using namespace std; const int MAXN = 1e9; bool is_prime[MAXN + 6]; int main(){ // Sieve of Eratosthenes memset(is_prime, true, sizeof(is_prime)); is_prime[0] = is_prime[1] = false; for (int i=2; i<MAXN + 6; i++){ if (is_prime[i]){ for (int j=2 * i; j < MAXN + 6; j += i){ is_prime[j] = false; } } } // Count twin sexy primes. int ans = 1; // 5 is the only twin sexy prime < 6. for (int i=6; i<MAXN; i++){ if (is_prime[i] && (is_prime[i-6] || is_prime[i+6]) && (is_prime[i-2] || is_prime[i+2])) { ans++; } } cout << ans << endl; return 0; } Guts