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

Question

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.

Answer 1

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.

Answer 2

• 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.

Answer 3

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$.