PUMaC 2019 · 数论（B 组） · 第 4 题
PUMaC 2019 — Number Theory (Division B) — Problem 4
题目详情
- Let n be the smallest positive integer which can be expressed as a sum of multiple (at least two) consecutive integers in precisely 2019 ways. Then n is the product of k not necessarily distinct primes. Find k .
解析
- Let n be the smallest positive integer which can be expressed as a sum of multiple (at least two) consecutive integers in precisely 2019 ways. Then n is the product of k not necessarily distinct primes. Find k . Proposed by: Oliver Thakar Answer: 105 n can be written as a sum of 2 k + 1 consecutive integers if and only if 2 k + 1 is a divisor of n, for letting x be the integer in the center of the sum, then n = ( x − k ) + . . . + x + . . . + ( x + k ) = (2 k + 1) x. Hence, the number of odd divisors of n minus one (1 is an odd divisor of n but does not correspond to a sum of at least two consecutive integers) equals the number of ways that n can be written as a sum of an odd number of consecutive integers. There is a bijection between each writing of n as a sum of consecutive even integers and the odd divisors of n. Letting 2 k be an even integer, and x being the center of the sum (so that x is some integer 1 plus , ) then: 2 1 1 1 1 n = ( x − − k ) + . . . + ( x − ) + ( x + ) + . . . + ( x + + k ) = kx. 2 2 2 2 Thus, we know that the factor of 2 in k must be one more than the factor of 2 in n, and that 2 k divides n. For each odd divisor of n, there is one such k which is a power of 2 times that divisor, and vice versa. 1 Thus, the total number of ways to write n as the sum of multiple consecutive integers is 2 times the number of odd divisors minus 1. The number of odd divisors of n must be 1010 , then, which factors into 1010 = 2 ∗ 5 ∗ 101 . Now, there are three prime factors of 1010, so there can be up to 3 odd prime factors of n. (And, the smallest n will have no even prime factors.) 1009 If there is only one prime factor, then n = 3 , for n must be the smallest. 100 9 201 4 If there are two prime factors, then there are three possibilities: n = p q or n = p q or 504 n = p q. Clearly, in all three cases, the smallest n results in p = 3 and q = 5 . Of all three 100 9 1 8 5 100 9 cases, the smallest is n = 3 5 , for 3 01 > 3 > 5 . Similarly, n = 3 5 is smaller than 1009 909 14 9 n = 3 , for 3 > 3 > 5 . 100 4 4 9 Now, suppose there are three prime factors. Here, n = 3 · 5 · 7 . Since 5 · 7 < 5 , then this solution is the smallest possible. 100 4 Thus, the answer is n = 3 · 5 · 7 .