Problem 3

Let

0<f(1)<f(2)<f(3)<\ldots

be a sequence with all its terms positive integers. The

n

-th positive integer which doesn't belong to the sequence is

f(f(n))+1

. Find

f(240)

Step 2 of 5: Derive the counting recursion

Previous step Next step

In plain words

One known value supplies two new entries by counting the terms and gaps below it.

f(n)=k \;\Longrightarrow\; f(k)=n+k-1,\quad f(k+1)=n+k+1

Detailed analysis

Let $f(n)=k$ . The $n$ -th missing integer is $f(k)+1$ , so among the integers $1$ through $f(k)+1$ there are $n$ missing integers and $k$ sequence terms. Hence $n+k=f(k)+1$ , giving $f(k)=n+k-1$ . Therefore the $n$ -th missing integer is $n+k$ , so the next integer $n+k+1$ belongs to the sequence and equals $f(k+1)$ .