HMMT 二月 2015 · 冲刺赛 · 第 36 题

英文解析

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.
    How many sexy twin primes (i.e. primes that are both twin and sexy) are there less than 10 ? Express 9
    your answer as a positive integer N in decimal notation; for example, 521495223. If your answer is
    { ⌋
    in this form, your score for this problem will be max 0 , 25 − ⌊ | A − N | } , where A is the actual 1
    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 isw ( p ; A )
    ∏
    1 −
    (1 + o (1))px
    | A |1
    (ln x ) (1 − )kpwhere w ( p ; A ) is the number of distinct residues of A modulo p and the o (1) term goes to 0 as x goes topinfinity. Note that for the 4 tuples of the form (0 , ± 2 , ± 6), w ( p ; A ) = 3, and using the approximation
    ( )
    1 − k/p kk
    2 ( )1
    ≈ 1 − /p ≈ (1 − ) , we have 2
    k 2
    (1 − 1 /p ) 2 pk k k k
    ( ) ( ) ( ) ( )
    ( ) ( ) ( ) ( )k
    ∏ 2 2 2 2
    1 −
    6 4 9 9
    ≈ · ≈pk 21
    π 3 8 10
    (1 − )
    p> 3 p
    Applying this for the four sets A = (0 , ± 2 , ± 6), x = 10 (and approximating ln x = 20 and just taking 9
    the p = 2 and p = 3 terms, we get the approximate answer
    ( )
    1 23
    1 − 1 −9
    10 9
    2 3
    4 · = 1640250
    1 1
    3 33
    20 10
    ( ) ( )
    2 3
    One improvement we can make is to remove the double-counted tuples, in particular, integers x suchthat x, x + 6 , x − 6, and one of x ± 2 is prime. Again by the Hardy-Littlewood conjecture, the numberof such x is approximately (using the same approximations)
    ( )
    1 26
    1 − 1 −9
    10 9
    2 3
    2 · ≈ 90000
    1 1
    4 44
    20 10
    ( ) ( )
    2 3
    Subtracting gives an estimate of about 1550000. Note that this is still an overestimate, as ln 10 is 9
    1 − k/pk
    1 ( )
    actually about 20 . 7 and < (1 − ) .2
    k 2
    (1 − 1 /p )p
    Here is the C++ code that we used to generate the answer:
    Guts
    #include<iostream>
    #include<cstring> // memsetusing namespace std;
    const int MAXN = 1 e 9;
    bool is_prime[MAXN + 6];
    int main(){
    // Sieve of Eratosthenesmemset(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