HMMT 二月 2024 · 冲刺赛 · 第 34 题
HMMT February 2024 — Guts Round — Problem 34
题目详情
- [20] Estimate the number of positive integers n ≤ 10 such that n + 1 has a prime factor greater than n . Submit a positive integer E . If the correct answer is A , you will receive ( ⌊ ⌋) ( ) 5 6 E 10 − E max 0 , 20 · min , + 0 . 5 points. 6 A 10 − A
解析
- [20] Estimate the number of positive integers n ≤ 10 such that n + 1 has a prime factor greater than n . ( ⌊ ⌋) ( ) 5 6 E 10 − E Submit a positive integer E . If the correct answer is A , you will receive max 0 , 20 · min , + 0 . 5 6 A 10 − A points. Proposed by: Pitchayut Saengrungkongka Answer: 757575 6 Solution: Let N denote 10 . We count by summing over potential prime factors p . 2 For any prime p > 2 , we have that p | n + 1 for two values of n if p ≡ 1 (mod 4) , and zero values otherwise. Pretending these values are equally likely to be any of 1 , . . . , p , we expect the number of n ( ) 2 N corresponding to a 1 (mod 4) prime to be min 2 , . p x The number of primes up to x is, by the Prime Number Theorem . Assuming around half of the log x 1 prime numbers are 1 (mod 4) , we on average expect some x to be a 1 (mod 4) prime of the time. 2 log x 2 Approximating by an integral over potential primes x from 1 to N , using our approximations, gives 2 ( ) ∫ N 2 N dx min 2 , · . x 2 log x 1 We now approximately calculate this integral as follows: 2 ( ) 2 ∫ ∫ ∫ N N N 2 N dx dx N min 2 , · = + dx x 2 log x log x x log x 1 1 N N 2 ≈ + N (log log( N ) − log log N ) log N N = + N log 2 . log N Here, for the first integral, we estimate log x on [1 , N ] by log N , and for the second integral, we use 1 that the antiderivative of is log log x . x log x Using log 2 ≈ 0 . 7 , one can estimate log N = 2 log 1000 ≈ 20 log 2 ≈ 14 giving a final estimate of 6 6 10 / 14 + 10 · 0 . 7 = 771428 . This estimate yields a score of 15. If one uses the closer estimate log 2 ≈ 0 . 69 , one gets the final estimate of 761428 , yielding a score of 18. Here is a code using sympy to calculate the final answer: from sympy.ntheory import factorint cnt = 0 for n in range (1,10 ** 6+1): if max(factorint(n ** 2+1, multiple=True)) > n: cnt += 1 print (cnt)