PUMaC 2015 · 团队赛 · 第 8 题

PUMaC 2015 — Team Round — Problem 8

[ 5 ] Let σ : N → N be a function that takes a natural number n , and returns the sum of the 1 positive integer divisors of n . For example, σ (6) = 1 + 2 + 3 + 6 = 12. What is the largest 1 number n such that σ ( n ) = 1854? 1

解析

[ 5 ] Let σ : N → N be a function that takes a natural number n , and returns the sum of the 1 positive integer divisors of n . For example, σ (6) = 1 + 2 + 3 + 6 = 12. What is the largest 1 number n such that σ ( n ) = 1854? 1 Solution: A factorization of 1854 is 1854 = 3 · 618 = (1 + 2) · (1 + 617), thus since 2 and 617 are primes, we know that σ (1234) = σ (2 · 617) = (1 + 2)(1 + 617) = 1854. 1 To see that 1234 is the largest (in fact the only such number), note that the prime factorization 2 of 1854 = 2 · 3 · 103. Thus for each possible factorization 1854 = a · b · c · d (where a, b, c, d can equal 1), 3 · 618 is the only factorization such that a, b, c, d are the sums of powers of primes (or 1). Thus in fact, 1234 is the only number n such that σ ( n ) = 1854, and thus it is the 1 largest. Author: Heesu Hwang 3