# Find the thousandth number in the sequence of numbers relatively prime to $105$.

Suppose that all positive integers which are relatively prime to $$105$$ are arranged into a increasing sequence: $$a_1 , a_2 , a_3, . . . .$$ Evaluate $$a_{1000}$$

By inclusion exclusion principle I found the following equation:

$$n - \left( \left\lfloor \dfrac {n} {3} \right\rfloor + \left\lfloor \dfrac {n} {5} \right\rfloor + \left\lfloor \dfrac {n} {7} \right\rfloor \right) + \left( \left\lfloor \dfrac {n} {15} \right\rfloor + \left\lfloor \dfrac {n} {21} \right\rfloor + \left\lfloor \dfrac {n} {35} \right\rfloor \right) - \left\lfloor \dfrac {n} {105} \right\rfloor=1000$$

I tried to solve the equation by setting $$n=105k+r ; 0 \leq 0<105$$. But this method is so tiring and lengthy to solve. I thought to invoke inequalities like $$a-1 <\lfloor a \rfloor \leq a$$, but I couldn't do as the equation contains positive as well as negative terms .Please provide me any other method to solve such equations involving floor function. Any help would be appreciated.

• Well, I'd do it by ignoring the floor (getting something like $2187$) and searching near there.
– lulu
Sep 30 '19 at 11:25
• You already have a good formula there. All that's left to do is to do a binary search on it, and you'll have an algorithm that is pretty much as fast as possible Sep 30 '19 at 12:01
• @Sudix As the left-hand side evolves in a roughly linear fashion, one can do a lot better than pure binary search by using the secant method. Sep 30 '19 at 12:08
• I don't understand your equation. For $n=105$, I got 48. Mar 20 at 23:23

• Note that if $$\gcd(a,b)=1$$, then $$\gcd(a+b,b)=1$$

• There are $$48$$ numbers which are less than $$105$$ which are relatively prime to $$105$$, since $$\phi(105)=48$$. Let $$a_i$$ be the $$i$$-th number which is relatively prime to $$105$$. It is clear that $$a_{48}=104$$.

• Also the first $$104$$ numbers which are relatively prime are $$\{1,2,4,8,\ldots,104\}$$. The next $$48$$ numbers are $$\{1+105,2+105,4+105,\ldots,104+105\}$$. Thus you see that $$a_{96}=209$$.

Continue like this.

• In point 3, I think you mean "The first $48$" and "The next $48$", not $104$. Sep 30 '19 at 11:56
• Also, I think you meant $1,2,4,8,\ldots$, not $1,2,4,7,\ldots$. Sep 30 '19 at 12:44

I personally think this problem is easier to approach from a slightly more brute-force angle.

How many of the $$a_i$$ are below $$105$$? How many of them are between $$105$$ and $$210$$? How many are between $$210$$ and $$315$$? How many multiples of $$105$$ do you have to go before you have (close to) $$1000$$ terms? From there it's basically trial and error.

Alternate solution, taken from the comments above.

The left-hand side of your equation is roughly linear. So you can do a linear regression from basically any two $$n$$-values to find the solution to your equation. For instance, inserting $$n = 1$$ and $$n = 11$$ gives $$1$$ and $$5$$ respectively.

Straight-forward linear regression from these two values (draw the line going through the points $$(1, 1)$$ and $$(11, 5)$$, and see where that line hits $$y = 1000$$) says the two sides of the equation will be equal at $$n = 2498$$. Actually inserting this value into the left-hand side of your equation we get $$1142$$, which is closer, but still a bit off. (Using more sensible $$n$$-values, like $$n = 0$$ and $$n = 105$$ will, of course, give you a much better result.)

However, one more linear regression from $$n = 11$$ and $$n = 2498$$ basically gives you the solution.

The number of integers $$n \in \{1,2,3,\dots, 105\}$$ that are relatively prime to $$105$$ is

$$\phi(105) = \phi(3 \times 5 \times 7) = 2 \times 4 \times 6 = 48$$

We know that $$\gcd(105A + n, 105) = \gcd(n, 105)$$.

Since $$1000 = 20\times 48 + 40$$, we know that there are $$20 \times 48 = 960$$ numbers relatively prime to $$105$$ in the interval $$[1, 2100]$$ (where $$2100 = 20 \times 105$$).

$$86$$ is the $$40^{\text{th}}$$ number in that range that is relatively prime to $$105$$.

So the thousandth number relatively prime to $$105$$ is $$2100 + 86 = 2186$$.