There is no such $k$: We will say that a number $k$ is "bad" if Tita can jump only to finitely many integers from $k$. Note that if $b$ is "bad" and there is a sequence of jumps $a \to a_{1} \to a_{2} \to ... \to b$, then $a$ is also "bad" because once Titu gets to $b$ after a finite number of values, it can reach a finite number of values starting from $b$. Now, for the numbers $2,3...,12$ we have the following sequences of jumps: $$2 \to 4 \to 4 ... $$$$3 \to 6 \to 5 \to 10 \to 7 \to 14 \to 9 \to 6...$$$$8 \to 4 \to 4... $$$$11 \to 22 \to 13 \to 26 \to 15 \to 8 \to 4 \to 4...$$$$12 \to 5 \to 10 \to 7 \to 14 \to 9 \to 6 \to 5... $$ So the first $12$ integers are "bad". Now we prove by mathematical induction that all integers are "bad". Let the numbers $1,2,...,n-1$ be "bad", with $n > 12$. We will use the following lemmas: Lemma 1. If $a$ is a composite natural number, $f(a) \le \frac{a}{2}$. Proof: Indeed, let $f(a) = p$. Because $p|a$ we can write $a = p \cdot t$. We have that $a$ is composite so $t >1$. That means that $t \ge 2$ so $p = \frac{a}{t} \le \frac{a}{2}$. Lemma 2. If $b$ is a composite natural number, $g(b) \le \sqrt{b}$. Proof: Indeed, by setting $g(b) = q$, we have that $b = q \cdot s$. Now $s >1$ because $b$ is composite and $q \le s$ because $q$ is the smallest (prime) divisor of $b$ other than $1$. Now $b = q \cdot s \ge q^{2}$ so $q \le \sqrt{b}$. Now we will proceed with induction. If $n$ is composite, than $f(n) + g(n) \le \frac{n}{2} + \sqrt{n} < n$ for all $n > 4$. That means that Titu jumps from $n$ to a "bad" number by the induction hypothesis, so $n$ is also bad. If $n = p > 12$ is prime, then $n = p \to 2p \to p+2 = n+2$. Now we have two cases. If $n+2$ is composite, then $f(n+2) + g(n+2) \le \frac{n+2}{2} + \sqrt{n+2} < n$ if and only if $\sqrt{n+2} < \frac{n}{2} - 1 \Leftrightarrow n+2< \frac{n^{2}}{4} - n + 1 \Leftrightarrow 8n + 4 < n^{2}$ which is true for $n > 12$, so Tita also jumps to a "bad" number in this case. If $n+2 = q$ is also prime, then $n+2 = q \to 2q \to q+2 = n+4$. But $n, n+2, n+4$ give different remainders mod $3$, so one of them is not a prime, so $n+4$ must be composite if $n$ and $n+2$ are both prime. Finally, $f(n+4) + g(n+4) \le \frac{n+4}{2} + \sqrt{n+4} < n \Leftrightarrow \sqrt{n+4} < \frac{n}{2} - 2 \Leftrightarrow n+4 < \frac{n^{2}}{4} -2n + 4 \Leftrightarrow 12 < n$. So for $n > 12$ Tita always jumps to a number smaller than $n$, which must be "bad" by induction, so all numbers are "bad".

Prove by induction on n that hop cannot hit infinitely distinct integers. Base case. Try n <= 8. 2 -> 4 -> 4... 3 -> 6 -> 5 -> 10 -> 7 -> 14 -> 9 -> 6... 8 -> 4 -> 4... Inductive step. Suppose claim true for k < n, where n > 8. Consider n, and let f(n) = p, g(n) = q. Case 1. p < q. Then n >= pq. Because (p-1)(q-1) >= (2-1)(3-1) = 2, we have n >= pq > p + q. Thus, Tita hops to a number smaller than n, so by inductive step, the hop can't hit infinitely many distinct integers. Case 2. p = q. If n >= p^2 then n >= p^2 >= 2p, equality holding only when p = 2, in which case equality doesn't hold because n > 8. Thus Tita hops to 2p, which is smaller than n, so by inductive step, the hop can't hit infinitely many distinct integers. Now suppose n < p^2. Then n is prime, so n -> 2n -> n+2. If n+2 is prime, then n+2 -> 2(n+2) -> n+4. Now n+4 can't be prime since n, n+2, n+4 are greater than 3 and hit all the distinct residues mod 3 (including 0). Now use a similar argument to above to show f(n+4) + g(n+4) < n, so we can apply inductive step. If n+2 is not prime, then we can similarly show f(n+2) + g(n+2) < n, so we can also apply inductive step. In either case, Tita is doomed to traverse finitely many integers.

A problem proposed by Cuba

I`m looking for the OMCC 2018. Why isn`t publicated in Aops?

I dont know