A Brain Teaser

May 22, 2023May 23, 2023 / Michael Xue / Leave a comment

Problem

Find the smallest integer such that if the digit on the extreme left is transferred to the extreme right, the new number so formed is one and a half times the original number.

Solution

We express the unknown number as $\sum\limits_{i=0}^{n}a_i 10^i$ . That is,

$a_n10^n + \sum\limits_{i=0}^{n-1}a_i\cdot 10^i$ .

When we have transferred the digit, the new number is

$10 \sum\limits_{i=0}^{n-1}a_i 10^i + a_n$ .

“the new number so formed is one and a half times the original number” means

$10 \sum\limits_{i=0}^{n-1}a_i 10^i + a_n = 1.5\sum\limits_{i=0}^{n}a_i\cdot 10^i$

It follows that

$10 \sum\limits_{i=0}^{n}a_i 10^i - a_n10^n + a_n = 1.5\sum\limits_{i=0}^{n}a_i\cdot 10^i$ ,

$8.5\sum\limits_{i=0}^{n}a_i 10^i = a_n 10^n -a_n$ ,

$\sum\limits_{i=0}^{n}a_i 10^i = \frac{a_n (10^n -1)}{8.5}$ ,

$\sum\limits_{i=0}^{n} a_i 10^i = \frac{a_n (10^n -1)\cdot 10}{85}$ .

To make it as small as possible, we let

$a_n=1$ .

i.e.;

$\sum\limits_{i=0}^{n} a_i 10^i = \frac{(10^n -1)\cdot 10}{85}$ .

It yields an integer (see Fig. 1) when $n=16$ :

$1176470588235294.$

Fig. 1

The result is verified below:

Fig. 2

The Russian multiplication method

May 18, 2023May 22, 2023 / Michael Xue / Leave a comment

The Russian multiplication method is an alternative algorithm for multiplying two numbers. It states:

[1] Place two numbers to be multiplied at the head of two columns.

[2] The number in the first column is continuously divided by 2, ignoring reminders, until the number 1 is reached. The number in the second column is continuously doubled, until it reaches the last row of the first column.

[3] Now cross out all numbers in the second column that are in line with even numbers from the first column.

[4] The product is given by adding the remaining numbers in the second column.

For example, to multiply 158 and 39,

The result is 78 + 156 + 312 + 624 + 4992 = 6162.

To understand this algorithm, we let

$A=\sum\limits_{i=0}^{n}a_i 2^i, B=\sum\limits_{j=0}^{m}b_j 2^j$

where $a_n = b_m =1$ ; all other $a_i$ s and $b_j$ s are either $0$ or $1$ .

As a result,

$A\cdot B=\left(\sum\limits_{i=0}^{n}a_i 2^i\right) \cdot \left(\sum\limits_{j=0}^{m}b_j 2^j\right)$

$=\sum\limits_{i=0}^{n}\left(a_i2^i\sum\limits_{j=0}^{m}b_j2^j\right)$

$=\sum\limits_{i=0}^{n}\left(a_i\sum\limits_{j=0}^{m}b_j2^{i+j}\right)$

$= a_0\sum\limits_{j=0}^{m}b_j2^j + a_1\sum\limits_{j=0}^{m}b_j2^{j+1}+ \cdots + \underline{a_k\sum\limits_{j=0}^{m}b_j2^{j+k}} + \cdots + a_n\sum\limits_{j=0}^{m}b_j2^{j+n}\quad\quad(1)$

After depicting $A \cdot B$ by the Russian multiplication method in Fig. 1:

${\begin{array}{c|c} \hline \sum\limits_{i=1}^{n}a_i 2^i + a_0 & \sum\limits_{j=0}^{m}b_j 2^{j+1} \\ \hline \sum\limits_{i=2}^{n}a_i 2^{i-1} + a_1 & \sum\limits_{j=0}^{m}b_j 2^{j+2} \\ \hline \ddots & \ddots \\ \hline\sum\limits_{i=k}^{n}a_i 2^{i-k} + a_k & \sum\limits_{j=0}^{m}b_j 2^{j+k} \\ \hline \ddots & \ddots \\ \hline 1\cdot2 + a_{n-1}& \sum\limits_{j=0}^{m}b_j 2^{j+(n-1)}\\ \hline 1 & \sum\limits_{j=0}^{m}b_j 2^{j+n} \\ \hline\end{array}}.$

Fig. 1

we see for a given $k$ , if $\sum\limits_{i=k}^{n}a_i 2^{i-k} + a_k$ is an even number, then $a_k$ must be $0.$ Consequently,

$\underline{a_k\sum\limits_{j=0}^{m}b_j2^{j+k}} = 0\cdot \sum\limits_{j=0}^{m}b_j2^{j+k}=0.$

It means on any given row, if the first column contains an even number, the second column will take no part in summation $(1)$ . This is equivalent to “cross out all numbers in the second column that are in line with even numbers from the first column”. Adding the remaining numbers in the second column then gives $A\cdot B.$

See also “Schematic Integration by Parts“.

This, therefore, is mathematics: she gives life to her own discoveries; she awakens the mind and purifies the intellect; she brings light to our intrinsic ideas; she abolishes the oblivion and ignorance which are ours by birth.

– Proclus , a Greek commentator of the 5th centry

Schematic Integration by Parts

May 1, 2023May 18, 2023 / Michael Xue / Leave a comment

By definition, $\displaystyle\int f g\;dx$ can be expressed as

$\displaystyle \int f \left(\int g\; dx \right)' \;dx.$

Applying integration by parts,

$\displaystyle\int fg\;dx$

$\overset{g_1=\int g\;dx }{=} \displaystyle\int f g_1'\;dx = f g_1 - \underline{\int f' g_1\;dx}$

$\overset{g_2 = \int g_1\;dx}{=} f g_1 -\left(f' g_2 -\displaystyle \int f'' g_2\;dx\right)$

$= f g_1 -f' g_2 + \displaystyle \int f'' g_2\;dx$

$\overset{g_3 = \int g_2\;dx}{=} f g_1 -f' g_2 + \left(f'' g_3 - \displaystyle\int f^{(3)} g_3\;dx\right)$

$\ddots$

$= fg_1 - f'g_2 + f^{''}g_3 + \dots + (-1)^{n-1} f^{(n-1)} g_n +(-1)^n\displaystyle\int f^{n}g_n\;dx$

$= \sum\limits_{i=1}^{n}(-1)^{i-1}f^{i-1}g_i + (-1)^n\displaystyle\int f^{(n)}g_n\;dx$

Note a pattern has emerged – namely,

$\displaystyle \int fg\;dx = fg_1 - f'g_2 + f^{''}g_3 + \dots + (-1)^{n-1} f^{(n-1)} g_n +(-1)^n\displaystyle\int f^{n}g_n\;dx$

holds for all $n$ ‘s (see $(*)$ ). Consequently, it introduces a schematic method of evaluating certain integrals. For example, to determine

$I_1 = \displaystyle \int x^5 \sin(x)\;dx,$

let $f=x^5$ and $g=\sin(x).$ Write $f'$ in one column and $\displaystyle\int g\; dx$ in another, continuing to the row in which $f^{(n)} = 0:$

$\displaystyle I_1=$ $-x^5\cos(x) + 5x^4\sin(x)+20x^3\cos(x)-60x^2\sin(x)-120x\cos(x)+120\sin(x)$

To evaluate

$I_2 = \displaystyle\int e^{ax}\cos(bx)\;dx,$

let $f = e^{ax}$ and $g=\sin(bx).$ Proceed as before, but continuing to the row in which the $f_n g_n$ is a constant multiple of $I_2$ ‘s integrand:

$I_2 = e^{ax}\cdot\frac{\sin(bx)}{b} + ae^{ax}\cdot\frac{cos(bx)}{b^2} - \frac{a^2}{b^2}I_2.$

Solving for $I_2,$ we obtain

$I_2 = \frac{e^{ax}(b\cdot\sin(bx)+a\cdot\cos(bx))}{a^2+b^2}$

Prove:

$\forall n \in \mathbb{N}, \displaystyle \int fg\;dx = \sum\limits_{i=1}^{n}(-1)^{i-1}f^{i-1}g_i + (-1)^n\displaystyle\int f^{(n)}g_n\;dx\quad\quad\quad(*)$

where $f^{(0)} = f, f^{(n)} = (f^{(n-1)})'; g_{0} = g, g_{n} = \displaystyle\int g_{n-1}\;dx.$

proof

When $n=1,$ the right-hand side of $(*)$ is

$\sum\limits_{i=1}^{1}(-1)^{i-1}f^{i-1}g_i + (-1)^1\displaystyle\int f^{(1)}g_1\;dx$

$= f^{(0)} g_1 - \displaystyle\int f^{(1)}g_1\;dx$

$= f\displaystyle\int g_0\;dx - \int f' \left(\int g_0\;dx \right)\;dx$

$= \displaystyle\int f \left(\int g_0\;dx\right)'\;dx$

$= \displaystyle\int f g\;dx$

which is the left-hand side of $(*).$

Suppose when $n = k,$

$\displaystyle\int f\cdot g\;dx = \sum\limits_{i=1}^{k}(-1)^{i-1}f^{i-1}g_i + (-1)^k\displaystyle\int f^{(k)}g_k\;dx.$

Then

$\displaystyle\int f\cdot g\;dx = \sum\limits_{i=1}^{k}(-1)^{i-1} f^{(i-1)}g_i +(-1)^k\displaystyle\int f^{(k)}(g_{k+1})'\; dx$

$= \sum\limits_{i=1}^{k}(-1)^{i-1} f^{(i-1)}g_i +(-1)^k \left(f^{(k)}g_{k+1} - \displaystyle\int f^{(k+1)}g_{k+1}\;dx\right)$

$= \sum\limits_{i=1}^{k}(-1)^{i-1} f^{(i-1)}g_i +(-1)^k f^{(k)}g_{k+1} +(-1)^{k+1}\displaystyle\int f^{(k+1)}g_{k+1}\;dx$

$=\underbrace{\sum\limits_{i=1}^{k}(-1)^{i-1} f^{(i-1)}g_i +(-1)^{(k+1-1)} f^{(k+1-1)}g_{k+1}}_{\sum\limits_{i=1}^{k+1}(-1)^{i-1} f^{(i-1)}g_i} +(-1)^{k+1}\displaystyle\int f^{(k+1)}g_{k+1}\;dx$

$=\sum\limits_{i=1}^{k+1}(-1)^{i-1} f^{(i-1)}g_i + (-1)^{k+1}\displaystyle\int f^{(k+1)}g_{k+1}\;dx.$

And so, when $n=k+1,$

$\displaystyle \int f g\;dx =\sum\limits_{i=1}^{k+1}(-1)^{i-1} f^{(i-1)}g_i + (-1)^{k+1}\displaystyle\int f^{(k+1)}g_{k+1}\;dx.$

See also “The Russian multiplication method“.

Exercise-1 Evaluate $I_3 = \displaystyle\int xe^x\cos(2x)\;dx$ by the schematic method (hint: $f=xe^{x}, g=\cos(2x)$ and $I_2$ )