# Estimating the number of integers relatively prime to $6$ between $1$ and some integer $x$?

I am trying to understand the standard way to estimate the number of integers relatively prime to $6$ where we don't know which congruence class $x$ belongs to.

For a given $x$, if we know the congruence class, it is straight forward to determine the number of integers between $1$ and $x$ that are relatively prime to $6$.

If $x \equiv 0 \pmod 3$, the answer is $\frac{x}{3}$: i.e., between $1$ and $9$, there are $3$ that are relatively prime: $\{ 1, 5, 7\}$

If $x \equiv 1 \pmod 6$, the answer is $\frac{x+2}{3}$: ie., between $1$ and $7$, there are $3$.

If $x \equiv 2 \pmod 3$, the answer is $\frac{x+1}{3}$

if $x \equiv 4 \pmod 6$, the answer is $\frac{x-1}{3}$

What be the standard answer for $x$ where we don't know the congruence class?

Would we say between $\frac{x-1}{3}$ and $\frac{x+2}{3}$?

What would be the right way for any $x$ to estimate the number of integers relatively prime to $6$?

• An example estimate would be $\frac x3$ for large $x$, to highest order, with absolute error at most $\frac 23$. If you want a formula for the exact number there are ways of doing that. – Mark Bennet Nov 10 '15 at 21:27
• @LarryFreeman $x/3$ ...............no? – martin Nov 10 '15 at 21:27
• Hi @Martin, that would be incorrect betwen $1$ and $2$. The correct answer is $1$ but $\frac{2}{3}$ would not be correct. – Larry Freeman Nov 10 '15 at 21:31
• @LarryFreeman well, seq[nn_] := With[{aa = (ConstantArray[1, #] & /@ Table[3 + (-1)^n, {n, 0, Ceiling[nn/3]}])}, Take[Flatten[aa*Range@Length@aa], nn]] and then seq[50]gives sequence up to $50,$ as to defining it using correct mathematical notation, I will give it some thought... – martin Nov 10 '15 at 21:42
• One way of estimating the error is to use periodic functions like sixth roots of unity to the power $n$ - this will give an exact and algebraic expression. Other ways involve floor functions etc, which are simpler in some ways, but not in others. – Mark Bennet Nov 10 '15 at 21:43

The number of integers relatively prime to $6$ for each $x$ is given by the expression

$$\left\lfloor \frac{x-1}{6}\right\rfloor +\left\lfloor \frac{x+1}{6}\right\rfloor +1$$

which is clearly $\sim x/3.$

Check:

rp6[x_] := Floor[(x - 1)/6] + Floor[(x + 1)/6] + 1

{Length@Select[Range@#, GCD[#, 6] == 1 &] & /@ Range@40,
rp6@# & /@ Range@40} // ListLinePlot


Generalisation:

The number of integers relatively prime to $n$ for each $x$ is $\sim x \cdot \phi(n)/n,$ where $\phi$ is the Euler totient function.