Question 38

The function $f: \mathbb{N}^+ \to \mathbb{N}^+$ satisfies:

• $f(n) = f(n/2)$ if $n$ is even
• $f(n) = f(n + 5)$ if $n$ is odd

Notice that if $n$ is odd, $n + 5$ is even, so $f(n) = f(n+5) = f((n+5)/2)$.
Let us trace the operations on positive integers modulo 5:

• If $n$ is a multiple of 5 ($n = 5k$):
  • For $n = 5$: $f(5) = f(10) = f(5)$ (forms a self-loop).
  • For any $n = 5k$: repeatedly applying $n \to n/2$ when even and $n \to n+5$ when odd preserves divisibility by 5 because adding 5 preserves multiples of 5, and dividing an even multiple of 5 by 2 yields another multiple of 5.
    All multiples of 5 eventually reduce to the attractor 5.

Now consider integers NOT divisible by 5 ($n \not\equiv 0 \pmod 5$):

• Adding 5 preserves $n \pmod 5$.
• Dividing an even number by 2 multiplies by $2^{-1} \equiv 3 \pmod 5$, which never maps a non-zero residue to zero.
  Thus, no number not divisible by 5 can ever transition to a multiple of 5.

Trace values not divisible by 5:

• $n = 1$: $f(1) = f(6) = f(3)$
• $n = 3$: $f(3) = f(8) = f(4) = f(2) = f(1)$
• $n = 7$: $f(7) = f(12) = f(6) = f(3) = f(1)$
• $n = 9$: $f(9) = f(14) = f(7) = f(1)$
  Every integer coprime to 5 is reachable from and reduces to the cycle $\{1, 2, 3, 4, 6, 8\}$.

Therefore, the set of positive integers $\mathbb{N}^+$ is partitioned into exactly two disjoint connected components under the relations:

1. The set of integers not divisible by 5 (all mapped to $f(1)$)
2. The set of integers divisible by 5 (all mapped to $f(5)$)
   Since there are only 2 equivalence classes, $f$ can take at most 2 distinct values. Hence, the maximum possible size of $R$ is 2.