TheCATExam
Sign in

CAT 2024 Slot 2 — QA Question 2

Basics (Functions)Easy

A function f maps the set of natural numbers to whole numbers, such that f(xy) = f(x)f(y) + f(x) + f(y) for all x, y and f(p) = 1 for every prime number p. Then, the value of f(160000) is

Answer & solution

  • A

    8191

  • B

    2047

  • 4095

  • D

    1023

Solution

Medium

The relation f(xy)=f(x)f(y)+f(x)+f(y)f(xy)=f(x)f(y)+f(x)+f(y) becomes multiplicative after a clever shift: define g(x)=f(x)+1g(x)=f(x)+1. Then gg is multiplicative, so factor 160000160000 into primes and multiply.

1

Linearise the functional equation. Add 11 to both sides:

f(xy)+1=f(x)f(y)+f(x)+f(y)+1⇒ f(xy)+1=(f(x)+1)(f(y)+1)(factor RHS)⇒ g(xy)=g(x) g(y),where g(x)=f(x)+1\begin{aligned} &f(xy)+1=f(x)f(y)+f(x)+f(y)+1\\ &\Rightarrow\ f(xy)+1=(f(x)+1)(f(y)+1) \quad\text{(factor RHS)}\\ &\Rightarrow\ g(xy)=g(x)\,g(y),\quad\text{where }g(x)=f(x)+1 \end{aligned}
2

Value at primes. Given f(p)=1f(p)=1 for every prime pp:

g(p)=f(p)+1=2(for every prime p)\begin{aligned} &g(p)=f(p)+1=2 \quad\text{(for every prime }p\text{)} \end{aligned}
3

Factorise the argument. 160000=16×10000=24×(2×5)4=28×54160000=16\times 10000=2^4\times(2\times5)^4=2^8\times 5^4.

g(160000)=g ⁣(28)g ⁣(54)(g multiplicative, step 1)⇒ g(160000)=g(2)8 g(5)4=28⋅24(g(2)=g(5)=2, step 2)⇒ g(160000)=212=4096\begin{aligned} &g(160000)=g\!\left(2^8\right)g\!\left(5^4\right) \quad\text{(g multiplicative, step 1)}\\ &\Rightarrow\ g(160000)=g(2)^8\,g(5)^4=2^8\cdot 2^4 \quad\text{(g(2)=g(5)=2, step 2)}\\ &\Rightarrow\ g(160000)=2^{12}=4096 \end{aligned}
4

Convert back. Since f(160000)=g(160000)−1f(160000)=g(160000)-1:

f(160000)=4096−1=4095\begin{aligned} &f(160000)=4096-1=4095 \end{aligned}
f(160000)=4095f(160000)=4095
Need a hint?

When a functional equation has the shape f(xy)=f(x)f(y)+f(x)+f(y)f(xy)=f(x)f(y)+f(x)+f(y), try g=f+1g=f+1 to turn it into the clean multiplicative law g(xy)=g(x)g(y)g(xy)=g(x)g(y).

CAT 2024 Slot 2 QA Q2: A function f maps the set of natural numbers to whole numbers, such that f (xy) = f (x) f (y) + f (x) + f (y) — Solution | TheCATExam