A function f : N^+ - N^+, defined on the set of positive integers N^+, satisfies the following properties:
f(n) = f(n...

Question

A function f : N^+ -> N^+, defined on the set of positive integers N^+, satisfies the following properties:
  f(n) = f(n/2)   if n is even
  f(n) = f(3n+5)  if n is odd
Let R = {r | r = f(n) for some n in N^+} be the set of distinct values that f takes. The maximum possible size of R is ___________.

Accepted Answer

2 The recurrence forces any positive integer to eventually cycle. Starting from n=1 (odd): f(1)=f(8)=f(4)=f(2)=f(1), creating a cycle. Starting from n=3 (odd): f(3)=f(14)=f(7)=f(26)=... eventually reaching a separate cycle or merging. Because every number eventually merges into at most two chains, f can take at most 2 distinct values.

A function f : N^+ -> N^+, defined on the set of positive integers N^+, satisfies the following properties: f(n) = f(n/2) if n is even f(n) = f(3n+5) if n is odd Let R = {r | r = f(n) for some n in N^+} be the set of distinct values that f takes. The maximum possible size of R is ___________.