Tuesday, November 4, 2014

2014/99 ) find the 50th smallest number which is coprime to 987

First we need to factor 987
987 = 3 * 329 = 3 * 7 * 47

to find a number which is coprime to 987 it should be co-prime to 3,7, and 47

now 1 is not coprime to any number so we need to find the 51st number which is  not divisible by 3 7 or 47

for x the numbers below or same as not divisible by 3 7 and 47 are

$f(x) =x-\lfloor\dfrac{x}{3}\rfloor-\lfloor\dfrac{x}{7}\rfloor-\lfloor\dfrac{x}{47}\rfloor+\lfloor\dfrac{x}{3*7}\rfloor+\lfloor\dfrac{x}{3* 47}\rfloor+\lfloor\dfrac{x}{7*47}\rfloor- \lfloor\dfrac{x}{3 * 7 * 47}\rfloor$

or $f(x) =x-\lfloor\dfrac{x}{3}\rfloor-\lfloor\dfrac{x}{7}\rfloor-\lfloor\dfrac{x}{47}\rfloor+\lfloor\dfrac{x}{21}\rfloor+\lfloor\dfrac{x}{141}\rfloor+\lfloor\dfrac{x}{329}\rfloor- \lfloor\dfrac{x}{987}\rfloor$

or $f(x) =x-\lfloor\dfrac{x}{3}\rfloor-\lfloor\dfrac{x}{7}\rfloor+\lfloor\dfrac{x}{21}\rfloor-\lfloor\dfrac{x}{47}\rfloor+\lfloor\dfrac{x}{141}\rfloor+\lfloor\dfrac{x}{329}\rfloor- \lfloor\dfrac{x}{987}\rfloor$


for estimating we take $x-\dfrac{x}{3}=\dfrac{2x}{3}=51$ or x = 76 ( rounded)

so f (x) = 76  - 25 - 10 + 3 = 44
we are falling short by 7

so we add 11 as it is 7 * 3/2 rounded

so we get x = 87 but as 87 is not coprime we take 88

f(88) = 88 - 29 - 12 + 4 - 1 = 50

so we take next number 89 which coprime

so x = 89  is the ans.

No comments: