The function f(n) is defined on the positive integers as follows. f(1) = 1. f(n+1) is the largest positive integer m such that there is a strictly increasing arithmetic progression of m positive integers ending with n such that f(k) = f(n) for each k in the arithmetic progression. Show that there are positive integers a and b such that f(an + b) = n + 2 for all positive integers n.
Solution
Answer: a = 4, b = 8.
We start by finding the first few terms. f(2). The only AP of positive integers ending on 1 is 1 (we use AP to mean an arithmetic progression of strictly increasing positive integers). So f(2) = 1. For f(3) we have the AP 1, 2 (with f(1) = f(2) = 1), so f(3) = 2. For f(4) the only eligible term of the AP is 3, so f(4) = 1. For f(5), the eligible terms for the AP are 1, 2, 4, so the longest AP has 2 terms and f(5) = 2. For f(6) the eligible terms are 3, 5, so f(6) = 2. For f(7) the eligible terms are 3, 5, 6, so f(7) = 2. For f(8) the eligible terms are 3, 5, 6, 7, so the longest AP is 5, 6, 7 and f(8) = 3. For f(9) the only eligible term is 8, so f(9) = 1. For f(10) the eligible terms are 1, 2, 4, 9, so f(10) = 2. For f(11) the eligible terms are 3, 5, 6, 7, 10, so f(11) = 2. For f(12) the eligible terms are 3, 5, 6, 7, 10, 11 and the longest AP is 3, 7, 11, so f(12) = 3. For f(13) the only eligible terms are 8, 12, so f(13) = 2. For f(14) the eligible terms are 3, 5, 6, 7, 10, 11, 13 and the longest is 7, 10, 13, so f(14) = 3. For f(15) the eligible terms are 8, 12, 14 and f(15) = 2. For f(16) the eligible terms are 3, 5, 6, 7, 10, 11, 13, 15 and the longest is 3, 7, 11, 15, so f(16) = 4. For f(17) the only eligible term is 16, so f(17) = 1. For f(18) the eligible terms are 1, 2, 4, 9, 17 and the longest is 1, 9, 17, so f(18) = 3. For f(19) the eligible terms are 8, 12, 14, 18, so f(19) = 2. For f(20) the eligible terms are 3, 5, 6, 7, 10, 11, 13, 15, 19 and the longest is 3, 7, 11, 15, 19, so f(20) = 5. So f(21) = 1. Then f(22) = 2 (based on 17, 21), f(23) = 2, f(24) = 6 (3, 7, 11, 15, 19, 23), f(25) = 1, f(26) = 4 (1, 9, 17, 25), f(27) = 2, f(28) = 7 (3, 7, 11, 15, 19, 23, 27), f(29) = 1, f(30) = 4 (17, 21, 25, 29), f(31) = 2.
Summarising f(n) = 1 for n = 1, 2, 4, 9, 17, 21, 25; 2 for 3, 5, 6, 7, 10, 11, 13, 15, 19, 22, 23; 3 for 8, 12, 14, 18; 4 for 16; 5 for 20; 6 for 24. The pattern is not obvious. But we seem to get f(4n) = n based on an AP of terms k with f(k) = 2, then f(4n+1) = 1, f(4n+2) = n - something, based on an AP of terms k with f(k) = 1, then f(4n+3) = 2. But plenty of early exceptions.
We prove by induction that for n >= 7, f(4n) = n, f(4n+1) = 1, f(4n+2) = n-3, f(4n+3) = 2. We have already established it is true for n = 7. So assume it is true for n. For f(4n+4) we have the AP 3, 7, 11, ... , 4n+3 of length n+1 and that is obviously maximal, so f(4n+4) = n+1. That is the first term k with f(k) = n+1, so f(4n+5) = 1. For f(4n+6) we have the AP 17, 21, 25, ... , 4n+1, 4n+5 of length n-2. That particular AP cannot be extended because f(13) = 2. If we use a larger difference, then we must use at least a difference 8. But 4n+5, 4n+5-8, 4n+5-16, ... will have fewer terms. A larger difference will be even worse. So f(4n+5) = n-2. For f(4n+6) there are only two eligible terms for n > 7, so f(4n+6) = 2. That completes the induction.
Finally, note that f(4n+8) = n+2 for n >= 5 (just proved). But f(12) = 3 = 1 + 2, f(16) = 4 = 2 + 2, f(20) = 5 = 3 + 2, f(24) = 6 = 4 + 2. So f(4n+8) = n+2 for all positive n. [We are not asked to show that a, b are unique, but it is easy to do so. The only other candidate for a, b is f(4n+22), but that fails for n = 1.]
© John Scholes
jscholes@kalva.demon.co.uk
4 Sep 2002