HMMT 二月 2021 · 冲刺赛 · 第 30 题

HMMT February 2021 — Guts Round — Problem 30

[18] Let f ( n ) be the largest prime factor of n + 1. Compute the least positive integer n such that f ( f ( n )) = n .

解析

[18] Let f ( n ) be the largest prime factor of n + 1. Compute the least positive integer n such that f ( f ( n )) = n . Proposed by: Milan Haiman Answer: 89 2 2 Solution: Suppose f ( f ( n )) = n , and let m = f ( n ). Note that we have mn | m + n + 1. First we find all pairs of positive integers that satisfy this condition, using Vieta root jumping. 2 2 Suppose m + n + 1 = kmn , for some positive integer k . Considering this as a quadratic in m , let ′ ′ ′ ′ 2 the other root (besides m ) be m . We have m + m = kn , so m is an integer. Also, mm = n + 1. ′ ′ So if m > n then m ≤ n . So if we have a solution ( m, n ) we can find a smaller solution ( n, m ). In particular, it suffices to find all small solutions to describe all solutions. A minimal solution must have m = n , which gives only m = n = 1. We have that k = 3. Now the recurrence a = a = 1, a + a = 3 a describes all solutions with consecutive terms. In 0 1 n n +2 n +1 fact this recurrence gives precisely other Fibonacci number: 1 , 1 , 2 , 5 , 13 , 34 , 89 , 233 , . . . Checking these terms gives an answer of 89.