IMO 1995 SL 23

Problem

S1 (UKR) Does there exist a sequence F(1), F(2), F(3), . . . of nonneg- ative integers that simultaneously satisfies the following three conditions? (a) Each of the integers 0, 1, 2, . . . occurs in the sequence. (b) Each positive integer occurs in the sequence infinitely often. (c) For any n \geq2, F
F
n163 = F(F(n)) + F(F(361)).

Solution

By putting F(1) = 0 and F(361) = 1, condition (c) becomes F(F(n163)) = F(F(n)) for n \geq2. For n = 2, 3, . . . , 360 let F(n) = n, and inductively define F(n) for n \geq362 as follows: F(n) = .F(m), if n = m163, m \inN; the least number not in {F(k) | k < n} , otherwise. Obviously, (a) each nonnegative integer appears in the sequence because there are infinitely many numbers not of the form m163, and (b) each positive integer appears infinitely often because F(m163) = F(m). Since F(n163) = F(n), (c) also holds. Second solution. Another example of such a sequence is as follows: If n = p\alpha1 1 p\alpha2 2 \cdot \cdot \cdot p\alphak k , is the factorization of n into primes, we put F(n) = \alpha1 + \alpha2 + \cdot \cdot \cdot + \alphak and F(1) = 0. Conditions (a) and (b) are evidently satisfied for this F, while (c) follows from F(F(n163)) = F(163F(n)) = F(F(n))+1 (because 163 is a prime) and F(F(361)) = F(F(192)) = F(2) = 1.