5
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Well, I'd do it by ignoring the floor (getting something like $2187$) and searching near there. $\endgroup$ – lulu Sep 30 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 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 at 12:08
5
$\begingroup$
  • 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.

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

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.

$\endgroup$

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.