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.

  • 2
    $\begingroup$ Well, I'd do it by ignoring the floor (getting something like $2187$) and searching near there. $\endgroup$
    – lulu
    Sep 30 '19 at 11:25
  • $\begingroup$ 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 $\endgroup$
    – Sudix
    Sep 30 '19 at 12:01
  • $\begingroup$ @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. $\endgroup$
    – Arthur
    Sep 30 '19 at 12:08
  • $\begingroup$ I don't understand your equation. For $n=105$, I got 48. $\endgroup$ 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.

  • 2
    $\begingroup$ In point 3, I think you mean "The first $48$" and "The next $48$", not $104$. $\endgroup$
    – Arthur
    Sep 30 '19 at 11:56
  • 1
    $\begingroup$ Also, I think you meant $1,2,4,8,\ldots$, not $1,2,4,7,\ldots$. $\endgroup$ 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.