Function f from the positive integers to the positive integers satisfies the following conditions:
(1) f ( x y ) = f ( x ) + f ( y ) − 1 , for any pair of positive integers x and y .
(2) f ( x ) = 1 holds for only finitely many x .
(3) f ( 3 0 ) = 4 .
What is the value of f ( 1 4 4 0 0 ) ?
This problem is posed by Shourya P .
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.
Loved your solution! I did it the same way.
I went f ( 2 6 3 2 5 2 ) = 6 f ( 2 ) + 2 f ( 3 ) + 2 f ( 5 ) − ( ( 6 + 2 + 2 ) − 1 )
Well Explained !!!
I prove that the only solution to f ( x ) = 1 is only x = 1 by contradiction.And then deduce that f ( 2 ) = f ( 3 ) = f ( 5 ) = 2 from the equation f ( 2 ) + f ( 3 ) + f ( 5 ) = 6
Log in to reply
I proved by contradicting the fact that if there are at least 2 solutions,say x 1 , x 2 then we can make a solution x 3 = ( x 1 ) ( x 2 ) using the first condition.But we can do this infinitely many times,contradicting the second condition
Can you tell me how does your contradiction proof go? Just curious. Thanks!
14400=120^2 . so x nd y be tken 120,120
From the condition (1) we can obtain f ( 1 ) = 1 by substituting x = y = 1 .
For any positive integer k > 1 . If f ( k ) = 1 , then f ( k 2 ) = f ( k ) + f ( k ) − 1 = 1 .
Moreover 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 satisfying f ( x ) = 1 , that is 1 .
Since f ( 3 0 ) = 4 , by condition (1) we obtain f ( 2 ) + f ( 3 ) + f ( 5 ) = 6 .
Because f ( 2 ) , f ( 3 ) , f ( 5 ) are all positive integer more than 1 , there is only one possible value of them that is f ( 2 ) = f ( 3 ) = f ( 5 ) = 2 .
Now we move to computing f ( 1 4 4 0 0 ) .
By condition (1) we get f ( 1 4 4 0 0 ) = 2 f ( 3 0 ) + 4 f ( 2 ) − 5 = 2 ( 4 ) + 4 ( 2 ) − 5 = 1 1 .
From f ( 3 0 ) = 4 ,
f ( 1 4 4 0 0 ) = f ( 3 0 ) + f ( 4 8 0 ) − 1 = f ( 3 0 ) + ( f ( 3 0 ) + f ( 1 6 ) − 1 ) − 1 = 6 + f ( 1 6 )
f ( 1 6 ) = f ( 4 ) + f ( 4 ) − 1 = ( f ( 2 ) + f ( 2 ) − 1 ) + ( f ( 2 ) + f ( 2 ) − 1 ) − 1 = 4 f ( 2 ) − 3
Therefore, f ( 1 4 4 0 0 ) = 3 + 4 f ( 2 )
Since f ( 3 0 ) = f ( 2 ) + f ( 3 ) + f ( 5 ) − 2 = 4 , 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 , then f ( 4 ) = f ( 2 ) + f ( 2 ) − 1 = f ( 2 ) = 1 , f ( 8 ) = f ( 2 ) + f ( 2 ) + f ( 2 ) − 2 = f ( 2 ) = 1 and so on)
So f ( 2 ) = 2 .
So the value of f ( 1 4 4 0 0 ) = 3 + 4 f ( 2 ) = 1 1 .
First of all, we can easily prove that f ( 1 ) = 1 . Now, let n be the greatest solution of f ( x ) = 1 Then, f ( n 2 ) = 2 f ( n ) − 1 Therefore n = 1 . Therefore, f ( 2 ) > 1 , f ( 3 ) > 1 , f ( 5 ) > 1 Moreover, we have f ( 3 0 ) = 4 = f ( 2 ) + f ( 3 ) + f ( 5 ) − 2 ⇒ f ( 2 ) = 6 − f ( 3 ) − f ( 5 ) yet f ( 3 ) ≥ 2 , f ( 5 ) ≥ 2 so f ( 2 ) ≤ 6 − 2 − 2 = 2 ∧ f ( 2 ) > 1 ⇒ f ( 2 ) = 2 We can now find f ( 1 6 ) : f ( 1 6 ) = f ( 2 ) + f ( 8 ) − 1 = 2 f ( 2 ) + f ( 4 ) − 2 = 4 f ( 2 ) − 3 = 5 Finally : f ( 1 4 4 0 0 ) = f ( 3 0 ) + f ( 4 8 0 ) − 1 = 2 f ( 3 0 ) + f ( 1 6 ) − 2 = 8 + 5 − 2 = 1 1
f ( 1 4 4 0 0 ) = f ( 9 0 0 ) + f ( 1 6 ) − 1 = 2 f ( 3 0 ) + f ( 1 6 ) − 2 = 6 + f ( 1 6 )
Also, f ( 1 6 ) = 2 f ( 4 ) − 1 = 2 ( 2 f ( 2 ) − 1 ) − 1 = 4 f ( 2 ) − 3
We now know that f ( 1 4 4 0 0 ) = 3 + 4 f ( 2 ) . So if we can find f ( 2 ) , the problem is solved.
If f ( p ) = 1 for some prime p , f ( p 2 ) = 2 f ( p ) − 1 = 1 . Similarly, f ( p 4 ) = 1 , f ( p 2 n ) = 1 for all positive integers n.
But condition (2) states that f ( x ) = 1 does not hold for infinitely many x, so f ( p ) ≥ 2 . f ( 3 0 ) = f ( 2 ) + f ( 1 5 ) − 1 = f ( 2 ) + f ( 3 ) + f ( 5 ) − 2 = 4 , so f ( 2 ) + f ( 3 ) + f ( 5 ) = 6 . This means that 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 ) = 1 1 .
The given condtion 1 imply for all positive integers x 1 , x 2 ⋯ , 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 ) , which we can have f ( 1 4 4 0 0 ) = f ( 2 6 ⋅ 3 2 ⋅ 5 2 ) = 6 f ( 2 ) + 2 f ( 3 ) + 2 f ( 5 ) − 1 1 . It suffices to determine the value of f ( 2 ) , f ( 3 ) , f ( 5 ) .
Lemma: f ( n ) ≥ 2 for all n = 1 .
If there exist n = 1 such that 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 for all k , condraticts condition 2.
Given f ( 3 0 ) = 4 , then f ( 2 ) + f ( 1 5 ) = 5 , f ( 3 ) + f ( 1 0 ) = 5 , f ( 5 ) + f ( 6 ) = 5 . This imply f ( 2 ) , f ( 3 ) , f ( 5 ) , f ( 6 ) are either 2 or 3. However, f ( 2 ) + f ( 3 ) = f ( 6 ) − 1 , and f ( 6 ) is either 2 or 3, we have f ( 2 ) = f ( 3 ) = 2 . So f ( 6 ) = 3 ⇒ f ( 5 ) = 2 .
So f ( 1 4 4 0 0 ) = 6 f ( 2 ) + 2 f ( 3 ) + 2 f ( 5 ) − 1 1 = 1 1 .
Problem Loading...
Note Loading...
Set Loading...
First, we can simplify the number 1 4 4 0 0 into 3 0 ∗ 4 8 0 . Then, by using rule number 1, we can make such equation: f ( 1 4 4 0 0 0 ) = f ( 3 0 ) + f ( 4 8 0 ) − 1 Then, since 4 8 0 is 3 0 ∗ 1 6 , with using the first and third rule, we can write previous equation into f ( 1 4 4 0 0 ) = f ( 3 0 ) + ( f ( 3 0 ) + f ( 1 6 ) − 1 ) − 1 = f ( 1 6 ) + 2 f ( 3 0 ) − 2 = f ( 1 6 ) + 6 = 2 f ( 4 ) − 1 + 6 = 4 ( 2 ) − 3 + 6 = 4 f ( 2 ) + 3 Then, let's see the significance of the rule number 2. Let's assume that any prime number, p , has a property that f ( p ) = 1 Then, f ( p 2 ) = 2 f ( p ) − 1 = 1 f ( p 4 ) = 2 f ( p 2 ) − 1 = 1 . . . so the value of f ( p 2 n ) 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 Then, let's go back to rule three. We can simplify f ( 3 0 ) into such equation: f ( 3 0 ) = f ( 6 ) + f ( 5 ) − 1 = f ( 2 ) + f ( 3 ) + f ( 5 ) − 2 = 4 Then, f ( 2 ) + f ( 3 ) + f ( 5 ) = 6 And since 2 , 3 , 5 are all prime numbers, 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 Therefore, by plugging f ( 2 ) = 2 to the previous equation, f ( 1 4 4 0 0 ) = 8 + 3 = 1 1