An elegant result

Feb 12, 2020

Let $A, M$ be two positive integers such that $A < M$.

Define the sequence $\{c_n\}$ satisfies $0 \le c_n < M$ and $c_n \equiv A n (\mathrm{mod}\ M)$ for $n \ge 1$.

Moreover let $n_1 = 1$ and if $c_{n_k} > 0$, we define

$$ n_{k + 1} = \min \{n: n > n_k, c_n < c_{n_k} \}. $$

Hence $A n_{k+1}$ is the first positive multiple of $A$ that yields a residual less than $c_{n_k}$.

Following theorem shows the recurrence relation of the sequence $\{n_k\}$.

Theorem 1

Suppose that $c_{n_{k+1}} > 0$, then we have

$$\begin{align} n_{k+2} = \left\lceil \frac{c_{n_k}}{c_{n_{k+1}}} \right\rceil n_{k+1} - n_k. \end{align}$$

Following proof is based on the proof of brob26.

Read more..

An Euclidean-algorithm type algorithm

Feb 11, 2020

In this article, we introduce an Euclidean-algorithm type algorithm for solving following problem

$$\begin{align} \min_{x} \{x \ge 0: L \le Ax(\mathrm{mod}\ M) \le R \} ,\end{align}$$
where $A, M, L, R, x$ are both nonnegative integers such that $0 \le L \le R < M$ and $\text{gcd}(A, M) = 1$.
We use $n(\mathrm{mod}\ M)$ to denote the integer $n’$ such that $n’ \equiv n (\mathrm{mod}\ M)$ and $0 \le n’ < M$.

Read more..

Period of out-shuffle

Aug 28, 2019

An out-shuffle is a riffle shuffle in which the top half of the deck is taken in the left hand and cards are then alternatively interleaved from left and right hands with preserving the location of the top and bottom card of the deck.

Suppose a deck of size $6$ originally arranged as $(1, 2, 3, 4, 5, 6)$. After an out-shuffle, the deck will become $(1, 4, 2, 5, 3, 6)$.

Period of out-shuffle

Let $n$ is an even integer and $s(n)$ be the minimum number of out-shuffles needed to restore a deck of size $n$ to its original order. Then we have

$$\begin{equation*} s(n) = \min_{m} \{ m : 2^m \equiv 1 (\bmod n - 1) \}. \end{equation*}$$
Read more..

Sum of the Euler Totient function

Aug 26, 2019

In this article, we introduce an algorithms for computing sum of the Euler Totient function. Our approach completely comes from the approach in the previous article about counting square free numbers.

The Euler totient function $\varphi(n)$ is defined as the number of positive integers less than $n$ which are co-prime with $n$. Our goal is to compute the sum of all values of the totient function up to a certain $N$

$$ S(N) = \sum_{n=1}^N \varphi(n). $$
Read more..

Proof for Minimax Theorem

Mar 24, 2019

Von Neumann's minimax theorem (1928)

Let $X$ and $Y$ be compact convex sets. Suppose that $f:X \times Y \rightarrow \mathbb{R}$ is a continuous function that satisfies:
1. $f(\cdot, y): X \rightarrow \mathbb{R}$ is convex for any fixed $y \in Y$,
2. $f(x, \cdot): Y \rightarrow \mathbb{R}$ is concave for any fixed $x \in X$.
Then, we have that

$$\begin{equation} \min_{x \in X} \max_{y \in Y} f(x, y) = \max_{y \in Y} \min_{x \in X} f(x, y) \end{equation}$$

Following proof is from Hidetoshi Komiya [1].

Read more..

A note for command `convert`

Mar 3, 2019

failure

$ convert -density 300 example.eps example.png
convert-im6.q16: not authorized `example.eps’ @ error/constitute.c/ReadImage/412.
convert-im6.q16: no images defined `example.png’ @ error/convert.c/ConvertImageCommand/3258.

Read more..