## National Canadian Math League 1979 Problem

Posted: April 17, 2019 in Mathematics

Here is the problem.

In triangle ABC, AC = 18, and “D” is the point on AC for which AD = 5. Perpendiculars drawn from “D” to AB and BC have lengths of 4 and 5 respectively. Find the area of triangle ABC.

Suggested Solution.

By similar triangles,

$\displaystyle \frac{a}{c}=\frac34 \quad\text{ and }\quad \frac{b}{c}=\frac{12}{5}$

$\displaystyle \therefore a+b=\frac34 c + \frac{12}{5} c = 18$

hence,

$\displaystyle c = \frac{40}7$

Therefore, the area of triangle ABC is

$\displaystyle \frac{40}{7} \cdot \frac{18}{2} = \frac{360}{7}$

## An extremely good approximation of the Euler number e using only the digits 1-9

Posted: January 15, 2019 in Mathematics

The Euler number, not to confuse with the Euler constant 0.5772156649… , is the irrational number e. It is approximately equal to 2.7182818284…, and it is exactly equal to

$\displaystyle \lim_{n\to\infty} \left(1+\frac{1}{n}\right)^{n} \quad\text{ or }\quad \sum_{n=0}^\infty \frac{1}{n!}$

Remarkably in around 2004, Richard Sabey gave an extremely accurate approximation to the Euler number,

$\displaystyle e \approx (1+9^{-4^{7\cdot6}})^{3^{2^{85}}}$

which uses the digits 1 to 9 exactly once and it is accurate to around $1.8 \times 10^{25}$ digits.

## Finding a Triangular Number that is Twice Another Triangular Number

Posted: January 8, 2019 in Mathematics

So here is the problem.

First of all, we need to know what a triangular number (aka triangle number) is. A triangular number is the number count of dots which forms an equilateral triangle such as the diagram below.

Or basically the nth triangular number is the sum of the natural numbers from 1 to n. Some people will define the zeroth triangular number as zero. And the formula for the nth triangular number can be easily defined as the following.

$T_n = \dfrac{n(n+1)}{2}$

An interesting fact about triangular number is that the number 666 is one of them. Why? because 666 = 2 · 3 · 3 · 37 = 18 · 37. which is 36 · 37 / 2, so 666 is the 36th triangular number. And if you switch the number 36 to 63. The 63rd triangular number is 2016. That’s why I want to write something about triangular number three years ago but I didn’t have the time back then too busy taking care of my baby girl. Anyway let’s go back to what I want to do today. I want to find two triangular numbers such that one is twice another one. Since the devil number 666 is one of them, let’s list out all triangular numbers up to 666.

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, 666, …

At first glance, the pair of 3 and 6 stands out right away. Now the question is can we find another pair? Without much trouble, 105 and 210 can be picked out quite easily from the above list. Can we find more? Consider the following. For natural number m and n,

$T_m = 2T_n$

$\dfrac{m(m+1)}{2} = n(n+1)$

Multiplied both sides by 8,

$4m(m+1) = 8n(n+1)$

$4m^2 + 4m + 1 + 1 = 8n^2 + 8n + 2$

$(2m+1)^2 + 1 = 2(2n+1)^2$

Let $x = 2m+1$ and $y = 2n+1$, we have

$x^2 - 2y^2 = -1$

which is a classical Pell’s equation of the form $x^2 - Dy^2 = -1$. Since it is negative one, some people prefer to call it the negative Pell’s equation or the anti-Pell’s equation. To solve this equation, we can use continued fraction. I am not going to explain what continued fraction is because that will be too long and one can always find the explanation on Wikipedia or in any elementary number theory books. Maybe later when I have the mood I will write something on continued fraction coz I think continued fraction is a better way to represent a real number than the decimal expansion representation we are normally using. For instance, the number 1/3 can not be expressed as a terminating decimal but in continued fraction it can be written as [0; 3]. For irrational number such as root 2, it is approximately equal to 1.414213562… which I need to use a calculator to evaluate plus the decimals are non-repeating. But root 2 can be written as an exact form by using continued fraction with a repeating pattern [1;2,2,2,2,2, …].

Anyway let me solve the anti-Pell’s equation

$x^2 - 2y^2 = -1$

First I need to find the continued fraction of root 2.

$\displaystyle \sqrt2 = 1 + \sqrt2 - 1 = 1 + \frac{1}{\sqrt2 + 1} = 1 + \frac{1}{2+\sqrt2-1} = 1+\frac{1}{2+\frac{1}{\sqrt2+1}}$

$= [1;2,2,\ldots] = [1;\overline{2}]$

Note that continued fraction is denoted as

$\displaystyle a_0 + \frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+\cdots}}} = [a_0;a_1,a_2,a_3,\ldots]$

So in our case here,

$a_0 = 1, \quad a_1 = a_2 = a_3 = \cdots = 2$

Next, we can find the kth convergent of root 2. The kth convergent of the continued fraction $[a_0; a_1, a_2, \ldots, a_n]$ has the value

$C_k = \dfrac{p_k}{q_k} \qquad 0 \leq k \leq n$

and the values of the numerators and denominators can be defined as follows.

$\begin{array}{ll} p_{-2} = 0 & q_{-2} = 1 \\ p_{-1} = 1 & q_{-1} = 0 \\ p_k = a_k p_{k-1} + p_{k-2} \qquad & q_k = a_k q_{k-1} + q_{k-2}\\ \text{for } k = 0, 1, 2, \ldots \end{array}$

It is straightforward to prove this by math induction.

To proceed further, we need the following theorem.

Theorem. Let $d$ be a positive integer that is not a perfect square. Let $p_k/q_k$ denote the kth convergent of the simple continued fraction of  $\sqrt{d}$. Let $n$ be the period length of this continued fraction. Then, when $n$ is even, the positive solutions of the Pell’s equation $x^2-dy^2=1$ are $x=p_{jn-1}, y=q_{jn-1}, j = 1,2,3,\ldots$, and the anti-Pell’s equation $x^2-dy^2=-1$ has no solution. When $n$ is odd, the positive solutions of the Pell’s equation $x^2-dy^2=1$ are $x = p_{2jn-1}, y=q_{2jn-1}, j=1,2,3,\ldots$, and the solutions of the anti-Pell’s equation $x^2-dy^2=-1$ are $x=p_{(2j-1)n-1}, y=q_{(2j-1)n-1}, j=1,2,3,\ldots$.

The proof is quite long so I am too lazy to type them all out.

Let me list out the numerators and the denominators of the kth convergent of the infinite simple continued fraction of $\sqrt{2}$ for $k=0,1,2,3, \ldots$ by using the recursive formula for $p_k$ and $q_k$ defined earlier.

$\begin{array}{ll} p_{-2} = 0 & q_{-2} = 1 \\ p_{-1} = 1 & q_{-1} = 0 \\ p_0 = 1\cdot1+0 = 1 & q_0 = 1\cdot0+1 = 1 \\ p_1 = 2\cdot1+1 = 3 & q_1 = 2\cdot1+0 = 2 \\ p_2 = 2\cdot3+1 = 7 & q_2 = 2\cdot2+1 = 5 \\ p_3 = 2\cdot7+3 = 17 & q_3 = 2\cdot5+2 = 12 \\ p_4 = 2\cdot17+7 = 41 & q_4 = 2\cdot12+5 = 29 \\ p_5 = 2\cdot41+17 = 99 & q_5 = 2\cdot29+12 = 70 \\ p_6 = 2\cdot99+41 = 239 & q_6 = 2\cdot70+29 = 169 \\ p_7 = 2\cdot239+99 = 577 & q_7 = 2\cdot169+70 = 408 \\ p_8 = 2\cdot577+239 = 1393 \qquad & q_8 = 2\cdot408+169 = 985 \end{array}$

Since $\sqrt2 = [1;\overline{2}]$, the period n = 1 is odd, then by the theorem, we have the index for p and q being equal to $(2j-1)(1)-1 = 2j-2 = 2(j-1), j=1,2,3,\ldots$ which are 0, 2, 4, 6, 8, …, all the even convergents. So the solutions are

$(x,y) = (1,1), (7,5), (41,29), (239, 169), (1393, 985), \ldots$

Since $x = 2m + 1$ and $y = 2n + 1$, then $m=\dfrac{x-1}{2}$ and $n=\dfrac{y-1}{2}$, hence,

$(m,n) = (0,0), (3,2), (20,14), (119, 84), (696, 492), \ldots$

The first pair (0,0) implies that zeroth triangular number is twice the zeroth triangular number (if you accept zero as the zeroth triangular number). And the rest are:

(3, 2) implies that 3rd triangular number is twice the 2nd triangular number.

(20, 14) implies that 20th triangular number is twice the 14th triangular number.

(119, 84) implies that 119th triangular number is twice the 84th triangular number.

(696, 492) implies that 696th triangular number is twice the 492nd triangular number.

etc.

In conclusion, since $\sqrt{2}$ is irrational and the infinite simple continued fraction of $\sqrt2$ is periodic, there are infinitely many kth convergents of $\sqrt2$. Therefore, there are infinitely many pairs of triangular numbers that one is twice another one.

QED.

## Happy New Year 2019

Posted: January 1, 2019 in Mathematics

I was in bed last night thinking about the number 2019. Obviously it is not a prime. Can I find a way to add up the numbers 1 to 9 (in the exact order) to get 2019? First of all, 2019 is divisible by 3. it’s a product of 3 and 673. So I can do this, 2019 = (1 + 2)(673).

It isn’t difficult to verify 673 a prime number. Now I have used the digits 1 and 2 and there are 7 left, they are 3, 4, 5, 6, 7, 8, 9. After a while of trying out different products, I can’t find 673 out of the remaining digits. So I try factorials and I found 6! = 720 is pretty close to 673, a difference of only 47. And 4 times 5 is 20 so I have 27 left to consider, which is great coz I know 7 + 8 + 9 = 3 times 8 which is 24 and with the remaining digit 3 I am done!

$(1+2)\times(-3-4\times5+6!-7-8-9)=2019$

HAPPY NEW YEAR !!!

Remark

Matt Parker has a YouTube video on 2019 and I think it is amazing that

$0^3+1^8+2^7-3^9+4^6+5^4+6^2+7^5+8^1+9^0=2019$

and here is the video

## Rule of 72

Posted: December 27, 2018 in Mathematics

People love money. Specially when the money gets double. So, coming up with an estimate of the time it takes to double the money helps an average person to manage their investment. However, the math to calculate the amount of time to double the money from an investment that yields a fix rate of return could be quite complex for some individuals. Fortunately, the Rule of 72 comes in handy for this purposes.

$\text{Time for Investment to Double} = \dfrac{72}{\text{Rate of Return}}$

For example, if a person invested a certain amount of money at a fixed annual interest rate of 9%, the Rule of 72 will give around 72 / 9 = 8 years for the investment to be doubled. Where the actual calculation should be log(2) / log(1.09) = 8.043, but it’s pretty damn close.

Let’s look at another example, you deposit $100 into a saving account with 4% p.a., the Rule of 72 says it will take about 72 / 4 = 18 years for your money to become$200. The actual calculation should be log(2) / log(1.04) = 17.67, again it’s close enough.

The Rule of 72 is very useful in situation like when calculators aren’t around because there is no way I can calculate log(2) / log(1.04) in my head but I can manage to compute 72 / 4 mentally.

The reason that this rule works is because of the following:

First, we are trying to find the linear approximation of $\log(1+r)$.

Let $f(x) = \log(x)$, then first order taylor series around $a=1$ would be

$f(x) \approx f(1) + f'(1)(x-1) = x-1$

hence,

$\log(x) \approx x-1, \quad x\approx 1$

or

$\log(1+r) \approx r, \quad r\approx0$

So, $2 = \left(1+\frac{r}{100}\right)^t$ becomes

$t = \dfrac{\log 2}{\log(1+r/100)} = \dfrac{\log 2}{r/100}\cdot\dfrac{r/100}{\log(1+r/100)} \approx \dfrac{100 \log 2}{r} \approx \dfrac{69.31}{r} \approx \dfrac{72}{r}$

The number 72 is chosen because in fact it is close to 69.31 and 72 has 12 divisors that is considered a lot. 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72 divide 72.

## Perfect Number & Mersenne Prime

Posted: December 25, 2018 in Mathematics

One of the interesting thing about Number Theory is that quite often a theorem or a conjecture is easy to be stated and yet it is hard to be proven. For example, a conjecture that there are infinitely many perfect numbers. To this date no one has ever proved it true or false. However it is believed to be true by many mathematicians. First of all, what is a perfect number? A perfect number is a positive integer such that the sum of all its proper divisors equal to the number itself. For instance, 6 is a perfect number since 1, 2, and 3 are the proper divisors of 6 and 6 = 1 + 2 + 3. The next perfect number would be 28 since 28 = 1 + 2 + 4 + 7 + 14. This has to be one of the oldest puzzles in the history of mathematics. Euclid (around 300 BC) had shown that when $2^k-1$ is prime, $2^{k-1}(2^k-1)$ is perfect. There is a special name for numbers in the form $2^k-1$. They are called the Mersenne Numbers, which is named after a French priest Marin Mersenne (1588 – 1648) who devoted a lot of his time and effort studying them. And whenever a Mersenne number is prime, it is called a Mersenne Prime. So there is a relationship between Mersenne Prime and Perfect Number. To be more accurate, when you find a Mersenne prime, you will find an even perfect number. It was proven by Euler around the 18th Century that all even perfect numbers must be in the form $2^{k-1}(2^k-1)$. Now, the proof is not really that difficult in today’s standard.

Euclid-Euler Theorem. For $k > 1$, if $2^k-1$ is prime, then $n = 2^{k-1}(2^k-1)$ is perfect. And every even perfect number is of this form.

Proof. Denote the sum of all divisors function as $\sigma$. Let $2^k-1$ be Mersenne Prime and $n = 2^{k-1}(2^k-1)$ be an integer. Since $(2^{k-1}, 2^k-1) = 1$ and $\sigma$ is multiplicative, we then have

$\sigma(n) = \sigma(2^{k-1}(2^k-1)) = \sigma(2^{k-1})\sigma(2^k-1)$

Since the factors of $2^{k-1}$ are $1, 2, 2^2, \ldots, 2^{k-1}$ and $2^k-1$ is Mersenne prime,

$\sigma(2^{k-1}) = 2^k-1 \quad\text{and}\quad \sigma(2^k-1) = 2^k$

$\therefore \sigma(n) = (2^k-1)2^k = 2n$

And this is exactly the definition of a perfect number.

To prove the converse, assume n is an even perfect number such as $n = 2^{k-1}(2a-1)$ where a and k are positive integers and $k\geq2$. Since $(2^{k-1}, 2a-1) = 1$, we have

$\sigma(n) = \sigma(2^{k-1}(2a-1)) = \sigma(2^{k-1})\sigma(2a-1) = (2^k-1)\sigma(2a-1)$

Since n is perfect, then

$\sigma(n) = 2n = 2\cdot 2^{k-1}(2a-1) = 2^k(2a-1)$

$\therefore 2^k(2a-1) = (2^k-1)\sigma(2a-1) \qquad (1)$

Hence, $2^k-1 \;|\; 2^k(2a-1)$, but $(2^k-1, 2^k)=1$, so $2^k-1 \;|\; 2a-1$, which means $2a-1 = (2^k-1)b$ for some integer b. Then equation (1) becomes

$2^k(2^k-1)b = (2^k-1)\sigma(2a-1)$

$2^kb = \sigma(2a-1)$

Since $2a-1$ and $b$ are both divisors of $2a-1$, we have

$2^kb = \sigma(2a-1) \geq (2a-1) + b = (2^k-1)b + b = 2^kb$

This forces the inequality to equality,

$\sigma(2a-1) = (2a-1) + b$

And this implies that $2a-1$ has only two divisors and so $2a-1$ must be prime and $b=1$. Therefore $2a-1 = (2^k-1)b = 2^k-1$ is a prime number, which completes the proof. QED.

So the problem of finding even perfect numbers boils down to the hunt for Mersenne primes. And I remember the last time I wrote the article on the largest known prime, the last greatest Mersenne prime was $2^{77232917}-1$. But now the record has been broken again. On December 7, 2018 the largest known prime (or Mersenne prime) is found to be

$2^{82589933}-1$

which makes the largest known perfect number to be

$2^{82589932}(2^{82589933}-1)$

which is 49,724,095 digits long!

## Proof of the Square of Standard Normal is a Chi-Square(1) Distribution

Posted: December 3, 2018 in Mathematics

Theorem. If $Z \sim N(0, 1)$, then $W = Z^2 \sim \chi^2(1)$.

Proof

The idea of the proof is to show that the pdf of random variable W is the same as the pdf of chi-square random variable with 1 degree of freedom, $\chi^2_1$. That is

$f_W(w) = \dfrac{1}{2^{1/2}\Gamma(1/2)}w^{1/2-1}e^{-w/2}, w>0$

So, our strategy is to find F(w), the cdf of W, and then differentiate it with respect to w to get f(w), the pdf of W.

Here we start,

$F_W(w) = P(W

$=P(|Z|<\sqrt{w}) = P(-\sqrt{w}

$= \displaystyle \int_{-\sqrt{w}}^{\sqrt{w}} \frac{1}{\sqrt{2\pi}} e^{-z^2/2} dz$

Now, since standard normal distribution is symmetric about zero. hence,

$F_W(w) = \displaystyle 2\int_0^{\sqrt{w}} \frac{1}{\sqrt{2\pi}} e^{-z^2/2} dz$

Now, differentiating F(w) with respect to w to get f(w).

$\displaystyle f_W(w) = F_W'(w) = \frac{d}{dw} 2\int_0^{\sqrt{w}} \frac{1}{\sqrt{2\pi}} e^{-z^2/2} dz$

Now, by the Fundamental Theorem of Calculus and chain rule, we get

$\displaystyle f_W(w) = \frac{2}{\sqrt{2\pi}} e^{-w/2}\cdot\frac{1}{2\sqrt{w}}$

$\displaystyle = \frac{1}{\sqrt{2\pi}} w^{-1/2} e^{-w/2}, \quad 0 < w < \infty$

Now since $\Gamma(\frac12) = \sqrt\pi$, we get

$f_W(w) = \dfrac{1}{2^{1/2}\Gamma(1/2)} w^{1/2-1}e^{-w/2}, w>0$

$\therefore W=Z^2 \sim \chi^2(1). \quad \square$