# Limit of an interesting sequence

• Nov 4th 2010, 04:39 PM
Drexel28
Limit of an interesting sequence
Problem: Fix $\displaystyle n_0\in\mathbb{N}$ and let $\displaystyle E_n=\left\{m\leqslant n:(m,n_0)=1\right\}$ (i.e. the set of all $\displaystyle m\leqslant n$ where $\displaystyle m$ and $\displaystyle n_0$ are coprime). Then, define $\displaystyle a_n=\text{card }E_n$. Compute $\displaystyle \displaystyle \lim_{n\to\infty}\frac{a_n}{n}$.

Remark: I recently solved this problem on my blog, if you have seen it I would ask you refrain from answering.
• Nov 4th 2010, 04:43 PM
Also sprach Zarathustra
What is card? :)
• Nov 4th 2010, 04:50 PM
Drexel28
Quote:

Originally Posted by Also sprach Zarathustra
What is card? :)

Cardinality :)
• Nov 4th 2010, 05:48 PM
Bruno J.
Quote:

Originally Posted by Drexel28
Problem: Fix $\displaystyle n_0\in\mathbb{N}$ and let $\displaystyle E_n=\left\{m\leqslant n:(m,n_0)\right\}$ (i.e. the set of all $\displaystyle m\leqslant n$ where $\displaystyle m$ and $\displaystyle n_0$ are coprime). Then, define $\displaystyle a_n=\text{card }E_n$. Compute $\displaystyle \displaystyle \lim_{n\to\infty}\frac{a_n}{n}$.

Remark: I recently solved this problem on my blog, if you have seen it I would ask you refrain from answering.

I guess you mean $\displaystyle E_n=\left\{m\leqslant n:(m,n_0)=1\right\}$.

Isn't it just the product of the $\displaystyle (1-1/p)$ where $\displaystyle p$ ranges over the prime divisors of $\displaystyle n$, i.e. the proportion of integers relatively prime to $\displaystyle n_0$?
• Nov 4th 2010, 05:51 PM
Drexel28
Quote:

Originally Posted by Bruno J.
I guess you mean $\displaystyle E_n=\left\{m\leqslant n:(m,n_0)=1\right\}$.

Isn't it just the product of the $\displaystyle (1-1/p)$ where $\displaystyle p$ ranges over the prime divisors of $\displaystyle n$, i.e. the proportion of integers relatively prime to $\displaystyle n$?

Yes, that is what I mean. And I don't know, is it? >:]
• Nov 4th 2010, 05:52 PM
Bruno J.
Welcome back on MHF by the way :)
• Nov 4th 2010, 05:52 PM
Bruno J.
Quote:

Originally Posted by Drexel28
Yes, that is what I mean. And I don't know, is it? >:]

Yes, it is. This is barely a challenge problem! :) (*with $\displaystyle n_0$ instead of $\displaystyle n$ :) )
• Nov 4th 2010, 06:14 PM
Drexel28
Quote:

Originally Posted by Bruno J.
Yes, it is. This is barely a challenge problem! :) (*with $\displaystyle n_0$ instead of $\displaystyle n$ :) )

Ah, ****. My bad then. You see, the one subject I am truly ignorant of is number theory. That said, the way I devised of doing it was probably much more difficult than the number theoretic approach. What I did was (sketch):

Spoiler:
If $\displaystyle n_0=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ then $\displaystyle (m,n_0)\ne1 \Leftrightarrow p_1\mid m\text{ or }\cdots\text{ or }p_k\mid m$. Thus, if $\displaystyle A_{j,n}=\left\{m\leqslant n:p_j\mid m\right\}$ we see that

$\displaystyle [n]=E_n\sqcup\left(A_{1,n}\cup\cdots\cup A_{k,n}\right)$

where the square cup just means that $\displaystyle \left\{E_n,A_{1,n}\cup\cdots\cup A_{k,n}\right\}$ forms a partition of $\displaystyle [n]$. Thus, $\displaystyle a_n=n-\left|A_{1,n}\cup\cdots\cup A_{k,n}\right|$. But, by the inclusion exclusion principle

$\displaystyle \displaystyle \left|A_{1,n}\cup\cdots\cup A_{k,n}\right|=\sum_{j=1}^{k}(-1)^{j+1}\sum_{S\in S_j}\left|\bigcap_{s\in S}A_{s,n}\right|$

where $\displaystyle S_j=\left\{S\subseteq [k]:|S|=j\right\}$. Thus, noticing that any subcollection of $\displaystyle \{p_1,\cdots,p_k\}$ is a family of coprime numbers we see that

$\displaystyle \displaystyle \bigcap_{s\in S}A_{s,n}=\left\{m\leqslant n:p_s\mid m\text{ for all }s\in S\right\}=\left\{m\leqslant n:\prod_{s\in S}p_s\mid m\right\}$

From where simple reasoning leads us to

$\displaystyle \displaystyle\left|\bigcap_{s\in S}A_{s,n}\right|=\left\lfloor n\left(\prod_{s\in S}p_s\right)^{-1}\right\rfloor$

Thus,

$\displaystyle \displaystyle a_n=n-\sum_{j=1}^{k}(-1)^{j+1}\sum_{S\in S_j}\left\lfloor n\left(\prod_{s\in S}p_s\right)^{-1}\right\rfloor$

From where it quickly follows that

$\displaystyle \displaystyle \lim_{n\to\infty}\frac{a_n}{n}=1-\sum_{j=1}^{k}(-1)^{j+1}\sum_{S\in S_j}\left(\prod_{s\in S}p_s\right)^{-1}$

At least we know now that

$\displaystyle \displaystyle \prod_{j=1}^{k}\left(1-\frac{1}{p_j}\right)=1-\sum_{j=1}^{k}(-1)^{j+1}\sum_{S\in S_j}\left(\prod_{s\in S}p_s\right)^{-1}$
:)
• Nov 4th 2010, 06:38 PM
Drexel28
Quote:

Originally Posted by Bruno J.
Yes, it is. This is barely a challenge problem! :) (*with $\displaystyle n_0$ instead of $\displaystyle n$ :) )

OH MY GOD! Is the number theoretic way to do it this:

Spoiler:
Let $\displaystyle n_0=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$

Notice that $\displaystyle (m,n_0)=1\Leftrightarrow (m+n_0\ell,n_0)=1$. Thus, one can easily see that $\displaystyle E_{n_0(n+1)}=E_{nn_0}\cup\left\{k+n_0n:k\in E_{n_0}\right\}$. It easily follows then by induction that $\displaystyle a_{nn_0}=na_{n_0}$. But, evidently by definition $\displaystyle a_{n_0}=\varphi(n_0)$. Thus, $\displaystyle a_{nn_0}=n\varphi(n_0)$. So, notice that $\displaystyle a_n$ is increasing since $\displaystyle E_n\subseteq E_{n+1}$. Then, if $\displaystyle \gamma_{n_0}$ denotes reduction $\displaystyle \text{ mod }n_0$ that

$\displaystyle a_{n-\gamma_{n_0}(n)}\leqslant a_n\leqslant a_{n+n_0-\gamma_{n_0}(n)}$

But, notice that since $\displaystyle n_0\mid n-\gamma_{n_0}(n),n+n_0-\gamma_{n_0}(n)$ that $\displaystyle \frac{n_0-\gamma_{n_0}(n)}{n_0},\frac{n+n_0-\gamma_{n_0}(n)}{n_0}$ are both integers. Thus, our previous discussion applies and tells us that

$\displaystyle \displaystyle a_{n-\gamma_{n_0}(n)}=a_{n_0\left[\frac{n-\gamma_{n_0}(n)}{n_0}\right]}=\varphi(n_0)\frac{n-\gamma_{n_0}}{n_0}$

and

$\displaystyle \displaystyle a_{n+n_0-\gamma_{n_0}(n_0)}=a_{n-0\left[\frac{n+n_0-\gamma_{n_0}(n)}{n_0}\right]}=\varphi(n_0)\left[\frac{n+n_0-\gamma_{n_0}(n)}{n_0}\right]$

Notice then though that clearly

$\displaystyle \displaystyle \lim_{n\to\infty}\frac{\varphi(n_0)}{n}\left[\frac{n-\gamma_{n_0}(n)}{n_0}\right]=\lim_{n\to\infty}\frac{\varphi(n_0)}{n}\left[\frac{n+n_0-\gamma_{n_0}(n)}{n_0}\right]=\frac{\varphi(n_0)}{n_0}$

So, that by the squeeze theorem it follows that

$\displaystyle \displaystyle \lim_{n\to\infty}\frac{a_n}{n}=\frac{\varphi(n_0)} {n_0}=\frac{1}{n_0}\left(n_0\prod_{j=1}^{k}\left(1-\frac{1}{p_j}\right)\right)=\prod_{j=1}^{k}\left(1-\frac{1}{p_j}\right)$

My mind is blown.