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

英文解析

32. [ 17 ] Find the sum of all positive integers n ≤ 2015 that can be expressed in the form d e + y + xy ,
    where x and y are positive integers.2
    Proposed by: Calvin Deng
    Answer: 2029906
    Lemma: n is expressible as d e + y + xy iff 2 n + 1 is not a Fermat Prime.x
    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 2
    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 anodd factor greater than 1, then we factor out its largest odd factor as 2 y + 1, giving a positive integervalue for x and y . Thus n is expressible iff 2 n + 1 is not prime or n is not a power of 2. That leavesonly the n such that 2 n + 1 is a prime one more than a power of two. These are well-known, and arecalled 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