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 3 of 5: Build the main chain

Previous step Next step

In plain words

The recursion grows quickly, but its main chain skips over the target index.

f(2)=3,\ f(3)=4,\ f(4)=6,\ f(6)=9,\ f(9)=14,\ f(14)=22,\ f(22)=35,\ f(35)=56,\ f(56)=90,\ f(90)=145

Detailed analysis

Starting at $f(1)=1$ and repeatedly using the first relation in the previous step gives $f(2)=3$ , $f(3)=4$ , $f(4)=6$ , $f(6)=9$ , $f(9)=14$ , $f(14)=22$ , $f(22)=35$ , $f(35)=56$ , $f(56)=90$ , and $f(90)=145$ .