HMMT 十一月 2024 · 冲刺赛 · 第 2 题

2 . 5 | E − A | Submit a positive integer E . If the correct answer is A , you will receive 20 . 99 max 0 , 1 − A points. Proposed by: Pitchayut Saengrungkongka Answer: 141444 6 2 12 12 Solution: If x ≤ 10 , then 2 x − 1 < 2 · 10 . The density of prime numbers up to 2 · 10 is roughly 1 ≈ 0 . 0366 . 12 ln(2 · 10 ) − 1 1 2 4 4 2 However, 2 x − 1 can never be divisible by 2, 3, or 5. Only · · = of numbers are not divisible 2 3 5 15 by 2, 3, or 5, including all of the primes, so the density of primes among such numbers is a factor of 15 6 higher. Among the 10 possible values of x , we get an estimate of 4 15 6 · 0 . 0366 · 10 = 137250 4 primes, which is close enough for 19 points. 2 To refine this estimate further, observe that the values of 2 x − 1 are not uniformly distributed from 2 12 12 1 to 2 · 10 . Their average is very close to · 10 , so as a crude estimate, we can take the density of 3 4 12 prime numbers up to · 10 instead: 3 1 ≈ 0 . 03715 . 4 12 ln · 10 − 1 3 This gives us an estimate of 15 6 · 0 . 03715 · 10 ≈ 139313 , 4 which earns all 20 points. Using sage , one can easily obtain the exact answer by the following code. cnt = 0 for x in range (1 , 10 ^ 6 + 1 ) : if is_prime ( 2 * x ^ 2 - 1 ) : cnt + = 1 print ( cnt )