HMMT 十一月 2015 · 冲刺赛 · 第 32 题

HMMT November 2015 — Guts Round — Problem 32

[ 17 ] Find the sum of all positive integers n ≤ 2015 that can be expressed in the form d e + y + xy , 2 where x and y are positive integers.

解析

[ 17 ] Find the sum of all positive integers n ≤ 2015 that can be expressed in the form d e + y + xy , 2 where x and y are positive integers. Proposed by: Calvin Deng Answer: 2029906 x Lemma: n is expressible as d e + y + xy iff 2 n + 1 is not a Fermat Prime. 2 Proof: Suppose n is expressible. If x = 2 k , then 2 n + 1 = (2 k + 1)(2 y + 1), and if x = 2 k − 1, then n = k (2 y + 1). Thus, if 2 n + 1 isn’t prime, we can factor 2 n + 1 as the product of two odd integers 2 x + 1, 2 y + 1 both greater than 1, resulting in positive integer values for x and y . Also, if n has an odd factor greater than 1, then we factor out its largest odd factor as 2 y + 1, giving a positive integer value for x and y . Thus n is expressible iff 2 n + 1 is not prime or n is not a power of 2. That leaves only the n such that 2 n + 1 is a prime one more than a power of two. These are well-known, and are called the Fermat primes. It’s a well-known fact that the only Fermat primes ≤ 2015 are 3, 5, 17, 257, which correspond to 2015 · 2016 n = 1 , 2 , 8 , 128. Thus the sum of all expressible numbers is − (1 + 2 + 8 + 128) = 2029906. 2