Shourya's function

Algebra Level 5

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

(1) f ( x y ) = f ( x ) + f ( y ) 1 f(xy)=f(x)+f(y)-1 , for any pair of positive integers x x and y y .

(2) f ( x ) = 1 f(x)=1 holds for only finitely many x x .

(3) f ( 30 ) = 4 f(30)=4 .

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

This problem is posed by Shourya P .


The answer is 11.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

6 solutions

Albert Han
Oct 6, 2013

First, we can simplify the number 14400 14400 into 30 480 30*480 . Then, by using rule number 1, we can make such equation: f ( 144000 ) = f ( 30 ) + f ( 480 ) 1 f(144000) = f(30) + f(480) - 1 Then, since 480 480 is 30 16 30*16 , with using the first and third rule, we can write previous equation into f ( 14400 ) = f ( 30 ) + ( f ( 30 ) + f ( 16 ) 1 ) 1 f(14400)=f(30)+(f(30)+f(16)-1)-1 = f ( 16 ) + 2 f ( 30 ) 2 = f ( 16 ) + 6 =f(16)+2f(30)-2=f(16)+6 = 2 f ( 4 ) 1 + 6 = 4 ( 2 ) 3 + 6 = 4 f ( 2 ) + 3 =2f(4)-1+6=4(2)-3+6=4f(2)+3 Then, let's see the significance of the rule number 2. Let's assume that any prime number, p p , has a property that f ( p ) = 1 f(p)=1 Then, f ( p 2 ) = 2 f ( p ) 1 = 1 f(p^{2})=2f(p)-1=1 f ( p 4 ) = 2 f ( p 2 ) 1 = 1... f(p^{4}) = 2f(p^{2})-1=1... so the value of f ( p 2 n ) f(p^{2n}) will be always 1, when n is any positive integer. Therefore, this assumption breaks the second rule, so we can deduce that f ( p ) 1 f(p) \neq 1 Then, let's go back to rule three. We can simplify f ( 30 ) f(30) into such equation: f ( 30 ) = f ( 6 ) + f ( 5 ) 1 f(30) = f(6)+f(5)-1 = f ( 2 ) + f ( 3 ) + f ( 5 ) 2 = 4 =f(2)+f(3)+f(5)-2=4 Then, f ( 2 ) + f ( 3 ) + f ( 5 ) = 6 f(2)+f(3)+f(5)=6 And since 2 , 3 , 5 2,3,5 are all prime numbers, f ( 2 ) , f ( 3 ) , f ( 5 ) f(2), f(3), f(5) all have to be greater than 1, so the only way is f ( 2 ) = f ( 3 ) = f ( 5 ) = 2 f(2)=f(3)=f(5)=2 Therefore, by plugging f ( 2 ) = 2 f(2)=2 to the previous equation, f ( 14400 ) = 8 + 3 = 11 f(14400)=8+3=\boxed{11}

Loved your solution! I did it the same way.

Chirag Bharadwaj - 7 years, 8 months ago

I went f ( 2 6 3 2 5 2 ) = 6 f ( 2 ) + 2 f ( 3 ) + 2 f ( 5 ) ( ( 6 + 2 + 2 ) 1 ) f(2^6 3^2 5^2) = 6f(2) + 2f(3) + 2f(5) - ((6+2+2)-1)

Matt McNabb - 7 years, 8 months ago

Well Explained !!!

Achint Gupta - 7 years, 8 months ago

I prove that the only solution to f ( x ) = 1 f(x)=1 is only x = 1 x=1 by contradiction.And then deduce that f ( 2 ) = f ( 3 ) = f ( 5 ) = 2 f(2)=f(3)=f(5)=2 from the equation f ( 2 ) + f ( 3 ) + f ( 5 ) = 6 f(2)+f(3)+f(5)=6

Artupazira ykzer - 7 years, 8 months ago

Log in to reply

I proved by contradicting the fact that if there are at least 2 solutions,say x 1 , x 2 x_1,x_2 then we can make a solution x 3 = ( x 1 ) ( x 2 ) x_3=(x_1)(x_2) using the first condition.But we can do this infinitely many times,contradicting the second condition

Artupazira ykzer - 7 years, 8 months ago

Can you tell me how does your contradiction proof go? Just curious. Thanks!

Albert Han - 7 years, 8 months ago

14400=120^2 . so x nd y be tken 120,120

A Former Brilliant Member - 4 years, 5 months ago

From the condition (1) we can obtain f ( 1 ) = 1 f(1)=1 by substituting x = y = 1 x=y=1 .

For any positive integer k > 1 k>1 . If f ( k ) = 1 f(k)=1 , then f ( k 2 ) = f ( k ) + f ( k ) 1 = 1 f(k^2)=f(k)+f(k)-1=1 .

Moreover f ( k 3 ) = f ( k 2 ) + f ( k ) 1 = 1 f(k^3)=f(k^2)+f(k)-1=1 , and so on.

Which is contradict with the condition (2).

Thus there is only one positive integer x x satisfying f ( x ) = 1 f(x)=1 , that is 1 1 .

Since f ( 30 ) = 4 f(30)=4 , by condition (1) we obtain f ( 2 ) + f ( 3 ) + f ( 5 ) = 6 f(2)+f(3)+f(5)=6 .

Because f ( 2 ) , f ( 3 ) , f ( 5 ) f(2),f(3),f(5) are all positive integer more than 1 1 , there is only one possible value of them that is f ( 2 ) = f ( 3 ) = f ( 5 ) = 2 f(2)=f(3)=f(5)=2 .

Now we move to computing f ( 14400 ) f(14400) .

By condition (1) we get f ( 14400 ) = 2 f ( 30 ) + 4 f ( 2 ) 5 = 2 ( 4 ) + 4 ( 2 ) 5 = 11 f(14400)=2f(30)+4f(2)-5=2(4)+4(2)-5=11 .

From f ( 30 ) = 4 f(30)=4 ,

f ( 14400 ) = f ( 30 ) + f ( 480 ) 1 f(14400)=f(30)+f(480)-1 = f ( 30 ) + ( f ( 30 ) + f ( 16 ) 1 ) 1 = 6 + f ( 16 ) =f(30)+(f(30)+f(16)-1)-1=6+f(16)

f ( 16 ) = f ( 4 ) + f ( 4 ) 1 f(16)=f(4)+f(4)-1 = ( f ( 2 ) + f ( 2 ) 1 ) + ( f ( 2 ) + f ( 2 ) 1 ) 1 = 4 f ( 2 ) 3 =(f(2)+f(2)-1)+(f(2)+f(2)-1)-1=4f(2)-3

Therefore, f ( 14400 ) = 3 + 4 f ( 2 ) f(14400)=3+4f(2)

Since f ( 30 ) = f ( 2 ) + f ( 3 ) + f ( 5 ) 2 = 4 f(30)=f(2)+f(3)+f(5)-2=4 , f ( 2 ) + f ( 3 ) + f ( 5 ) = 6 f(2)+f(3)+f(5)=6

From the condition 2, none of the prime number can be equal to 1 because that will make its power become 1 and there will be infinitely many 1s. ( If f ( 2 ) = 1 f(2)=1 , then f ( 4 ) = f ( 2 ) + f ( 2 ) 1 = f ( 2 ) = 1 f(4)=f(2)+f(2)-1=f(2)=1 , f ( 8 ) = f ( 2 ) + f ( 2 ) + f ( 2 ) 2 = f ( 2 ) = 1 f(8)=f(2)+f(2)+f(2)-2=f(2)=1 and so on)

So f ( 2 ) = 2 f(2)=2 .

So the value of f ( 14400 ) = 3 + 4 f ( 2 ) = 11 f(14400)=3+4f(2)=11 .

Anatole Dahan
Apr 7, 2014

First of all, we can easily prove that f ( 1 ) = 1 f(1)=1 . Now, let n be the greatest solution of f ( x ) = 1 f(x)=1 Then, f ( n 2 ) = 2 f ( n ) 1 f(n^2)=2f(n)-1 Therefore n = 1 n=1 . Therefore, f ( 2 ) > 1 , f ( 3 ) > 1 , f ( 5 ) > 1 f(2)>1, f(3)>1, f(5)>1 Moreover, we have f ( 30 ) = 4 = f ( 2 ) + f ( 3 ) + f ( 5 ) 2 f ( 2 ) = 6 f ( 3 ) f ( 5 ) f(30)=4=f(2)+f(3)+f(5)-2\Rightarrow f(2)=6-f(3)-f(5) yet f ( 3 ) 2 , f ( 5 ) 2 f(3)\ge 2, f(5)\ge 2 so f ( 2 ) 6 2 2 = 2 f ( 2 ) > 1 f ( 2 ) = 2 f(2)\le 6-2-2=2 \land f(2)>1\Rightarrow f(2)=2 We can now find f ( 16 ) f(16) : f ( 16 ) = f ( 2 ) + f ( 8 ) 1 = 2 f ( 2 ) + f ( 4 ) 2 = 4 f ( 2 ) 3 = 5 f(16)=f(2)+f(8)-1=2f(2)+f(4)-2=4f(2)-3=5 Finally : f ( 14400 ) = f ( 30 ) + f ( 480 ) 1 = 2 f ( 30 ) + f ( 16 ) 2 = 8 + 5 2 = 11 f(14400)=f(30)+f(480)-1=2f(30)+f(16)-2=8+5-2=\boxed{11}

Lauren Yeo
Oct 9, 2013

f ( 14400 ) = f ( 900 ) + f ( 16 ) 1 = 2 f ( 30 ) + f ( 16 ) 2 = 6 + f ( 16 ) f(14400)=f(900)+f(16)-1=2f(30)+f(16)-2=6+f(16)

Also, f ( 16 ) = 2 f ( 4 ) 1 = 2 ( 2 f ( 2 ) 1 ) 1 = 4 f ( 2 ) 3 f(16)=2f(4)-1=2(2f(2)-1)-1=4f(2)-3

We now know that f ( 14400 ) = 3 + 4 f ( 2 ) f(14400)=3+4f(2) . So if we can find f ( 2 ) f(2) , the problem is solved.

If f ( p ) = 1 f(p)=1 for some prime p p , f ( p 2 ) = 2 f ( p ) 1 = 1 f(p^{2})=2f(p)-1=1 . Similarly, f ( p 4 ) = 1 , f ( p 2 n ) = 1 f(p^{4})=1, f(p^{2^{n}})=1 for all positive integers n.

But condition (2) states that f ( x ) = 1 f(x)=1 does not hold for infinitely many x, so f ( p ) 2 f(p)≥2 . f ( 30 ) = f ( 2 ) + f ( 15 ) 1 = f ( 2 ) + f ( 3 ) + f ( 5 ) 2 = 4 f(30)=f(2)+f(15)-1=f(2)+f(3)+f(5)-2=4 , so f ( 2 ) + f ( 3 ) + f ( 5 ) = 6 f(2)+f(3)+f(5)=6 . This means that f ( 2 ) = f ( 3 ) = f ( 5 ) = 2 f(2)=f(3)=f(5)=2 (since 2, 3, 5 are primes) otherwise they cannot add up to 6. So the answer is 3 + 4 ( 2 ) = 11 3+4(2)=11 .

The given condtion 1 imply for all positive integers x 1 , x 2 , x n x_1, x_2 \cdots , x_n , f ( x 1 x 2 x n ) = f ( x 1 ) + f ( x 2 x x 3 x n ) 1 = = f ( x 1 ) + f ( x 2 ) + + f ( x n ) ( n 1 ) f(x_1 \cdot x_2 \cdots x_n)=f(x_1)+f(x_2x\cdot x_3 \cdots x_n)-1=\cdots = f(x_1)+f(x_2)+\cdots+f(x_n)-(n-1) , which we can have f ( 14400 ) = f ( 2 6 3 2 5 2 ) = 6 f ( 2 ) + 2 f ( 3 ) + 2 f ( 5 ) 11 f(14400)=f(2^6 \cdot 3^2 \cdot 5^2)=6f(2)+2f(3)+2f(5)-11 . It suffices to determine the value of f ( 2 ) , f ( 3 ) , f ( 5 ) f(2), f(3), f(5) .

Lemma: f ( n ) 2 f(n)\ge 2 for all n 1 n\neq 1 .

If there exist n 1 n\neq 1 such that f ( n ) = 1 f(n)=1 , then f ( n k ) = f ( n k 1 ) + f ( n ) 1 = f ( n k 1 ) = f ( n k 2 ) = f ( n ) = 1 f(n^k)=f(n^{k-1})+f(n)-1=f(n^{k-1})=f(n^{k-2})=\cdots f(n)=1 for all k k , condraticts condition 2.

Given f ( 30 ) = 4 f(30)=4 , then f ( 2 ) + f ( 15 ) = 5 f(2)+f(15)=5 , f ( 3 ) + f ( 10 ) = 5 f(3)+f(10)=5 , f ( 5 ) + f ( 6 ) = 5 f(5)+f(6)=5 . This imply f ( 2 ) , f ( 3 ) , f ( 5 ) , f ( 6 ) f(2), f(3), f(5), f(6) are either 2 or 3. However, f ( 2 ) + f ( 3 ) = f ( 6 ) 1 f(2)+f(3)=f(6)-1 , and f ( 6 ) f(6) is either 2 or 3, we have f ( 2 ) = f ( 3 ) = 2 f(2)=f(3)=2 . So f ( 6 ) = 3 f ( 5 ) = 2 f(6)=3 \Rightarrow f(5)=2 .

So f ( 14400 ) = 6 f ( 2 ) + 2 f ( 3 ) + 2 f ( 5 ) 11 = 11 f(14400)=6f(2)+2f(3)+2f(5)-11=11 .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...