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(n + 5) if n is odd

Let R = {i | ∃ j: f(j) = i} be the set of distinct values that f takes. The maximum possible size of R is _______. 

Answer 1

Let f(1) = a

Given:

f(n) = f(n/2) if n is even

f(n) = f(n + 5) if n is odd

Now, f (2) = f (2/2) = f(1) = a   [Because 2 is even]

For n = 3; 3 is odd

f(3) = f (3 + 5) = f (8) = f(8/2) = f(4) = f(4/2) = f (2) = f(2/2) = f(1) = a

For n = 4; 4 is even

f(4) = f (4/2) = f(2) = f(2/2) = f(1) = a;

For n = 5, 5 is odd

f(5) = f(5 + 5) = f(10) = f(10/2) =f(5) = f(5 + 5) = f(10) = f(10/2) = f(5) = b    [As f(5) is repeating ,let f(5) = b]

for n= 6

f(6) = f(6/2) = f(3) = x

So, there are two values only a and b. All multiples of 5 are b and others have value a.

So, the maximum possible size of R is 2.