5th Iberoamerican 1990

The function f is defined on the non-negative integers. f(2ⁿ - 1) = 0 for n = 0, 1, 2, ... . If m is not of the form 2ⁿ - 1, then f(m) = f(m+1) + 1. Show that f(n) + n = 2^k - 1 for some k, and find f(2¹⁹⁹⁰).

Solution

We claim that if 2^m <= n < 2^m+1, then f(n) = 2^m+1 - n - 1. Put r = 2^m+1 - n. Then the claim follows by induction on r. Hence f(2¹⁹⁹⁰) = 2¹⁹⁹⁰ - 1.

5th Ibero 1990

© John Scholes
jscholes@kalva.demon.co.uk
1 July 2002