Has anyone seen the movie "The Kingdom of Heaven"? Besides the thing that the movie is very well made, the character of Salahuddin acted very well in that movie. I liked the character so much that I got tempted to keep the name of this blog after it.

Tuesday, August 9, 2011

Divisors problem (one more)

Here is a problem w.r.t divisors: For a given positive integers B and X find the number of positive integers N such that number N*X has at least one divisor D such that N < D <= B (Courtesy: www.codechef.com).

The number N, can be represented as a function of B and X, namely f(B, X). Prove the following:

f(B, 1) = 0
f(B, 2) = Floor(B / 2)
f(B, 3) = 2 * Floor(B / 3) - Floor(B / 6)
f(B, 4) = Floor(B / 2) + Floor(B / 4) - Floor(B / 6)
f(B, 5) = 4 * Floor(B / 5) - Floor(B / 10) - Floor((B + Floor(B / 15)) / 8) - Floor((B + Floor(B / 20)) / 7)

No comments:

Post a Comment