Abstract Nonsense

Crushing one theorem at a time

Neat Number Theory/Discrete Math Problem


Point of post: In this post I will discuss  the following simple problem:

” Let E_n=\left\{m\leqslant n:(m,15)=1\right\}, then define a_n=\left|E_n\right|. Compute \displaystyle \lim_{n\to\infty}\frac{a_n}{n}

where (\cdot,\cdot) stands for \text{g.c.d.}. We will solve this problem in two ways, the first of which is simple but the second of which generalizes to a much, much more general case which we will discuss in the next post.

Problem: Let E_n=\left\{m\leqslant n:(m,15)=1\right\}, then define a_n=\left|E_n\right|. Compute \displaystyle \lim_{n\to\infty}\frac{a_n}{n}.

Initial Proofs

Proof (1): Note first that \displaystyle \lim_{n\to\infty}\frac{a_n}{n} converges. To see this we first note that a_n is increasing since

E_n\subseteq E_{n+1} Next we recall the well known fact that

(k,15)=1\Leftrightarrow (15m+k,15)=1

So, in particular thus E_{15(n+1)}=E_{15n}\cup\left\{k+15n:k\in E_{15}\right\}. So, a_{15(n+1)}=a_{15n}+a_{15} and so by induction a_{15n}=na_{15} and since a_{15}=8 we may conclude that a_{15n}=8n. Thus, if \gamma_{15}(n) is defined as reduction \text{mod }nwe can see that

a_{n-\gamma_{15}(n)}\leqslant a_n\leqslant a_{n+15-\gamma_{15}(n)}

note though that since 15\mid n-\gamma_{15}(n),n+15-\gamma_{15n}(n) we  see that

\displaystyle \frac{n-\gamma_{15}(n)}{15}\quad \frac{n+15-\gamma_{15}(n)}{15}

are integers and so applying our above observation about a_{15m} we note that

a\displaystyle _{n-\gamma_{15}(n)}=a_{15\left[\frac{n-\gamma_{15}(n)}{15}\right]}=8\left[\frac{n-\gamma_{15}(n)}{15}\right]

and

\displaystyle a_{n+15-\gamma_{15}(n)}=a_{15\left[\frac{n+15-\gamma_{15}(n)}{15}\right]}=8\left[\frac{n+15-\gamma_{15}(n)}{15}\right]

so we may conclude that

\displaystyle \frac{8}{15}\left[1-\frac{\gamma_{15}(n)}{n}\right]\leqslant\frac{a_n}{n}\leqslant \frac{8}{15}\left[1+\frac{15-\gamma_{15}(n)}{n}\right]

and since \displaystyle \frac{\gamma_{15}(n)}{n},\frac{15-\gamma_{15}(n)}{n}\leqslant \frac{15}{n}. Thus, we may conclude by the Squeeze Theorem that

\displaystyle \lim_{n\to\infty}\frac{a_n}{n}=\frac{8}{15}

Proof (2): In this post we find explicitly the value of a_n and from there conclude. We begin by noting that

(m,15)\ne 1\Leftrightarrow 3\mid m\text{ or }3\mid n

thus, it clearly follows that if

A_n=\left\{m\leqslant n:3\mid m\right\}

and

B_n=\left\{m\leqslant n:5\mid n\right\}

that

[n]=E_n\sqcup\left(A_n\cup B_n\right)

(where \sqcup is merely notation for [n]=E_n\cup \left(A_n\cup B_n\right) and E_n\cap\left(A_n\cup B_n\right)=\varnothing, i.e. that \left\{E_n,A_n\cup B_n\right\} forms a partition of [n]). Thus,

n=\left|[n]\right|=\left|E_n\sqcup \left(A_n\cup B_n\right)\right|=\left|E_n\right|+\left|A_n\cup B_n\right|=a_n+\left|A_n+B_n\right|

so that

a_n=n-\left|A_n\cup B_n\right|

thus it suffices to compute \left|A_n\cup B_n\right|. To do this we recall the simple law that

\left|A_n\cup B_n\right|=\left|A_n\right|+\left|B_n\right|-\left|A_n\cap B_n\right|

Now, it is fairly obvious that

\displaystyle \left|A_n\right|=\left\lfloor\frac{n}{3}\right\rfloor

and

\displaystyle \left|B_n\right|=\left\lfloor \frac{n}{5}\right\rfloor

and since

A_n\cap B_n=\left\{m\leqslant n:3\mid m\text{ and }5\mid m\right\}=\left\{m\leqslant n:15\mid m\right\}

it follows that

\displaystyle \left|A_n\cap B_n\right|=\left\lfloor\frac{n}{15}\right\rfloor

Putting this all together we get that

\displaystyle a_n=n-\left|A_n\cup B_n\right|=n-\left\lfloor\frac{n}{3}\right\rfloor-\left\lfloor\frac{n}{5}\right\rfloor+\left\lfloor\frac{n}{15}\right\rfloor

so that

\displaystyle \frac{a_n}{n}=1-\frac{1}{n}\left(\left\lfloor \frac{n}{3}\right\rfloor+\left\lfloor\frac{n}{5}\right\rfloor-\left\lfloor\frac{n}{15}\right\rfloor\right)

But, evidently since in general x-1\leqslant\lfloor x\rfloor\leqslant x

\displaystyle 1-\frac{1}{3}-\frac{1}{5}-\frac{1}{15}-\frac{1}{n}\leqslant \frac{1}{n}\left(\left\lfloor\frac{n}{3}\right\rfloor+\left\lfloor\frac{n}{5}\right\rfloor-\left\lfloor\frac{1}{15}\right\rfloor\right)\leqslant 1-\frac{1}{3}-\frac{1}{3}+\frac{1}{15}+\frac{2}{n}

we may conclude by the Squeeze Theorem that

\displaystyle \lim_{n\to\infty}\frac{a_n}{n}=1-\frac{1}{3}-\frac{1}{5}+\frac{1}{15}=\frac{8}{15}.

Advertisements

November 4, 2010 - Posted by | Fun Problems, Uncategorized | , , ,

2 Comments »

  1. […] Point of post: This is a continuation of this post. […]

    Pingback by Neat Number Theory/Discrete Math Problem (Pt. II) « Abstract Nonsense | November 4, 2010 | Reply

  2. […] for some odd reason, I thought I’d also generalize the methodology in the first proof of this post to the general form and give another alternate proof. These methods have both their pros and cons. […]

    Pingback by Neat Number Theory/Discrete Math Problem (Pt. III) « Abstract Nonsense | November 6, 2010 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: