2

Moderator Note: This is a current contest question on Brilliant.org. The current contest ends on 13 October 2013, after which time this question will be unlocked.

A Function $f$ from the positive integers to the positive integers satisfies the following conditions:

  1. $f(xy)=f(x)+f(y)-1$
  2. $f(x)=1$ holds for only finitely many $x$.
  3. $f(30)=4$

What is the value of $f(14400)$?

This is how I proceeded. Putting $x=y=0$, we get $f(0)=1$ and similarly $f(1)=1$

Since $14400= (144)(100), f(14400)=f(100)+f(144)-1$.

From $f(30)=4$, we get $f(10)+f(3)=5$. Using this and from the above splitting we get $f(10)+f(10)-1+f(3)+f(48)-1=6+f(16)$. I am unable to find $f(16)$.

Mohsen Shahriari
  • 6,718
tattwamasi amrutam
  • 12,802
  • 5
  • 38
  • 73

1 Answers1

1

First of all, note that you can't put $x=0$ or $y=0$ because they're not in the domain of $f$.
Next, if you define $g(x):=f(x)-1$ then you'll have:
$g:\mathbb Z^+\to \mathbb Z^+\cup\{0\}\\ g(xy)=g(x)+g(y)\\ g(x)=0\text{ for finitely many }x\\ g(30)=3$
By putting $x=y=1$ you'll get $g(1)=0$.
Now for $x>1$, there's a unique factorization of $x$ into prime numbers. So if $p_i$ denotes the $i$'th prime number, there are $m_i$'s for which: $x=\prod_i p_i^{m_i}$.Therefore by the functional equation above, we get: $g(x)=\sum_i m_ig(p_i)$. So if we know $g(p_i)$ for each prime number $p_i$, we'll have $g(x)$ for arbitary $x$.
Now, note that if $g(p_i)=0$ then $g(p_i^n)=ng(p_i)=0$ and there will be infinitely many zeros of $g$, contradicting the assumptions. so we'll have $g(p_i)>0$.
Now, we know that $g(30)=g(2\cdot3\cdot5)=g(2)+g(3)+g(5)=3$. because $g(2)$, $g(3)$ and $g(5)$ are all positive, so all of them must be equal to $1$. This gives us the answer: $g(14400)=g(2^6\cdot3^2\cdot5^2)=6g(2)+2g(3)+2g(5)=6\cdot1+2\cdot1+2\cdot1=10$
So we'll have $f(14400)=11$.

Mohsen Shahriari
  • 6,718