PUMaC 2017 · 团队赛 · 第 5 题

PUMaC 2017 — Team Round — Problem 5

(4) Define the sequences a and b as follows: a = 2017 and b = 1. For n > 1, if there is n n 1 1 √ k a greatest integer k > 1 such that a is a perfect k th power, then a = a ; otherwise, n n +1 n a = a + b . If a ≥ a then b = b , otherwise b = b + 1. Find a . n +1 n n n +1 n n +1 n n +1 n 2017

解析

First, to understand what a looks like: each time the sequence resets, the difference between n upcoming terms increases by one, so it will be an arithmetic sequence until that next reset. We get the following table: n a b n n 1 2017 1 . . . . . . . . . 9 2025 1 10 45 2 11 47 2 12 49 2 13 7 3 . . . . . . . . . 16 16 3 17 2 4 18 6 4 . . . . . . . . . 2017 8002 4 The crucial step is to observe that, for n ≥ 17, a is always of form 4 k + 2; this cannot be a n perfect power because 4 k + 2 = 2(2 k + 1), which is always divisible by 2 but no greater integer power of 2. Problem written by Zack Stier