HMMT 二月 2020 · 冲刺赛 · 第 34 题
HMMT February 2020 — Guts Round — Problem 34
题目详情
- [22] For odd primes p , let f ( p ) denote the smallest positive integer a for which there does not exist an 2 2 5 integer n satisfying p | n − a . Estimate N , the sum of f ( p ) over the first 10 odd primes p . 3 An estimate of E > 0 will receive b 22 min( N/E, E/N ) c points.
解析
- [22] For odd primes p , let f ( p ) denote the smallest positive integer a for which there does not exist an 2 2 5 integer n satisfying p | n − a . Estimate N , the sum of f ( p ) over the first 10 odd primes p . 3 An estimate of E > 0 will receive b 22 min( N/E, E/N ) c points. Proposed by: Michael Ren Answer: 2266067 Solution: Note that the smallest quadratic nonresidue a is always a prime, because if a = bc with b, c > 1 then one of b and c is also a quadratic nonresidue. We apply the following heuristic: if p , 1 p , . . . are the primes in increasing order, then given a “uniform random prime” q , the values of 2 ( ) ( ) p p 1 1 1 2 , , . . . are independent and are 1 with probability and − 1 with probability . q q 2 2 Of course, there is no such thing as a uniform random prime. More rigorously, for any n , the joint dis- ( ) ( ) p p 1 n tributions of , . . . , where q is a uniform random prime less than N converges in distribution q q to n independent coin flips between 1 and − 1 as N → ∞ . For ease of explanation, we won’t adopt this more formal view, but it is possible to make the following argument rigorous by looking at primes q < N and sending N → ∞ . Given any n , the residue of q mod n is uniform over the ϕ ( n ) residues mod n that are relatively prime to n . By quadratic reciprocity, conditioned on either q ≡ 1 (mod 4) or ( ) p n q ≡ 3 (mod 4), exactly half of the nonzero residues mod p satisfy = 1 and exactly half satisfy n q ( ) p n = − 1 for odd p (the case of p = 2 is slightly different and one must look mod 8, but the result n n q is the same). The residue of q mod 8, p , p , . . . , p are independent as these are pairwise relatively 2 3 n prime, yielding our heuristic. Thus, we may model our problem of finding the smallest quadratic nonresidue with the following process: independent fair coins are flipped for each prime, and we take the smallest prime that flipped 2 ∑ ∞ p 2 n heads. We can estimate the expected value of f ( p ) as . Looking at the first few terms gives n n =1 2 us 2 2 2 2 2 2 2 2 2 2 2 3 5 7 11 13 17 19 23 29
-
-
-
-
-
-
-
-
- ≈ 22 . 2 4 8 16 32 64 128 256 512 1024 5 The terms after this decay rapidly, so a good approximation is E = 22 · 10 , good enough for 20 points. 5 The more inaccurate E = 20 · 10 earns 15 points. This Python code computes the exact answer: def smallest_nqr(p): for a in range(1,p): if pow(a,(p-1)//2,p)==p-1: return a import sympy print(sum([smallest_nqr(p)2 for p in sympy.ntheory.primerange(3,sympy.prime(105+2))])) Remark. In 1961, Erd˝ os showed that as N → ∞ , the average value of f ( p ) over odd primes p < N ∑ ∞ p n will converge to ≈ 3 . 675. n n =1 2
-
-
-
-
-
-
-