Problem Solving

CSASHISHPANDAY wrote:If f(x)=(f(x−2))(f(x−1))(x)for x>0 and f(x)=1 for all x<1, what is the largest prime number that divides f(50)?

A) 7
B) 43
C) 47
D) 49
E) 53

Tough question - definitely 750+ level.

Here's one approach.

First let's examine a few values:

Since f(x) = 1 for all x < 1, we know that
f(-1) = 1
f(0) = 1

Keep going by using the fact that f(x) = [f(x−2)][f(x−1)][x]
f(1) = [f(-1)][f(0)][1] = [1][1][1] = 1
f(2) = [f(0)][f(1)][2] = [1][1][2] = 2
f(3) = [f(1)][f(2)][3] = [1][2][3] = 6
f(4) = [f(2)][f(3)][4] = [2][6][4] = 72
f(5) = [f(3)][f(4)][5] = [6][72][5] = 2160
etc.

At this point, we should recognize that f(50) is going to be HUGE!! So, we certainly don't want to calculate this value.
Instead, we should observe that each value of f(x) involves the product of numbers before it. For example, f(6) is the product of f(5), f(4) and 6. Likewise, f(7) is the product of f(6), f(5) and 7.
The important part of all of this is that each function value is primarily based on previous functions. So, the only "new" numbers that get included in the product are the blue ones.
So, the only way for a new prime number to creep into the product is when x = a prime number.
For example, the prime number 13 enters the product when we calculate the value of f(13)
And prime number 29 enters the product when we calculate the value of f(29)
And so on.
Since 47 is the biggest prime number among the integers from 1 to 50, 47 is the largest prime number that divides f(50)

Answer: C

Aside: the trap answer here is 49. Since 49 is not prime, it cannot be the correct answer.

Cheers,
Brent