# The Maths Behind Logistic Regression

#### What are Your Odds?

Let’s have a look at this god-tier math puzzle. Only one out of seven gets it right, and the other six don’t. So, what are the odds for solving it correctly? 1 to 6. Generally, if $$p$$ is the probability that someone will get it right, then his/her odds are $$p/(1-p)$$.

However, it isn’t necessarily true that $$p=1/7$$ for every person because some people are smarter, some have better education and so on. Hence, $$p$$ also depends on the person attempting the puzzle. In a Bayesian framework, we capture this dependence with conditional probability.

# Prime Counting Function and Chebyshev Bounds

The distribution of primes plays a central role in number theory. The famous mathematician Gauss had conjectured that the number of primes between $$1$$ and $$n$$ is roughly $$n/\log n$$. This estimation gets more and more accurate as $$n\to \infty$$. We use $$\pi(n)$$ to denote the number of primes between $$1$$ and $$n$$. So, mathematically, Gauss’s conjecture is equivalent to the claim

$\lim_{n\to\infty}\frac{\pi(n)}{n/\log n}=1$

# Multiplying Two Polynomials with Fast Fourier Transform

Polynomial multiplication is one of the most important problems in mathematics and computer science. It can be formally defined as follows:

You are given two polynomials roughly of equal size$A(x)=a_0+a_1x+\dots+a_{n-1}x^{n-1}$$B(x)=b_0+b_1x+\dots+b_{n-1}x^{n-1}$find a polynomial $C(x)=c_0+c_1x+\dots+c_{2n-2}x^{2n-2}$ such that $$A(x)\cdot B(x)=C(x)$$. At first, this may look like an easy problem, Continue reading Multiplying Two Polynomials with Fast Fourier Transform

# Generating All Subsets of Size k in Python

Suppose you are given a set $$S$$ with $$n$$ elements and you need to generate every subset of size $$k$$ from it. For instance, if $$S=\{3,4,5\}$$ and $$k=2$$, then the answer would be $$\{3,4\}$$, $$\{3,5\}$$, $$\{4,5\}$$. So, how would you do that in Python?

First of all, this is a really simple exercise. Stuff like this often comes up when someone writes a moderately large script. I wanna talk about this one in particular because it has a combinatorial solution. Continue reading Generating All Subsets of Size k in Python

# A Special Case of Zsigmondy’s Theorem

Theorem (Zsigsmondy):Â

1. For two coprime positive integersÂ $$a$$ and $$b$$ and for any positive integer $$n$$, $$a^n-b^n$$ has a prime divisor that does not divide $$a^k-b^k$$ for all positive integers $$k< n$$ with the following exceptions:
• $$n = 2$$ and $$a+b$$ is a power of two.
• $$n=6, a=2, b=1$$.
2. For two coprime positive integersÂ $$a$$ and $$b$$ and for any positive integer $$n$$, $$a^n+b^n$$ has a prime divisor that does not divide $$a^k+b^k$$ for all positive integers $$k< n$$ with the following exception:
• $$n=3, a=2, b=1$$.

This theorem is very helpful in solving many olympiad number theory problems. However, its use is often frowned upon, as this theorem is quite hard to prove using only elementary mathematics. (I am aware of the proof using Cyclotomic Polynomials, but that’s not “elementary enough” in my opinion.)

In olympiad mathematics, one can get away in most of the cases by just using this theorem for a fixed pair of $$n$$ and $$k$$. This modification allows us to provide a very simple proof using LTE. Here I’ll restate this particular case, and then prove the first part. The second part can be proven analogously.

Theorem (Zsigsmondy Special Case):Â

1. For two coprime positive integersÂ $$a$$ and $$b$$ and any two positive integers $$n$$ and $$k$$ with $$k<n$$, $$a^n-b^n$$ has a prime divisor that does not divide $$a^k-b^k$$ with the following exception:
• $$n = 2, k=1$$ and $$a+b$$ is a power of two.
2. For two coprime positive integersÂ $$a$$ and $$b$$ and any two positive integers $$n$$ and $$k$$ with $$k<n$$, $$a^n+b^n$$ has a prime divisor that does not divide $$a^k+b^k$$ with the following exception:
• $$n=3, k=1,a=2, b=1$$.

Proof of 1:

Suppose $$a^n-b^n$$ and $$a^k-b^k$$ share same set of prime divisors. This implies $$a^n-b^n$$ and $$a^{\gcd(n,k)}-b^{\gcd(n,k)}$$ also share same set of prime divisors. Assuming $$A=a^{\gcd(n,k)}$$ and $$B=b^{\gcd(n,k)}$$, we could follow the rest of this argument and get to a contradiction. So, without loss of generality, we may assume $$k=1$$.

Now we consider two cases:

Case 1: $$n$$ is a power of $$2$$.
If $$n=2$$ and $$a+b$$ is a power of two, we arrive at one of the listed exceptions. Now note that,
\begin{align*}&\gcd(a+b, a^2+b^2)\\ =&\gcd(a+b, (a+b)^2-a^2-b^2)\\ =&\gcd(a+b,2ab)\\ =&\gcd(a+b,2)\end{align*}
This implies both $$a+b$$ and $$a^2+b^2$$ can’t be powers of two unless $$a+b=2\implies a=b=1$$. Hence at least one of them must have an odd prime divisor. Furthermore, this prime divisor does not divide $$a-b$$ since $$\gcd(a-b, a^2+b^2)=\gcd(a-b,2)$$ (following the previous steps). However, if $$n>2$$, then $$a^2+b^2|a^n-b^n$$, implying that odd prime will divide $$a^n-b^n$$. This is a contradiction.

Case 2: $$n=2^md$$ with $$d>1$$ being odd.
Without loss of generality, we may assume $$n>1$$ is odd, since $$a^d-b^d|a^n-b^n$$ and it is sufficient to show that $$a^d-b^d$$ has a prime divisor that does not divide $$a-b$$.Â Â From LTE, $$v_p(a-b)+v_p(n)=v_p(a^n-b^n)$$ for each odd prime $$p|a-b$$. Furthermore, $\frac{a^n-b^n}{a-b}\equiv na^{n-1}\equiv 1\pmod 2$ implying $$v_2(a-b)=v_2(a^n-b^n)$$. Therefore, we can conclude $\frac{a^n-b^n}{a-b}=\prod_{p|\gcd(n,a-b)}p^{v_p(n)}\leq n$ which is impossible for $$n>1$$. This raises another contradiction and we are done.

# āĻāĻ¨ā§āĻāĻŋāĻāĻžāĻ° āĻĢā§āĻ¯āĻžāĻā§āĻā§āĻ°āĻžāĻāĻā§āĻļāĻ¨: āĻĒāĻ°ā§āĻŦ ā§§ āĻĒā§āĻ˛āĻžāĻ°ā§āĻĄā§āĻ° āĻ°ā§ (rho) āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽ

āĻāĻ¤ āĻĒāĻ°ā§āĻŦā§ āĻāĻŽāĻ°āĻž āĻāĻžā§ā§āĻ° āĻā§āĻ°ā§ āĻāĻŋāĻā§ āĻ¸āĻāĻā§āĻ¯āĻžāĻ° āĻā§āĻĒāĻžāĻĻāĻ āĻŦā§āĻ° āĻāĻ°āĻžāĻ° āĻā§āĻˇā§āĻāĻž āĻāĻ°ā§āĻāĻŋāĻ˛āĻžāĻŽāĨ¤ āĻĻā§āĻāĻāĻāĻ¨āĻāĻ­āĻžāĻŦā§ āĻāĻŽāĻžāĻĻā§āĻ° āĻŦāĻžāĻā§āĻāĻž āĻĒā§āĻ°ā§āĻā§āĻ°āĻžāĻŽāĻāĻŋ $$20$$ āĻĄāĻŋāĻāĻŋāĻā§āĻ° āĻāĻāĻāĻŋ āĻ¸āĻāĻā§āĻ¯āĻžāĻā§ āĻā§āĻĒāĻžāĻĻāĻā§ āĻŦāĻŋāĻļā§āĻ˛ā§āĻˇāĻŖ āĻāĻ°āĻ¤ā§ āĻāĻŋā§ā§ āĻā§āĻ˛āĻžāĻ¨ā§āĻ¤ āĻšā§ā§ āĻāĻŋā§ā§āĻāĻŋāĻ˛āĨ¤ $$50$$ āĻŦāĻž $$100$$ āĻĄāĻŋāĻāĻŋāĻā§āĻ° āĻā§āĻ¨ āĻ¸āĻāĻā§āĻ¯āĻžāĻā§ āĻā§āĻĒāĻžāĻĻāĻā§ āĻŦāĻŋāĻļā§āĻ˛ā§āĻˇāĻŖ āĻāĻ°āĻ¤ā§ āĻšāĻ˛ā§ āĻ¸ā§āĻ āĻĒā§āĻ°ā§āĻā§āĻ°āĻžāĻŽā§āĻ° āĻā§ āĻāĻŦāĻ¸ā§āĻĨāĻž āĻšāĻŦā§ āĻ­āĻžāĻŦ āĻāĻāĻŦāĻžāĻ°!

āĻŽāĻžāĻ¨ā§āĻˇ āĻ¯āĻāĻ¨ āĻĻā§āĻāĻ˛ āĻŦā§ āĻŦā§ āĻ¸āĻāĻā§āĻ¯āĻžāĻ° āĻāĻ¨ā§āĻ¯ $$2$$ āĻĨā§āĻā§ $$N-1$$ [āĻāĻŋāĻāĻŦāĻž $$\sqrt N$$] āĻĒāĻ°ā§āĻ¯āĻ¨ā§āĻ¤ āĻ¸āĻŦ āĻ¸āĻāĻā§āĻ¯āĻž āĻĻāĻŋā§ā§ $$N$$-āĻā§ āĻāĻŽāĻ¨ āĻ­āĻžāĻ āĻāĻ°āĻž āĻāĻ¨ā§āĻ āĻ¸āĻŽā§āĻ¸āĻžāĻĒā§āĻā§āĻˇ, āĻ¤āĻāĻ¨ āĻ¤āĻžāĻ°āĻž āĻā§āĻ°āĻŋāĻ āĻā§āĻāĻāĻ¤ā§ āĻ˛āĻžāĻāĻ˛ āĻā§ āĻāĻ°ā§ āĻāĻ°āĻ āĻāĻŽ āĻ¸āĻāĻā§āĻ¯āĻ āĻ¸āĻāĻā§āĻ¯āĻž āĻĻāĻŋā§ā§ āĻ­āĻžāĻ āĻāĻ°ā§ $$N$$-āĻāĻ° āĻā§āĻĒāĻžāĻĻāĻ āĻŦā§āĻ° āĻāĻ°āĻž āĻ¯āĻžā§āĨ¤ āĻāĻŽāĻ¨ āĻāĻ¨ā§āĻāĻā§āĻ˛ā§ āĻā§āĻ°āĻŋāĻ āĻ°ā§ā§āĻā§, āĻ¯āĻžāĻ° āĻŽāĻžāĻā§ āĻāĻāĻāĻŋ āĻšāĻ˛ āĻāĻ¨ā§āĻŽāĻĻāĻŋāĻ¨ āĻ¸āĻŽāĻ¸ā§āĻ¯āĻž(āĻĒāĻ°āĻŋāĻļāĻŋāĻˇā§āĻā§ āĻĻā§āĻ)āĨ¤ āĻāĻā§ āĻāĻžāĻā§ āĻ˛āĻžāĻāĻŋā§ā§ āĻāĻ¨ā§āĻŽ āĻšā§ā§āĻā§ āĻāĻāĻāĻŋ āĻāĻžāĻ˛āĻžāĻāĻāĻ¤ā§āĻ° āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽā§āĻ°āĨ¤

## āĻĒā§āĻ˛āĻžāĻ°ā§āĻĄā§āĻ° $$\rho$$ āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽ

āĻŽāĻ¨ā§ āĻāĻ°, āĻāĻŽāĻžāĻĻā§āĻ°āĻā§ $$N=55$$-āĻā§ āĻā§āĻĒāĻžāĻĻāĻā§ āĻŦāĻŋāĻļā§āĻ˛ā§āĻˇāĻŖ āĻāĻ°āĻ¤ā§ āĻšāĻŦā§āĨ¤ (āĻāĻŽāĻ°āĻž āĻ¯āĻĻāĻŋāĻ āĻāĻžāĻ¨āĻŋ āĻ¯ā§ $$55$$ āĻāĻ° āĻāĻāĻāĻŋ āĻā§āĻĒāĻžāĻĻāĻ $$p=5$$, āĻ¤āĻŦā§āĻ āĻāĻŽāĻ°āĻž āĻ¸ā§āĻāĻŋ āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽ āĻŦā§āĻ° āĻāĻ°āĻŦāĨ¤)

āĻāĻŽāĻ°āĻž āĻāĻ°āĻŦ āĻāĻŋ, āĻ°âā§āĻ¯āĻžāĻ¨ā§āĻĄāĻŽ āĻĒā§āĻ°ā§āĻŖāĻ¸āĻāĻā§āĻ¯āĻžāĻ° āĻāĻāĻāĻŋ āĻāĻ¸ā§āĻŽ āĻ§āĻžāĻ°āĻž (infinite sequence) $$a_0, a_1, a_2, a_3, a_4,\ldots$$ [āĻ¸āĻāĻā§āĻˇā§āĻĒā§ $$\{a_i\}_{i = 0}^{\infty}$$] āĻĨā§āĻā§ āĻā§ā§āĻžāĻ˛ āĻā§āĻļāĻŋāĻŽāĻ¤ āĻāĻŋāĻā§ āĻĒāĻĻ, āĻ¯ā§āĻŽāĻ¨: $$a_0, a_3, a_7, a_{100}$$, āĻ¤ā§āĻ˛ā§ āĻ¨ā§āĻŦāĨ¤ āĻāĻ¨ā§āĻŽāĻĻāĻŋāĻ¨ āĻ¸āĻŽāĻ¸ā§āĻ¯āĻž āĻāĻ¨ā§āĻ¯āĻžā§ā§, āĻāĻ āĻāĻžāĻ°āĻāĻŋ āĻĒāĻĻā§āĻ° āĻŽāĻžāĻā§ $$\pmod {5}$$-āĻ āĻāĻ¨āĻā§āĻ°ā§ā§ā§āĻ¨ā§āĻ āĻāĻ¨ā§āĻ¤āĻ¤ āĻĻā§āĻāĻŋ āĻĒāĻĻ āĻĒāĻžāĻā§āĻžāĻ° āĻ¸āĻŽā§āĻ­āĻžāĻŦāĻ¨āĻž$1-e^{-\frac{4^2}{2\times 5}}\approx 80\%$āĻāĻŽāĻ¨ āĻĻā§āĻāĻŋ āĻĒāĻĻ $$a_m$$ āĻāĻŦāĻ $$a_n$$ āĻ¯āĻĻāĻŋ āĻ¸āĻ¤ā§āĻ¯āĻŋ āĻ¸āĻ¤ā§āĻ¯āĻŋ āĻĨāĻžāĻā§, āĻ¤āĻžāĻšāĻ˛ā§ $a_m\equiv a_n\pmod{5}$$\implies a_m-a_n\equiv 0\pmod{5}$$\implies d = \gcd(55, a_m-a_n)\ge 5$ āĻāĻ°ā§āĻĨāĻžā§, āĻāĻŽāĻ°āĻž $$55$$-āĻāĻ° āĻāĻāĻāĻŋ āĻā§āĻĒāĻžāĻĻāĻ $$d$$ āĻ¨āĻŋāĻ°ā§āĻŖā§ āĻāĻ°ā§ āĻĢā§āĻ˛āĻŦāĨ¤ āĻāĻŦāĻļā§āĻ¯ āĻā§āĻ āĻĒā§āĻ°āĻļā§āĻ¨ āĻāĻ°āĻ¤ā§āĻ āĻĒāĻžāĻ°ā§ $$d = 55$$ āĻšāĻ˛ā§? āĻšā§āĻ¯āĻžāĻ, āĻ¸ā§āĻāĻž āĻšāĻ¤ā§ āĻĒāĻžāĻ°ā§āĨ¤ āĻāĻŋāĻ¨ā§āĻ¤ā§ āĻāĻžāĻ°āĻāĻŋ āĻ¸āĻāĻā§āĻ¯āĻžāĻ° āĻŽāĻžāĻā§ $$\pmod{55}$$-āĻ āĻāĻ¨āĻā§āĻ°ā§ā§ā§āĻ¨ā§āĻ āĻĻā§āĻāĻŋ āĻ¸āĻāĻā§āĻ¯āĻž āĻĒāĻžāĻā§āĻžāĻ° āĻ¸āĻŽā§āĻ­āĻžāĻŦāĻ¨āĻž āĻŽāĻžāĻ¤ā§āĻ°$1-e^{-\frac{4^2}{2\times 55}}\approx 13.5\%$

āĻāĻ¤āĻāĻŦ, āĻāĻŽāĻ°āĻž āĻ¯āĻĻāĻŋ $$\{a_i\}_{i = 0}^{\infty}$$ āĻĨā§āĻā§ āĻĒā§āĻ°āĻ¤āĻŋāĻŦāĻžāĻ° āĻ¯ā§āĻā§āĻ¨ āĻĻā§āĻāĻāĻŋ āĻĒāĻĻ $$a_i$$ āĻāĻŦāĻ $$a_j$$ āĻ¨āĻŋā§ā§ $$\gcd(N, a_i-a_j)$$ āĻ¨āĻŋāĻ°ā§āĻŖā§ āĻāĻ°ā§ āĻ¯ā§āĻ¤ā§ āĻĨāĻžāĻāĻŋ, āĻ¤āĻžāĻšāĻ˛ā§ āĻā§āĻŦāĻ āĻ­āĻžāĻ˛ āĻ¸āĻŽā§āĻ­āĻžāĻŦāĻ¨āĻž āĻāĻā§ āĻ¯ā§ āĻāĻŽāĻ°āĻž $$a_m-a_n$$ āĻĒā§ā§ā§ āĻ¯āĻžāĻŦ āĻāĻŦāĻ $$55$$-āĻāĻ° āĻāĻāĻāĻŋ āĻĒā§āĻ°āĻā§āĻ¤ āĻā§āĻĒāĻžāĻĻāĻ $$d$$ āĻ¨āĻŋāĻ°ā§āĻŖā§ āĻāĻ°ā§ āĻĢā§āĻ˛āĻŦāĨ¤

āĻ¤āĻŦā§ āĻāĻžāĻŽā§āĻ˛āĻž āĻšāĻā§āĻā§ āĻāĻžāĻāĻāĻŋ āĻ°âā§āĻ¯āĻžāĻ¨ā§āĻĄāĻŽ āĻ¸āĻāĻā§āĻ¯āĻžāĻ° āĻāĻ¸ā§āĻŽ āĻ§āĻžāĻ°āĻž āĻŦā§āĻ¯āĻŦāĻšāĻžāĻ° āĻāĻ°āĻ˛ā§ āĻ¸ā§āĻāĻŋāĻ° āĻāĻ¨ā§āĻāĻā§āĻ˛ā§ āĻĒāĻĻ āĻāĻŽāĻžāĻĻā§āĻ°āĻā§ āĻŽā§āĻŽāĻ°āĻŋāĻ¤ā§ āĻ°āĻžāĻāĻ¤ā§ āĻšāĻŦā§, āĻĢāĻ˛ā§ $$50$$ āĻŦāĻž $$100$$ āĻĄāĻŋāĻāĻŋāĻā§āĻ° āĻā§āĻ¨ āĻ¸āĻāĻā§āĻ¯āĻžāĻ° āĻāĻ¨ā§āĻ¯ āĻā§āĻāĻŋ āĻā§āĻāĻŋ āĻĒā§āĻāĻžāĻŦāĻžāĻāĻ āĻŽā§āĻŽāĻ°āĻŋāĻ° āĻĒā§āĻ°ā§ā§āĻāĻ¨ āĻšāĻŦā§āĨ¤ āĻ¤āĻžāĻ āĻāĻŽāĻ°āĻž āĻāĻŽāĻ¨ āĻā§āĻ¨ āĻ¸āĻāĻā§āĻ¯āĻžāĻ° āĻ§āĻžāĻ°āĻž āĻ¨ā§āĻŦ āĻ¯āĻžāĻ° āĻŽāĻžāĻ¨ āĻĒā§āĻ°āĻā§āĻ¤āĻĒāĻā§āĻˇā§ āĻĄāĻŋāĻāĻžāĻ°āĻŽāĻŋāĻ¨āĻŋāĻ¸ā§āĻāĻŋāĻ, āĻāĻ°ā§āĻĨāĻžā§ āĻ¸ā§āĻ¤ā§āĻ° āĻŽā§āĻ¨ā§ āĻāĻ˛ā§, āĻāĻŋāĻ¨ā§āĻ¤ā§ $$\pmod p$$-āĻ¤ā§ āĻŽā§āĻāĻžāĻŽā§āĻāĻŋ āĻ°âā§āĻ¯āĻžāĻ¨ā§āĻĄāĻŽāĻ˛āĻŋ āĻāĻ¸ā§āĨ¤ (āĻāĻŽāĻ¨ āĻ¸āĻāĻā§āĻ¯āĻžāĻā§ āĻŦāĻ˛ā§ āĻ¸ā§āĻĄā§āĻ°âā§āĻ¯āĻžāĻ¨ā§āĻĄāĻŽ āĻ¸āĻāĻā§āĻ¯āĻž)

āĻāĻĻāĻžāĻšāĻ°āĻŖāĻ¸ā§āĻŦāĻ°ā§āĻĒ, āĻāĻ¸ā§āĻŽ āĻ§āĻžāĻ°āĻž āĻšāĻŋāĻ¸ā§āĻŦā§ $$a_0=1$$, āĻāĻŦāĻ $$a_i=a_{i-1}^2+1$$, āĻāĻ°ā§āĻĨāĻžā§ $$1, 2, 5, 26, 677,\ldots$$ āĻ§āĻžāĻ°āĻžāĻāĻŋ āĻ¨ā§āĻā§āĻž āĻ¨ā§āĻŦ āĻāĻŦāĻ āĻĒā§āĻ°āĻ¤āĻŋāĻāĻŋ āĻĒāĻĻā§āĻ° āĻāĻ¨ā§āĻ¯ $$\gcd(N, a_i-a_0)$$ āĻ¨āĻŋāĻ°ā§āĻŖā§ āĻāĻ°āĻŦāĨ¤ āĻ˛āĻā§āĻˇā§āĻ¯ āĻāĻ° āĻ¯ā§, āĻāĻŽāĻžāĻĻā§āĻ° $$a_i$$-āĻāĻ° āĻĒā§āĻ°āĻā§āĻ¤ āĻŽāĻžāĻ¨ā§āĻ° āĻĒāĻ°āĻŋāĻŦāĻ°ā§āĻ¤ā§ $$a_i\pmod N$$ āĻāĻžāĻ¨āĻ˛ā§āĻ āĻāĻ˛ā§āĨ¤

def rhonaive(N):
a_0 = d = 1
a_i = a_0
while d == 1:
a_i = (a_i * a_i + 1) % N
d = gcd(a_i - a_0, N)
return d


āĻāĻ¨ā§āĻāĻ¸āĻŽā§ āĻĻā§āĻāĻž āĻ¯ā§āĻ¤ā§ āĻĒāĻžāĻ°ā§ āĻāĻŽāĻžāĻĻā§āĻ° āĻ¨ā§āĻā§āĻž āĻ¸ā§āĻĄā§āĻ°âā§āĻ¯āĻžāĻ¨ā§āĻĄāĻŽ āĻ¸āĻāĻā§āĻ¯āĻžāĻ° āĻ§āĻžāĻ°āĻžāĻāĻŋ “āĻ¯āĻĨā§āĻˇā§āĻ āĻ°âā§āĻ¯āĻžāĻ¨ā§āĻĄāĻŽ” āĻ¨ā§āĨ¤ āĻ¤ā§āĻŽāĻ¨ āĻā§āĻˇā§āĻ¤ā§āĻ°ā§ āĻāĻŽāĻžāĻĻā§āĻ° $$a_i = a_{i-1}^2+1$$ āĻāĻ° āĻĒāĻ°āĻŋāĻŦāĻ°ā§āĻ¤ā§ āĻāĻ°ā§āĻāĻā§ āĻāĻāĻŋāĻ˛ āĻā§āĻ¨ āĻ¸āĻŽā§āĻĒāĻ°ā§āĻ āĻŦā§āĻ¯āĻŦāĻšāĻžāĻ° āĻāĻ°āĻ¤ā§ āĻšāĻŦā§āĨ¤ āĻ¤āĻžāĻ, āĻ¸āĻžāĻ§āĻžāĻ°āĻŖāĻ­āĻžāĻŦā§(generally) āĻāĻŽāĻ°āĻž $$a_i=f(a_{i-1})$$ āĻ§āĻ°āĻ¤ā§ āĻĒāĻžāĻ°āĻŋ āĻ¯ā§āĻāĻžāĻ¨ā§ $$f(x)$$ āĻšāĻā§āĻā§ āĻāĻāĻāĻŋ āĻ¸ā§āĻŦāĻŋāĻ§āĻžāĻāĻ¨āĻ āĻŦāĻšā§āĻĒāĻĻā§āĨ¤ āĻ¯ā§āĻŽāĻ¨- āĻāĻĒāĻ°ā§āĻ° āĻĒā§āĻ°ā§āĻā§āĻ°āĻžāĻŽā§ $$f(x)=x^2+1$$.

āĻ˛āĻā§āĻˇā§āĻ¯ āĻāĻ° āĻ¯ā§, $$\{a_i\}_{i = 0}^{\infty}$$ āĻ§āĻžāĻ°āĻžāĻ° āĻĒā§āĻ°āĻ¤āĻŋāĻāĻŋ āĻĒāĻĻ āĻļā§āĻ§ā§āĻŽāĻžāĻ¤ā§āĻ° āĻāĻā§āĻ° āĻĒāĻĻā§āĻ° āĻāĻĒāĻ° āĻ¨āĻŋāĻ°ā§āĻ­āĻ°āĻļā§āĻ˛āĨ¤ āĻ¤āĻžāĻ $$a_m \equiv a_n\pmod p$$ āĻāĻāĻŦāĻžāĻ° āĻĒāĻžāĻā§āĻž āĻā§āĻ˛ā§ āĻ§āĻžāĻ°āĻžāĻ¤ā§ āĻĒā§āĻ°ā§āĻŦāĻŦāĻ°ā§āĻ¤ā§ āĻĒāĻĻāĻā§āĻ˛ā§ āĻ¸āĻžāĻāĻā§āĻ˛āĻŋāĻāĻ­āĻžāĻŦā§ āĻā§āĻ°ā§ āĻĢāĻŋāĻ°ā§ āĻāĻ¸āĻ¤ā§ āĻĨāĻžāĻāĻŦā§āĨ¤ āĻāĻ°ā§āĻĨāĻžā§,$$a_{m+i}\equiv a_{n+i}\pmod p$$.

āĻ¤āĻŦā§ āĻāĻ āĻ¸āĻžāĻāĻā§āĻ˛ $$a_0$$ āĻĨā§āĻā§ āĻļā§āĻ°ā§ āĻšāĻ¤ā§ āĻšāĻŦā§ āĻāĻŽāĻ¨ āĻā§āĻ¨ āĻāĻĨāĻž āĻ¨ā§āĻāĨ¤ āĻ¯ā§āĻŽāĻ¨- $$p=29$$ āĻāĻŦāĻ $$f(x)=x^2+1$$ āĻšāĻ˛ā§, $$\pmod p$$-āĻ¤ā§ $$\{a_i\}_{i = 0}^{\infty}$$ āĻ§āĻžāĻ°āĻžāĻāĻŋ āĻšā§

 $$i$$ $$0$$ $$1$$ $$2$$ $$3$$ $$4$$ $$5$$ $$6$$ $$7$$ $$8$$ $$9$$ $$10$$ $$11$$ $$a_i$$ $$1$$ $$2$$ $$5$$ $$26$$ $$10$$ $$14$$ $$23$$ $$8$$ $$7$$ $$21$$ $$\color{red}7$$ $$\color{red}{21}$$

āĻĻā§āĻāĻ¤ā§āĻ āĻĒāĻžāĻā§āĻ, $$a_0$$-āĻ° āĻāĻ¨āĻā§āĻ°ā§ā§ā§āĻ¨ā§āĻ āĻā§āĻ¨ āĻĒāĻĻ āĻĻā§āĻŦāĻŋāĻ¤ā§ā§āĻŦāĻžāĻ° āĻĒāĻžāĻā§āĻž āĻ¯āĻžā§āĻ¨āĻŋāĨ¤ āĻ¤āĻžāĻ, āĻĒā§āĻ°ā§āĻā§āĻ°āĻžāĻŽ ā§§-āĻ āĻ¸āĻŦāĻ¸āĻŽā§ $$a_0$$ āĻĨā§āĻā§ āĻ¸āĻžāĻāĻā§āĻ˛ āĻļā§āĻ°ā§ āĻšāĻŦā§ āĻ§āĻ°ā§ āĻ¨ā§āĻā§āĻžāĻāĻž āĻ­ā§āĻ˛ āĻāĻŋāĻ˛āĨ¤

āĻāĻŽāĻ¨ āĻ§āĻžāĻ°āĻžāĻ¤ā§ āĻ¸āĻžāĻāĻā§āĻ˛ (āĻāĻ°ā§āĻĨāĻžā§ $$\pmod p$$-āĻ¤ā§ āĻāĻ¨āĻā§āĻ°ā§ā§ā§āĻ¨ā§āĻ āĻĻā§āĻāĻŋ āĻĒāĻĻ) āĻ¨āĻŋāĻ°ā§āĻŖā§ āĻāĻ°āĻ¤ā§ āĻāĻ°ā§āĻāĻā§ āĻŦā§āĻĻā§āĻ§āĻŋ āĻāĻžāĻāĻžāĻ¤ā§ āĻšā§āĨ¤ āĻāĻŽāĻŋ āĻāĻāĻžāĻ¨ā§ āĻĻā§āĻāĻŋ āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽā§āĻ° āĻāĻĨāĻž āĻŦāĻ˛ā§ āĻĻāĻŋāĻā§āĻāĻŋāĨ¤ āĻĒā§āĻ°āĻĨāĻŽāĻāĻŋ āĻĢā§āĻ˛ā§ā§āĻĄā§āĻ° āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽ, āĻĻā§āĻŦāĻŋāĻ¤ā§ā§āĻāĻŋ āĻŦā§āĻ°ā§āĻ¨ā§āĻā§āĻ° āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽāĨ¤

### āĻĢā§āĻ˛ā§ā§āĻĄā§āĻ° āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽ

āĻŽāĻ¨ā§ āĻāĻ° $$a_i$$ āĻ§āĻžāĻ°āĻžāĻ° āĻ¸āĻžāĻāĻā§āĻ˛ā§āĻ° āĻĻā§āĻ°ā§āĻā§āĻ¯ $$l$$. $$n$$ āĻ¯āĻĻāĻŋ āĻ¯āĻĨā§āĻˇā§āĻ āĻŦā§ āĻšā§, āĻ¤āĻŦā§,$a_n\equiv a_{n+l}\equiv a_{n+2l}\equiv\cdots\equiv a_{n+kl}\pmod p$
āĻāĻŽāĻ°āĻž āĻ¯āĻĻāĻŋ āĻ¯āĻĨā§āĻˇā§āĻ āĻŦā§ āĻā§āĻ¨ $$k$$-āĻ° āĻāĻ¨ā§āĻ¯ $$n=kl$$ āĻ¨ā§āĻ, āĻ¤āĻŦā§,$a_n \equiv a_{n+kl}=a_{2kl}=a_{2n}\pmod p$
āĻāĻ°ā§āĻĨāĻžā§, $$a_i$$ āĻ§āĻžāĻ°āĻžā§ āĻāĻŽāĻ¨ āĻāĻ¸ā§āĻŽ āĻ¸āĻāĻā§āĻ¯āĻ āĻĒāĻĻ $$a_n$$ āĻāĻā§ āĻ¯āĻžāĻĻā§āĻ° āĻāĻ¨ā§āĻ¯ $$a_n\equiv a_{2n}\pmod p$$. āĻ¸ā§āĻ¤āĻ°āĻžāĻ $$\gcd(N, a_{2i}-a_i)$$ āĻ¨āĻŋāĻ°ā§āĻŖā§ āĻāĻ°ā§ āĻ¯ā§āĻ¤ā§ āĻĨāĻžāĻāĻ˛ā§āĻ āĻāĻāĻāĻž āĻ¸āĻŽā§ $$\pmod p$$-āĻ¤ā§ āĻāĻ¨āĻā§āĻ°ā§ā§ā§āĻ¨ā§āĻ āĻĻā§āĻāĻŋ āĻĒāĻĻ āĻĒāĻžāĻā§āĻž āĻ¯āĻžāĻŦā§āĨ¤ āĻĢā§āĻ˛ā§ā§āĻĄā§āĻ° āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽ āĻāĻ āĻ§āĻžāĻ°āĻŖāĻžāĻāĻŋ āĻŦā§āĻ¯āĻŦāĻšāĻžāĻ° āĻāĻ°ā§āĨ¤

āĻĢā§āĻ˛ā§ā§āĻĄā§āĻ° āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽā§ āĻāĻāĻāĻŋ āĻāĻ°āĻā§āĻļ āĻāĻ° āĻāĻāĻāĻŋ āĻāĻā§āĻāĻĒā§āĻ° āĻŽāĻžāĻā§ āĻĻā§ā§ āĻĒā§āĻ°āĻ¤āĻŋāĻ¯ā§āĻāĻŋāĻ¤āĻžāĻ° āĻāĻ˛ā§āĨ¤ āĻāĻā§āĻāĻĒāĻāĻŋ āĻ§āĻžāĻ°āĻžāĻ° āĻāĻāĻāĻŋ āĻāĻāĻāĻŋ āĻĒāĻĻā§ $$a_0, a_1, a_2,a_3,\ldots$$ āĻĒāĻ°ā§āĻ¯āĻžā§āĻā§āĻ°āĻŽā§ āĻ¯ā§āĻ¤ā§ āĻĨāĻžāĻā§āĨ¤ āĻāĻāĻāĻ¸āĻŽā§ā§, āĻāĻ°āĻā§āĻļāĻāĻŋ āĻ§āĻžāĻ°āĻžāĻ° $$a_0, a_2, a_4, a_6,\ldots$$ āĻĒāĻĻāĻā§āĻ˛ā§āĻ¤ā§ āĻ˛āĻžāĻĢāĻŋā§ā§ āĻ˛āĻžāĻĢāĻŋā§ā§ āĻ¯ā§āĻ¤ā§ āĻĨāĻžāĻā§āĨ¤ āĻāĻŽāĻ°āĻž āĻāĻ°āĻā§āĻļā§āĻ° āĻāĻŦāĻ¸ā§āĻĨāĻžāĻ¨ āĻāĻŦāĻ āĻāĻā§āĻāĻĒā§āĻ° āĻāĻŦāĻ¸ā§āĻĨāĻžāĻ¨ā§āĻ° āĻĒāĻžāĻ°ā§āĻĨāĻā§āĻ¯ā§āĻ° āĻ¸āĻžāĻĨā§ $$N$$-āĻāĻ° āĻāĻ¸āĻžāĻā§ āĻ¨āĻŋāĻ°ā§āĻŖā§ āĻāĻ°āĻ¤ā§ āĻĨāĻžāĻāĻŋāĨ¤ āĻ¯āĻāĻ¨āĻ āĻāĻ¸āĻžāĻā§ $$1$$ āĻāĻ° āĻā§ā§ā§ āĻŦā§ āĻšā§ā§ āĻ¯āĻžā§, āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽāĻāĻŋ āĻāĻžāĻ°ā§āĻŽāĻŋāĻ¨ā§āĻ āĻāĻ°ā§āĨ¤

def rhofloyd(N):
#both hare and tortoise at a_0
tortoise = hare = d = 1
while d == 1:
tortoise = f(tortoise) % N #tortoise steps once
hare = f(f(hare)) % N #hare steps twice
d = gcd(hare - tortoise, N)
return d


### āĻŦā§āĻ°ā§āĻ¨ā§āĻā§āĻ° āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽ

āĻŦā§āĻ°ā§āĻ¨ā§āĻā§āĻ° āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽā§ āĻāĻ¨ā§āĻāĻā§āĻ˛ā§ āĻ°āĻžāĻāĻ¨ā§āĻĄā§ āĻāĻ°āĻā§āĻļ āĻāĻ° āĻāĻā§āĻāĻĒā§āĻ° āĻĻā§ā§ āĻĒā§āĻ°āĻ¤āĻŋāĻ¯ā§āĻāĻŋāĻ¤āĻž āĻāĻ˛ā§āĨ¤ āĻĒā§āĻ°āĻ¤āĻŋāĻ¯ā§āĻāĻŋāĻ¤āĻžāĻ° $$i$$-āĻ¤āĻŽ āĻ°āĻžāĻāĻ¨ā§āĻĄā§ āĻāĻ°āĻā§āĻļ āĻāĻ° āĻāĻā§āĻāĻĒ āĻāĻ­ā§ā§āĻ $$a_{2^i}$$-āĻ¤āĻŽ āĻĒāĻĻā§ āĻāĻŦāĻ¸ā§āĻĨāĻžāĻ¨ āĻāĻ°ā§āĨ¤ āĻĒā§āĻ°āĻ¤āĻŋāĻ¯ā§āĻāĻŋāĻ¤āĻž āĻļā§āĻ°ā§āĻ° āĻĒāĻ° āĻāĻ°āĻā§āĻļ āĻ¤āĻžāĻ° āĻāĻžā§āĻāĻžā§ āĻāĻ°āĻžāĻŽ āĻāĻ°ā§ āĻā§āĻŽ āĻĻā§ā§, āĻāĻ° āĻāĻā§āĻāĻĒāĻāĻŋ āĻā§āĻ āĻā§āĻ āĻāĻ°ā§ āĻāĻāĻāĻŋ āĻāĻāĻāĻŋ āĻĒāĻĻ āĻ¸āĻžāĻŽāĻ¨ā§ āĻāĻā§āĻ¤ā§ āĻĨāĻžāĻā§āĨ¤ āĻāĻŽāĻ°āĻž āĻĒā§āĻ°āĻ¤āĻŋāĻŦāĻžāĻ°āĻ āĻāĻ°āĻā§āĻļā§āĻ° āĻāĻŦāĻ¸ā§āĻĨāĻžāĻ¨ āĻāĻŦāĻ āĻāĻā§āĻāĻĒā§āĻ° āĻāĻŦāĻ¸ā§āĻĨāĻžāĻ¨ā§āĻ° āĻĒāĻžāĻ°ā§āĻĨāĻā§āĻ¯ā§āĻ° āĻ¸āĻžāĻĨā§ $$N$$-āĻāĻ° āĻāĻ¸āĻžāĻā§ $$d$$ āĻ¨āĻŋāĻ°ā§āĻŖā§ āĻāĻ°āĻŋāĨ¤ āĻ¯āĻāĻ¨ āĻāĻā§āĻāĻĒ āĻāĻ°āĻā§āĻļā§āĻ° āĻā§ā§ā§ $$2^i$$ āĻĒāĻĻ āĻ¸āĻžāĻŽāĻ¨ā§ āĻāĻāĻŋā§ā§ āĻ¯āĻžā§, āĻāĻ°āĻā§āĻļā§āĻ° āĻ¤ā§āĻžāĻ āĻāĻ°ā§ āĻā§āĻā§ āĻāĻ ā§ āĻāĻŦāĻ āĻ¸ā§ āĻāĻ āĻ˛āĻžāĻĢā§ āĻāĻā§āĻāĻĒā§āĻ° āĻāĻŦāĻ¸ā§āĻĨāĻžāĻ¨ā§ āĻāĻ˛ā§ āĻāĻ¸ā§āĨ¤ āĻāĻ°āĻĒāĻ° āĻĒā§āĻ°āĻ¤āĻŋāĻ¯ā§āĻāĻŋāĻ¤āĻžāĻ° $$i+1$$-āĻ¤āĻŽ āĻ°āĻžāĻāĻ¨ā§āĻĄ āĻļā§āĻ°ā§ āĻšā§āĨ¤

āĻāĻā§āĻ° āĻŽāĻ¤āĻ, $$d> 1$$ āĻšā§ā§ āĻā§āĻ˛ā§ āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽāĻāĻŋ āĻāĻžāĻ°ā§āĻŽāĻŋāĻ¨ā§āĻ āĻāĻ°āĻŦā§āĨ¤

āĻ˛āĻā§āĻˇā§āĻ¯ āĻāĻ° āĻ¯ā§, $$i$$ āĻāĻ° āĻŽāĻžāĻ¨ āĻŦāĻžā§āĻžāĻ° āĻ¸āĻžāĻĨā§ āĻ¸āĻžāĻĨā§ $$2^{i}$$ āĻāĻŦāĻ $$2^{i+1}$$-āĻāĻ° āĻŽāĻ§ā§āĻ¯āĻŦāĻ°ā§āĻ¤ā§ āĻĒāĻžāĻ°ā§āĻĨāĻā§āĻ¯āĻ āĻŦāĻžā§āĻ¤ā§ āĻĨāĻžāĻā§āĨ¤ āĻāĻāĻāĻž āĻ¸āĻŽā§ āĻāĻ āĻĒāĻžāĻ°ā§āĻĨāĻā§āĻ¯ $$\{a_i\}_{i = 0}^\infty$$ āĻ§āĻžāĻ°āĻžāĻ° āĻ¸āĻžāĻāĻā§āĻ˛ā§āĻ° āĻĻā§āĻ°ā§āĻā§āĻ¯ $$l$$ āĻĨā§āĻā§ āĻŦā§ āĻšā§ā§ āĻ¯āĻžā§āĨ¤ āĻ¤āĻāĻ¨ āĻāĻā§āĻāĻĒā§āĻ° āĻā§āĻ¨ āĻāĻ āĻāĻŦāĻ¸ā§āĻĨāĻžāĻ¨ā§āĻ° āĻāĻ¨ā§āĻ¯ āĻāĻ°āĻā§āĻļ āĻ āĻāĻā§āĻāĻĒā§āĻ° āĻāĻŦāĻ¸ā§āĻĨāĻžāĻ¨ā§āĻ° āĻĒāĻžāĻ°ā§āĻĨāĻā§āĻ¯ āĻšāĻŦā§ āĻ āĻŋāĻ $$l$$āĻāĻŋ āĻĒāĻĻāĨ¤ āĻāĻ āĻāĻŦāĻ¸ā§āĻĨāĻžāĻ¤ā§āĻ āĻāĻ¸āĻ˛ā§ āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽāĻāĻŋ āĻāĻžāĻ°ā§āĻŽāĻŋāĻ¨ā§āĻ āĻāĻ°āĻŦā§āĨ¤

def rhobrent(N):
#both hare and tortoise are at a_(2^0)
#power is the nearest 2^i behind tortoise
tortoise = hare = f(1)
power, lead, d = 1, 0, 1
while d == 1:
if lead == power: #tortoise reaches 2^(i+1)-th term
hare = tortoise #hare jumps to tortoise's position
power *= 2 #update power
lead = 0 #reset lead, since both hare and tortoise
#are in the same position now
tortoise = f(tortoise) % N #tortoise steps once
lead += 1 #tortoise leads the race by one more step
d = gcd(hare - tortoise, N)
return d


āĻŦā§āĻ°ā§āĻ¨ā§āĻā§āĻ° āĻāĻ¨āĻžāĻ˛āĻžāĻāĻ¸āĻŋāĻ¸ āĻāĻ¨ā§āĻ¸āĻžāĻ°ā§, āĻŦā§āĻ°ā§āĻ¨ā§āĻā§āĻ° āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽ āĻĢā§āĻ˛ā§ā§āĻĄā§āĻ° āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽ āĻĨā§āĻā§ $$24\%$$ āĻĻā§āĻ°ā§āĻ¤āĻ¤āĻ°āĨ¤

### āĻĒā§āĻ°ā§āĻŖāĻžāĻā§āĻ āĻĒā§āĻ°ā§āĻā§āĻ°āĻžāĻŽ

āĻŦā§āĻ°ā§āĻ¨ā§āĻā§āĻ° āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽ āĻĻāĻŋā§ā§ āĻ¯ā§āĻšā§āĻ¤ā§ āĻ¸āĻžāĻāĻā§āĻ˛ āĻļāĻ¨āĻžāĻā§āĻ¤āĻāĻ°āĻŖ āĻ¸āĻŦāĻā§ā§ā§ āĻĻā§āĻ°ā§āĻ¤ āĻāĻ°āĻž āĻ¯āĻžā§, āĻ¤āĻžāĻ āĻ¸ā§āĻāĻŋ āĻĻāĻŋā§ā§āĻ āĻ¨āĻŋāĻā§ āĻāĻāĻāĻŋ āĻĒā§āĻ°ā§āĻŖāĻžāĻā§āĻ āĻĒā§āĻ°ā§āĻā§āĻ°āĻžāĻŽ āĻĻā§āĻā§āĻž āĻšāĻ˛āĨ¤

from fractions import gcd
from time import time

def f(x):
return (x**2 + x + 1) % N

def rhobrent(N):
tortoise = hare = f(1)
power, lead, d = 1, 0, 1
while abs(d) == 1:
if lead == power:
hare, lead = tortoise, 0
power *= 2
tortoise = f(tortoise)
d = gcd(tortoise - hare, N)
return d

N = int(raw_input())
exec_time = time()
d = 1 if(-2 < N < 2) else rhobrent(N)
exec_time = time() - exec_time
print d, '*', N / d
print "Execution time: %.3f s" % exec_time

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iso646.h> //and

#define MAX 2147483647

long long f(long long x);
long long gcd(long long a, long long b);
long long rhobrent(long long N);

long long N;

int main(void){
long long d;
scanf("%lld", &N);
clock_t exec_time = clock();
d = (N < 2 and N > -2) ? 1 : rhobrent(N);
exec_time = clock() - exec_time;
double t = (double) exec_time / CLOCKS_PER_SEC;
printf("%lld * %lld\n", d, N/d);
printf("Execution time: %.3lf s\n", t);
return 0;
}

long long f(long long x){
if(x < MAX)
return (x * x + x + 1) % N;
long long y = x, output = x + 1;
while(y > 0){
if(y % 2 == 1)
output += x;
x *= 2;
y /= 2;
output %= N;
x %= N;
}
return output;
}

long long gcd(long long a, long long b){
long long r;
while(b != 0){
r =  a % b;
a = b;
b = r;
}
return (a > 0) ? a : -a;
}

long long rhobrent(long long N){
long long tortoise = f(1), hare = f(1), power = 1, lead = 0, d = 1;
while(d == 1){
hare = tortoise;
power *= 2;
}
tortoise = f(tortoise);
d = gcd(N, tortoise - hare);
}
return d;
}


āĻ¨ā§āĻ:

1. āĻāĻĒāĻ°ā§āĻ° āĻā§āĻĄā§ $$f(x)=x^2+x+1$$ āĻāĻŦāĻ āĻĢāĻžāĻāĻļāĻžāĻ¨ā§āĻ° āĻ­ā§āĻ¤āĻ°ā§āĻ $$N$$ āĻĻāĻŋā§ā§ āĻŽāĻĄā§āĻ˛āĻžāĻ¸ā§āĻ° āĻāĻžāĻ āĻļā§āĻˇ āĻāĻ°āĻž āĻšā§ā§āĻā§āĨ¤
2. āĻĒā§āĻ°āĻžā§ āĻ¸āĻāĻ˛ āĻāĻ§ā§āĻ¨āĻŋāĻ āĻāĻŽā§āĻĒāĻžāĻāĻ˛āĻžāĻ°ā§ long long int-āĻāĻ° āĻŦā§āĻ¯āĻžāĻŦāĻ§ā§ $$[-2^{63}, 2^{63})$$. āĻ¤āĻžāĻ āĻ¸āĻŋ āĻĒā§āĻ°ā§āĻā§āĻ°āĻžāĻŽā§ $$f(x)$$ āĻĢāĻžāĻāĻļāĻ¨āĻāĻŋ āĻ āĻŋāĻāĻ āĻžāĻāĻŽāĻ¤ āĻāĻžāĻ āĻāĻ°āĻžāĻ° āĻāĻ¨ā§āĻ¯ $x^2+x+1\leq 2^{63}-1\Longrightarrow x<2^{31.5}-1$ āĻšāĻ¤ā§ āĻšāĻŦā§āĨ¤ āĻāĻāĻ¨ā§āĻ¯ $$x \ge 2^{31}$$ -āĻāĻ° āĻāĻ¨ā§āĻ¯ $$y = x$$ āĻ¨āĻžāĻŽā§āĻ° āĻāĻāĻāĻŋ āĻ¨āĻ¤ā§āĻ¨ āĻ­ā§āĻ°āĻŋā§ā§āĻŦāĻ˛ āĻ¨āĻŋā§ā§ āĻāĻ° āĻĒā§āĻ°āĻ¤āĻŋāĻāĻŋ āĻŦāĻŋāĻā§āĻ° āĻ¸āĻžāĻĨā§ āĻāĻ˛āĻžāĻĻāĻžāĻ­āĻžāĻŦā§ $$x$$-āĻāĻ° āĻā§āĻŖāĻĢāĻ˛ āĻŦā§āĻ° āĻāĻ°ā§ āĻ¸ā§āĻ āĻ¸āĻŽāĻˇā§āĻāĻŋāĻ° āĻŽāĻĄā§āĻ˛āĻžāĻ¸ āĻ¨ā§āĻā§āĻž āĻšā§ā§āĻā§āĨ¤
3. $$\pmod N$$ āĻāĻŦāĻ $$\pmod p$$-āĻ¤ā§ $$N$$-āĻāĻ° āĻ¸āĻžāĻāĻā§āĻ˛ āĻāĻāĻ āĻšāĻ˛ā§ āĻāĻĒāĻ°ā§āĻ° āĻĒā§āĻ°ā§āĻā§āĻ°āĻžāĻŽ $$N$$ āĻā§āĻ¤ā§āĻ°āĻŋāĻŽ āĻšāĻā§āĻž āĻ¸āĻ¤ā§āĻŦā§āĻ āĻāĻ° āĻā§āĻĒāĻžāĻĻāĻ āĻā§āĻāĻā§ āĻĒāĻžāĻŦā§ āĻ¨āĻžāĨ¤ āĻāĻ°āĻāĻŽ āĻšāĻ˛ā§ $$f(x)$$ āĻĒāĻ˛āĻŋāĻ¨ā§āĻŽāĻŋā§āĻžāĻ˛āĻāĻŋ āĻĒāĻ°āĻŋāĻŦāĻ°ā§āĻ¤āĻ¨ āĻāĻ°ā§ āĻāĻŦāĻžāĻ° āĻā§āĻˇā§āĻāĻž āĻāĻ°āĻ¤ā§ āĻĒāĻžāĻ°āĨ¤

### āĻāĻŽāĻĒā§āĻ˛ā§āĻā§āĻ¸āĻŋāĻāĻŋ

āĻŽāĻ¨ā§ āĻāĻ°, $$\{a_i\}_{i=0}^{\infty}$$ āĻāĻāĻāĻŋ āĻ¸āĻ¤ā§āĻ¯āĻŋāĻāĻžāĻ°ā§ āĻ°âā§āĻ¯āĻžāĻ¨ā§āĻĄāĻŽ āĻ§āĻžāĻ°āĻžāĨ¤ āĻāĻ¨ā§āĻŽāĻĻāĻŋāĻ¨ā§āĻ° āĻ¸āĻŽāĻ¸ā§āĻ¯āĻž āĻāĻ¨ā§āĻ¯āĻžā§ā§, $$\pmod p$$-āĻ¤ā§ āĻāĻ¨āĻā§āĻ°ā§ā§ā§āĻ¨ā§āĻ āĻĻā§āĻāĻŋ āĻĒāĻĻ āĻĒāĻžāĻā§āĻžāĻ° āĻ¸āĻŽā§āĻ­āĻžāĻŦāĻ¨āĻž $$99\%$$ āĻšāĻ¤ā§ āĻšāĻ˛ā§ $$\sqrt{-2\times\ln(1-0.99)}\sqrt{p}$$-āĻāĻŋ āĻĒāĻĻ āĻ¨āĻŋāĻ¤ā§ āĻšāĻŦā§āĨ¤ āĻāĻ¤āĻāĻŦ, āĻ°ā§ āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽā§āĻ° āĻāĻŽāĻĒā§āĻ˛ā§āĻā§āĻ¸āĻŋāĻāĻŋ $$O(\sqrt p)\leq O\left(N^{\frac 1 4}\right)$$. [āĻāĻ°ā§āĻĨāĻžā§ $$N$$ āĻ¸āĻāĻā§āĻ¯āĻžāĻāĻŋāĻ¤ā§ $$k$$āĻāĻŋ āĻĄāĻŋāĻāĻŋāĻ āĻĨāĻžāĻāĻ˛ā§ āĻ°ā§ āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽā§āĻ° āĻ°āĻžāĻ¨āĻāĻžāĻāĻŽ $$O\left(10^{\frac k 4}\right)$$]
āĻāĻ¤āĻĒāĻ°ā§āĻŦā§āĻ° āĻā§ā§ā§ āĻāĻ°ā§āĻāĻā§ āĻ­āĻžāĻ˛ā§ āĻŦāĻžāĻāĻ¨ā§āĻĄ, āĻ¤āĻžāĻ āĻ¨āĻž? āĻĒāĻ°āĻŦāĻ°ā§āĻ¤ā§ āĻĒāĻ°ā§āĻŦā§ āĻāĻŽāĻ°āĻž āĻāĻ¨ āĻĒā§āĻ˛āĻžāĻ°ā§āĻĄā§āĻ°āĻ āĻāĻ°ā§āĻāĻāĻŋ āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽ āĻĻā§āĻāĻŦ, āĻ¯ā§āĻāĻŋāĻ° āĻ¨āĻžāĻŽ $$p-1$$ āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽāĨ¤

## āĻĒāĻ°āĻŋāĻļāĻŋāĻˇā§āĻ

### āĻāĻ¨ā§āĻŽāĻĻāĻŋāĻ¨ āĻ¸āĻŽāĻ¸ā§āĻ¯āĻž

āĻ¤ā§āĻŽāĻžāĻ° āĻĢā§āĻ¸āĻŦā§āĻ āĻĢā§āĻ°ā§āĻ¨ā§āĻĄāĻ˛āĻŋāĻ¸ā§āĻā§ āĻ¨ā§āĻ¨ā§āĻ¯āĻ¤āĻŽ āĻāĻ¤āĻāĻ¨ āĻĨāĻžāĻāĻ˛ā§ āĻāĻāĻĨāĻž āĻ¨āĻŋāĻļā§āĻāĻŋāĻ¤ āĻāĻ°ā§ āĻŦāĻ˛āĻž āĻ¯āĻžāĻŦā§ āĻ¯ā§ āĻāĻ¨ā§āĻ¤āĻ¤ āĻĻā§āĻāĻāĻ¨ āĻĢā§āĻ°ā§āĻ¨ā§āĻĄā§āĻ° āĻāĻ¨ā§āĻŽāĻĻāĻŋāĻ¨ āĻāĻāĻ āĻ¤āĻžāĻ°āĻŋāĻā§ āĻšāĻā§āĻžāĻ° āĻ¸āĻŽā§āĻ­āĻžāĻŦāĻ¨āĻž $$99\%$$?

āĻŽāĻ¨ā§ āĻāĻ°, āĻ¤ā§āĻŽāĻžāĻ° āĻĢā§āĻ°ā§āĻ¨ā§āĻĄāĻ˛āĻŋāĻ¸ā§āĻā§ $$m$$ āĻāĻ¨ āĻĢā§āĻ°ā§āĻ¨ā§āĻĄ āĻāĻā§, āĻāĻŦāĻ āĻā§āĻ¨ āĻĢā§āĻ°ā§āĻ¨ā§āĻĄā§āĻ° āĻāĻ¨ā§āĻŽāĻĻāĻŋāĻ¨ ā§¨ā§¯ āĻĢā§āĻŦā§āĻ°ā§ā§āĻžāĻ°āĻŋ āĻ¨ā§āĨ¤ āĻā§āĻ¨ āĻāĻāĻāĻ¨ āĻĢā§āĻ°ā§āĻ¨ā§āĻĄā§āĻ° āĻāĻ¨ā§āĻŽāĻĻāĻŋāĻ¨ ā§Ŧ āĻāĻā§āĻā§āĻŦāĻ° āĻšāĻ˛ā§ āĻāĻ° āĻā§āĻ¨ āĻĢā§āĻ°ā§āĻ¨ā§āĻĄā§āĻ° āĻāĻ¨ā§āĻŽāĻĻāĻŋāĻ¨ ā§Ŧ āĻāĻā§āĻā§āĻŦāĻ° āĻ¨āĻž āĻšāĻā§āĻžāĻ° āĻ¸āĻŽā§āĻ­āĻžāĻŦāĻ¨āĻž $$1-\frac {1}{365}$$. āĻāĻ°ā§āĻ āĻĢā§āĻ°ā§āĻ¨ā§āĻĄā§āĻ° āĻāĻ¨ā§āĻŽāĻĻāĻŋāĻ¨ āĻŽāĻ¨ā§ āĻāĻ° ā§Ē āĻāĻāĻ¸ā§āĻāĨ¤ āĻ¸ā§āĻ¤āĻ°āĻžāĻ, āĻ¤ā§āĻ¤ā§ā§ āĻā§āĻ¨ āĻĢā§āĻ°ā§āĻ¨ā§āĻĄā§āĻ° āĻāĻ¨ā§āĻŽāĻĻāĻŋāĻ¨ ā§Ŧ āĻāĻā§āĻā§āĻŦāĻ° āĻŦāĻž ā§Ē āĻāĻāĻ¸ā§āĻ āĻ¨āĻž āĻšāĻā§āĻžāĻ° āĻ¸āĻŽā§āĻ­āĻžāĻŦāĻ¨āĻž $$1-\frac {2}{365}$$. āĻāĻ¤āĻāĻŦ, $$m$$ āĻāĻ¨ āĻĢā§āĻ°ā§āĻ¨ā§āĻĄā§āĻ° āĻ­āĻŋāĻ¨ā§āĻ¨ āĻ­āĻŋāĻ¨ā§āĻ¨ āĻĻāĻŋāĻ¨ā§ āĻāĻ¨ā§āĻŽāĻĻāĻŋāĻ¨ āĻĒā§āĻžāĻ° āĻ¸āĻŽā§āĻ­āĻžāĻŦāĻ¨āĻž $\left(1-\frac {1}{365}\right)\cdots\left(1-\frac {m-1}{365}\right)$
āĻ¤āĻžāĻšāĻ˛ā§, āĻāĻ¨ā§āĻ¤āĻ¤ āĻĻā§āĻāĻ¨ āĻĢā§āĻ°ā§āĻ¨ā§āĻĄā§āĻ° āĻāĻ¨ā§āĻŽāĻĻāĻŋāĻ¨ āĻāĻāĻ āĻĻāĻŋāĻ¨ā§ āĻĒā§āĻžāĻ° āĻ¸āĻŽā§āĻ­āĻžāĻŦāĻ¨āĻž $1 – \left(1-\frac {1}{365}\right)\cdots\left(1-\frac {m-1}{365}\right)$
$$x$$-āĻāĻ° āĻŽāĻžāĻ¨ $$0$$-āĻāĻ° āĻāĻžāĻāĻžāĻāĻžāĻāĻŋ āĻšāĻ˛ā§ āĻāĻŽāĻ°āĻž āĻā§āĻāĻ˛āĻ°ā§āĻ° āĻ¸āĻŋāĻ°āĻŋāĻ āĻĨā§āĻā§ $$1-x\approx e^{-x}$$ āĻ˛āĻŋāĻāĻ¤ā§ āĻĒāĻžāĻ°āĻŋāĨ¤ āĻāĻ­āĻžāĻŦā§ āĻāĻĒāĻ°ā§āĻ° āĻ¸āĻŽā§āĻ­āĻžāĻŦāĻ¨āĻžāĻāĻŋāĻā§ āĻ¸āĻ°āĻ˛ āĻāĻ°ā§ āĻ˛āĻŋāĻāĻž āĻ¯āĻžā§ $1-e^{-\frac {1}{365}}\cdot e^{-\frac {2}{365}}\cdots e^{-\frac {m-1}{365}}$$\approx 1-e^{-\frac{m^2}{2\times 365}}$āĻāĻāĻ¨ $$1-e^{-\frac{m^2}{2\times 365}}\ge 0.99$$ āĻšāĻ¤ā§ āĻšāĻ˛ā§ $m\ge \sqrt{-2\times 365\ln(1-0.99)}\approx 58$ āĻšāĻ¤ā§ āĻšāĻŦā§āĨ¤

āĻ¤ā§āĻŽāĻžāĻ° āĻĢā§āĻ°ā§āĻ¨ā§āĻĄāĻ˛āĻŋāĻ¸ā§āĻā§ āĻŽāĻžāĻ¤ā§āĻ° $$58$$ āĻāĻ¨ āĻŽāĻžāĻ¨ā§āĻˇ āĻĨāĻžāĻāĻ˛ā§āĻ āĻ¤ā§āĻŽāĻŋ $$99\%$$ āĻā§āĻ¯āĻžāĻ°āĻžāĻ¨ā§āĻāĻŋ āĻĻāĻŋā§ā§ āĻŦāĻ˛āĻ¤ā§ āĻĒāĻžāĻ°āĻŦā§ āĻ¯ā§ āĻāĻ¨ā§āĻ¤āĻ¤ āĻĻā§āĻāĻāĻ¨ā§āĻ° āĻāĻ¨ā§āĻŽāĻĻāĻŋāĻ¨ āĻāĻāĻ āĻ¤āĻžāĻ°āĻŋāĻā§! āĻāĻ āĻŦāĻŋāĻā§āĻ¯āĻžāĻ¤ āĻ¸āĻŽāĻ¸ā§āĻ¯āĻžāĻāĻŋāĻ° āĻ¨āĻžāĻŽ āĻāĻ¨ā§āĻŽāĻĻāĻŋāĻ¨ āĻ¸āĻŽāĻ¸ā§āĻ¯āĻžāĨ¤

āĻ˛āĻā§āĻˇā§āĻ¯ āĻāĻ° āĻāĻ¨ā§āĻŽāĻĻāĻŋāĻ¨ā§āĻ° āĻ¸āĻŽāĻ¸ā§āĻ¯āĻžāĻ° āĻ¸āĻŽāĻžāĻ§āĻžāĻ¨ āĻĨā§āĻā§ āĻāĻāĻž āĻŦāĻ˛āĻž āĻ¯āĻžā§ āĻ¯ā§, $$0$$ āĻĨā§āĻā§ $$N-1$$ āĻāĻ° āĻŽāĻžāĻā§ $$m$$ āĻ¸āĻāĻā§āĻ¯āĻž āĻ¨āĻŋāĻ˛ā§ āĻā§āĻ¨ āĻāĻāĻāĻŋ āĻ¸āĻāĻā§āĻ¯āĻž āĻāĻ¨ā§āĻ¤āĻ¤ āĻĻā§āĻāĻŦāĻžāĻ° āĻ¨ā§āĻā§āĻžāĻ° āĻ¸āĻŽā§āĻ­āĻžāĻŦāĻ¨āĻž $$1-e^{-\frac{m^2}{2N}}$$.

# āĻāĻ¨ā§āĻāĻŋāĻāĻžāĻ° āĻĢā§āĻ¯āĻžāĻā§āĻā§āĻ°āĻžāĻāĻā§āĻļāĻ¨ āĻĒāĻ°ā§āĻŦ ā§Ļ

## āĻāĻŽāĻ°āĻž āĻā§āĻ¨ āĻāĻ¨ā§āĻāĻŋāĻāĻžāĻ° āĻĢā§āĻ¯āĻžāĻā§āĻā§āĻ°āĻžāĻāĻā§āĻļāĻ¨ āĻāĻ°āĻŋ

āĻāĻ¨ā§āĻā§āĻāĻžāĻ° āĻĢā§āĻ¯āĻžāĻā§āĻā§āĻ°āĻžāĻāĻā§āĻļāĻ¨ āĻāĻ°ā§āĻĨ āĻšāĻā§āĻā§ āĻāĻāĻāĻž āĻĒā§āĻ°ā§āĻŖāĻ¸āĻāĻā§āĻ¯āĻžāĻā§ āĻā§āĻĒāĻžāĻĻāĻā§ āĻŦāĻŋāĻļā§āĻ˛ā§āĻˇāĻŖ āĻāĻ°āĻžāĨ¤ āĻ¯ā§āĻŽāĻ¨ $$36 = 4\times 9$$. āĻāĻāĻžāĻ¨ā§ $$4$$ āĻāĻ° $$36$$ āĻāĻ­ā§ā§āĻ $$36$$-āĻāĻ° āĻā§āĻĒāĻžāĻĻāĻāĨ¤

āĻā§āĻāĻŦā§āĻ˛āĻžā§ āĻāĻŽāĻžāĻĻā§āĻ° āĻ¸āĻŦāĻžāĻ āĻāĻ¨ā§āĻā§āĻāĻžāĻ° āĻĢā§āĻ¯āĻžāĻā§āĻā§āĻ°āĻžāĻāĻā§āĻļāĻ¨ āĻāĻ°āĻ¤āĻžāĻŽāĨ¤ āĻā§āĻ¨ āĻāĻžāĻ¨ā§? āĻĒāĻ°ā§āĻā§āĻˇāĻžā§ āĻ¨āĻŽā§āĻŦāĻ° āĻĒāĻžāĻā§āĻžāĻ° āĻāĻ¨ā§āĻ¯! āĻĒā§āĻ°āĻļā§āĻ¨ā§ āĻāĻāĻāĻž āĻ¸āĻāĻā§āĻ¯āĻž āĻĻā§āĻā§āĻž āĻĨāĻžāĻāĻ¤ āĻāĻ° āĻāĻŽāĻ°āĻž āĻĻā§āĻ āĻĨā§āĻā§ āĻļā§āĻ°ā§ āĻāĻ°ā§ āĻāĻāĻāĻž āĻāĻāĻāĻž āĻ¸āĻāĻā§āĻ¯āĻž āĻĻāĻŋā§ā§ āĻĒā§āĻ°āĻļā§āĻ¨ā§ āĻĻā§āĻā§āĻž āĻ¸āĻāĻā§āĻ¯āĻžāĻāĻžāĻā§ āĻ­āĻžāĻ āĻĻāĻŋāĻ¤āĻžāĻŽāĨ¤ āĻ¯āĻāĻ¨ āĻ­āĻžāĻ āĻ¯ā§āĻ¤, āĻ¤āĻāĻ¨ āĻŦā§āĻāĻž āĻ¯ā§āĻ¤ āĻ¯ā§ āĻāĻāĻāĻž āĻā§āĻĒāĻžāĻĻāĻ (āĻŦāĻž āĻā§āĻŖāĻ¨ā§ā§āĻ) āĻĒā§ā§ā§ āĻā§āĻāĻŋāĨ¤ āĻā§āĻŦāĻ āĻ°ā§āĻāĻŋāĻ¨āĻŽāĻžāĻĢāĻŋāĻ āĻāĻāĻāĻž āĻāĻžāĻ, āĻ¤āĻžāĻ āĻ¨āĻž?

āĻ¤āĻŦā§ āĻŦāĻžāĻā§āĻāĻžāĻĻā§āĻ° āĻĒāĻ°ā§āĻā§āĻˇāĻžāĻ° āĻĒā§āĻ°āĻļā§āĻ¨ā§ āĻāĻ¸āĻž āĻāĻžā§āĻžāĻ āĻāĻ¨ā§āĻāĻŋāĻāĻžāĻ° āĻĢā§āĻ¯āĻžāĻā§āĻā§āĻ°āĻžāĻāĻā§āĻļāĻ¨ā§āĻ° āĻāĻ¨ā§āĻ¯āĻ°āĻāĻŽ āĻāĻāĻāĻž āĻā§āĻ°ā§āĻ¤ā§āĻŦ āĻāĻā§āĨ¤ āĻ¯ā§āĻŽāĻ¨- āĻāĻ¨āĻ˛āĻžāĻāĻ¨ā§ āĻ¤ā§āĻŽāĻžāĻ°, āĻāĻŽāĻžāĻ°, āĻ¸āĻāĻ˛ā§āĻ° āĻŦā§āĻ¯āĻā§āĻ¤āĻŋāĻāĻ¤ āĻ¤āĻĨā§āĻ¯ āĻĒāĻžāĻāĻŋ āĻ˛ā§āĻāĻĻā§āĻ° āĻšāĻžāĻ¤ āĻĨā§āĻā§ āĻ¸ā§āĻ°āĻā§āĻˇāĻŋāĻ¤ āĻ°āĻžāĻāĻ¤ā§ āĻā§āĻĒāĻ¨ āĻ¸āĻāĻā§āĻ¤ā§āĻ° āĻā§āĻžāĻ˛ā§ āĻ°āĻžāĻāĻž āĻšā§āĨ¤ āĻāĻ°āĻāĻŽ āĻāĻ¨ā§āĻ āĻā§āĻĒāĻ¨ āĻ¸āĻāĻā§āĻ¤ āĻŦāĻžāĻ¨āĻžāĻ¤ā§ āĻ āĻ­āĻžāĻāĻ¤ā§ āĻĻā§āĻāĻļ, āĻ¤āĻŋāĻ¨āĻļ āĻĄāĻŋāĻāĻŋāĻā§āĻ° āĻŦāĻŋāĻļāĻžāĻ˛ āĻŦāĻŋāĻļāĻžāĻ˛ āĻ¸āĻāĻā§āĻ¯āĻžāĻā§ āĻā§āĻĒāĻžāĻĻāĻā§ āĻŦāĻŋāĻļā§āĻ˛ā§āĻˇāĻŖ āĻāĻ°āĻ¤ā§ āĻšā§, āĻāĻŋāĻāĻŦāĻž āĻĒā§āĻ°āĻžāĻāĻŽ āĻā§āĻāĻā§ āĻŦā§āĻ° āĻāĻ°āĻ¤ā§ āĻšā§āĨ¤ āĻāĻ¸āĻŦ āĻšāĻŋāĻ¸ā§āĻŦ āĻāĻ¤ āĻŦā§ āĻšā§ āĻ¯ā§ āĻāĻžāĻ¤āĻž āĻāĻ˛āĻŽā§ āĻāĻ°āĻ¤ā§ āĻā§āĻ˛ā§ āĻāĻŽāĻžāĻĻā§āĻ° āĻā§āĻ˛ āĻĒā§āĻā§ āĻ¯āĻžāĻŦā§, āĻĒāĻžāĻ¤āĻžāĻ° āĻĒāĻ° āĻĒāĻžāĻ¤āĻž āĻĢā§āĻ°āĻŋā§ā§ āĻ¯āĻžāĻŦā§āĨ¤ āĻ¸ā§āĻāĻ¨ā§āĻ¯, āĻāĻŽāĻ°āĻž āĻ¤āĻāĻ¨ āĻāĻŽā§āĻĒāĻŋāĻāĻāĻžāĻ°ā§āĻ° āĻ¸āĻžāĻšāĻžāĻ¯ā§āĻ¯ āĻ¨ā§āĻāĨ¤

āĻāĻŋāĻ¨ā§āĻ¤ā§ āĻ¸āĻŽāĻ¸ā§āĻ¯āĻž āĻāĻŋ āĻāĻžāĻ¨ā§? āĻāĻŽā§āĻĒāĻŋāĻāĻāĻžāĻ° āĻā§āĻŦ āĻŦā§āĻāĻžāĨ¤ āĻ¯āĻĻāĻŋ āĻāĻŽāĻŋ āĻŦāĻ˛āĻŋ, “āĻāĻŽā§āĻĒāĻŋāĻāĻāĻžāĻ°, āĻāĻŽāĻžāĻ° āĻāĻāĻāĻž āĻšāĻŋāĻ¸ā§āĻŦā§ $$731$$-āĻāĻ° āĻā§āĻĒāĻžāĻĻāĻā§ āĻŦāĻŋāĻļā§āĻ˛ā§āĻˇāĻŖ āĻ˛āĻžāĻāĻŦā§āĨ¤ āĻ¤ā§āĻŽāĻŋ āĻāĻ āĻāĻ°ā§ āĻ¸ā§āĻāĻž āĻŦā§āĻ° āĻāĻ°ā§ āĻĻāĻžāĻ āĻ¤ā§ āĻĻā§āĻāĻŋ!”, āĻ¸ā§ āĻšāĻž āĻāĻ°ā§ āĻŦāĻ¸ā§ āĻĨāĻžāĻāĻŦā§āĨ¤ āĻāĻžāĻ°āĻŖ āĻ¸ā§ āĻ¤ā§ āĻāĻ° āĻāĻžāĻ¨ā§ āĻ¨āĻž āĻā§āĻ­āĻžāĻŦā§ āĻā§āĻĒāĻžāĻĻāĻā§ āĻŦāĻŋāĻļā§āĻ˛ā§āĻˇāĻŖ āĻāĻ°āĻ¤ā§ āĻšā§!

āĻāĻŽā§āĻĒāĻŋāĻāĻāĻžāĻ°āĻā§ āĻĻāĻŋā§ā§ āĻā§āĻĒāĻžāĻĻāĻā§ āĻŦāĻŋāĻļā§āĻ˛ā§āĻˇāĻŖ āĻāĻ°āĻžāĻ¨ā§āĻ° āĻāĻ¨ā§āĻ¯ āĻ¤āĻžāĻā§ āĻ¤ā§āĻŽāĻžāĻ° āĻĒā§āĻ°āĻžāĻāĻŽāĻžāĻ°āĻŋāĻ° āĻŦāĻžāĻā§āĻāĻžāĻĻā§āĻ° āĻŽāĻ¤ āĻāĻāĻā§ āĻāĻāĻā§ āĻāĻ°ā§ āĻŦā§āĻāĻŋā§ā§ āĻŦāĻ˛āĻ¤ā§ āĻšāĻŦā§, “āĻāĻŽā§āĻĒāĻŋāĻāĻāĻžāĻ°, $$2$$ āĻĨā§āĻā§ $$730$$ āĻĒāĻ°ā§āĻ¯āĻ¨ā§āĻ¤ āĻĒā§āĻ°āĻ¤āĻŋāĻāĻŋ āĻ¸āĻāĻā§āĻ¯āĻž āĻĻāĻŋā§ā§ $$731$$-āĻā§ āĻ­āĻžāĻ āĻĻāĻžāĻāĨ¤ āĻ¯āĻĻāĻŋ āĻā§āĻ¨āĻāĻž āĻĻāĻŋā§ā§ āĻ¨āĻŋāĻāĻļā§āĻˇā§ āĻ­āĻžāĻ āĻ¯āĻžā§, āĻ¤āĻŦā§ āĻ¸ā§āĻ āĻ¸āĻāĻā§āĻ¯āĻž āĻāĻŦāĻ āĻ­āĻžāĻāĻĢāĻ˛ āĻāĻŽāĻžāĻā§ āĻĻā§āĻāĻžāĻāĨ¤”

def factor(N):
for d in range(2, abs(N) + 1):
if N % d == 0: return d

N = int(raw_input())
d = 1 if(2 > N > -2) else factor(N)
print d, '*', N / d


āĻāĻŽā§āĻĒāĻŋāĻāĻāĻžāĻ° āĻ¯ā§āĻšā§āĻ¤ā§ āĻŦāĻžāĻāĻ˛āĻž āĻĒāĻžāĻ°ā§ āĻ¨āĻž, āĻ¤āĻžāĻ āĻ¸ā§ āĻŦā§āĻā§ āĻāĻŽāĻ¨ āĻāĻāĻāĻŋ āĻ­āĻžāĻˇāĻž āĻĒāĻžāĻāĻĨāĻ¨ā§ āĻāĻŽāĻ°āĻž āĻāĻŽāĻžāĻĻā§āĻ° āĻāĻĨāĻžāĻā§āĻ˛ā§ āĻ˛āĻŋāĻā§āĻāĻŋāĨ¤ āĻāĻ āĻā§āĻĄā§ āĻāĻāĻāĻŋ āĻĒā§āĻ°ā§āĻŖāĻ¸āĻāĻā§āĻ¯āĻž $$N$$-āĻā§ āĻāĻ¨āĻĒā§āĻ āĻšāĻŋāĻ¸ā§āĻŦā§ āĻĻā§āĻā§āĻž āĻšāĻŦā§āĨ¤ āĻāĻ° āĻāĻŽā§āĻĒāĻŋāĻāĻāĻžāĻ° āĻ¸āĻžāĻĨā§ āĻ¸āĻžāĻĨā§ $$N$$-āĻā§ āĻā§āĻĒāĻžāĻĻāĻā§ āĻŦāĻŋāĻļā§āĻ˛ā§āĻˇāĻŖ āĻāĻ°ā§ āĻā§āĻļāĻŋāĻŽāĻ¨ā§ āĻāĻŽāĻžāĻĻā§āĻ° āĻāĻžāĻ¨āĻŋā§ā§ āĻĻā§āĻŦā§āĨ¤ āĻ¯āĻ¤ āĻŦā§ āĻ¸āĻāĻā§āĻ¯āĻžāĻ āĻšā§āĻ āĻ¨āĻž āĻā§āĻ¨, āĻāĻŽāĻžāĻĻā§āĻ° āĻā§āĻ˛ā§āĻŦā§āĻ˛āĻžā§ āĻļā§āĻāĻž āĻ¨āĻŋā§āĻŽ āĻĻāĻŋā§ā§ āĻ¤āĻžāĻ° āĻā§āĻĒāĻžāĻĻāĻ āĻŦā§āĻ° āĻāĻ°āĻž āĻ¸āĻŽā§āĻ­āĻŦāĨ¤

āĻāĻĒāĻ°ā§āĻ° āĻĒā§āĻ°ā§āĻā§āĻ°āĻžāĻŽā§ $$731$$ āĻāĻ¨āĻĒā§āĻ āĻĻāĻŋāĻ˛ā§ āĻāĻŽā§āĻĒāĻŋāĻāĻāĻžāĻ° āĻāĻŽāĻžāĻĻā§āĻ° āĻŦāĻ˛ā§ āĻĻā§āĻŦā§ āĻ¯ā§ $$731 = 17\times 43$$.

āĻāĻŦāĻžāĻ° āĻāĻāĻāĻž āĻāĻžāĻ āĻāĻ°āĨ¤ āĻāĻĒāĻ°ā§āĻ° āĻĒā§āĻ°ā§āĻā§āĻ°āĻžāĻŽāĻāĻŋ āĻāĻžāĻ˛āĻŋā§ā§ $$N = 18446744073709551619$$ āĻāĻ¨āĻĒā§āĻ āĻĻāĻžāĻāĨ¤ āĻā§ āĻšāĻ˛?

āĻĒā§āĻ°ā§āĻā§āĻ°āĻžāĻŽāĻāĻŋ āĻāĻ° āĻĨāĻžāĻŽāĻā§ āĻ¨āĻžāĨ¤

āĻāĻ° āĻāĻžāĻ°āĻŖ āĻšāĻā§āĻā§ āĻāĻĒāĻ°ā§āĻ° āĻĒā§āĻ°ā§āĻā§āĻ°āĻžāĻŽā§ āĻāĻŽā§āĻĒāĻŋāĻāĻāĻžāĻ°āĻā§ $$2$$ āĻĨā§āĻā§ $$N-1$$ āĻĒāĻ°ā§āĻ¯āĻ¨ā§āĻ¤ āĻ¸āĻāĻ˛ āĻ¸āĻāĻā§āĻ¯āĻž āĻĻāĻŋā§ā§āĻ $$N$$-āĻā§ āĻ­āĻžāĻ (āĻĒā§āĻ°āĻā§āĻ¤āĻĒāĻā§āĻˇā§ āĻŽāĻĄā§āĻ˛āĻžāĻ¸ āĻ¨āĻŋāĻ°ā§āĻŖā§) āĻāĻ°āĻ¤ā§ āĻšāĻā§āĻā§āĨ¤ āĻāĻŽā§āĻĒāĻŋāĻāĻāĻžāĻ°ā§āĻ° āĻĒā§āĻ°āĻ¤āĻŋāĻāĻž āĻ­āĻžāĻ āĻāĻ°āĻ¤ā§ āĻāĻŋāĻā§āĻāĻž āĻ¸āĻŽā§ āĻ˛āĻžāĻā§āĨ¤ āĻ¤āĻžāĻ $$N$$ āĻ¯āĻ¤ āĻŦā§ āĻšāĻŦā§, āĻāĻŽā§āĻĒāĻŋāĻāĻāĻžāĻ°āĻā§ āĻ¤āĻ¤ āĻŦā§āĻļāĻŋ āĻ¸āĻāĻā§āĻ¯āĻž āĻĻāĻŋā§ā§ āĻ­āĻžāĻ āĻāĻ°āĻ¤ā§ āĻšāĻŦā§, āĻāĻŦāĻ āĻĒā§āĻ°ā§āĻā§āĻ°āĻžāĻŽā§āĻ° āĻ°āĻžāĻ¨ āĻāĻ°āĻ¤ā§ āĻ¸āĻŽā§ (āĻ°āĻžāĻ¨āĻāĻžāĻāĻŽ) āĻŦā§āĻļāĻŋ āĻ˛āĻžāĻāĻŦā§āĨ¤ āĻ°āĻžāĻ¨āĻāĻžāĻāĻŽ $$N$$-āĻāĻ° āĻ¸āĻžāĻĨā§ āĻĒāĻžāĻ˛ā§āĻ˛āĻž āĻĻāĻŋā§ā§ āĻāĻ¤ āĻĻā§āĻ°ā§āĻ¤ āĻŦāĻžā§āĻŦā§ āĻ¸ā§āĻāĻžāĻ° āĻāĻāĻāĻž āĻ§āĻžāĻ°āĻŖāĻžāĻ āĻāĻŽāĻ°āĻž āĻĒā§āĻ¤ā§ āĻĒāĻžāĻ°āĻŋāĨ¤

āĻ§āĻ° $$N$$ āĻ¸āĻāĻā§āĻ¯āĻžāĻāĻŋāĻ¤ā§ $$k$$ āĻ¸āĻāĻā§āĻ¯āĻ āĻĄāĻŋāĻāĻŋāĻ āĻāĻā§āĨ¤ āĻāĻŽāĻ°āĻž āĻāĻ¸āĻ¨ā§āĻ¨āĻ­āĻžāĻŦā§ $$N\approx 10^k$$ āĻ§āĻ°āĻ¤ā§ āĻĒāĻžāĻ°āĻŋāĨ¤ āĻ¯āĻĻāĻŋ $$N$$ āĻāĻāĻāĻŋ āĻŽā§āĻ˛āĻŋāĻ āĻ¸āĻāĻā§āĻ¯āĻž āĻšā§, āĻ¤āĻŦā§ āĻĒā§āĻ°ā§āĻā§āĻ°āĻžāĻŽ ā§§-āĻ $$N$$-āĻā§ $$2$$ āĻĨā§āĻā§ $$N-1$$ āĻĒāĻ°ā§āĻ¯āĻ¨ā§āĻ¤ āĻ¸āĻāĻ˛ āĻ¸āĻāĻā§āĻ¯āĻž āĻĻāĻŋā§ā§āĻ āĻ­āĻžāĻ āĻāĻ°āĻž āĻšāĻŦā§āĨ¤ āĻ¯āĻĻāĻŋ āĻĒā§āĻ°āĻ¤āĻŋāĻŦāĻžāĻ° āĻ­āĻžāĻ āĻāĻ°āĻ¤ā§ āĻ¸āĻ°ā§āĻŦā§āĻā§āĻ $$c$$ āĻĒāĻ°āĻŋāĻŽāĻžāĻŖ āĻ¸āĻŽā§ āĻ˛āĻžāĻā§, āĻ¤āĻŦā§ āĻāĻĒāĻ°ā§āĻ° āĻĒā§āĻ°ā§āĻā§āĻ°āĻžāĻŽāĻāĻŋ āĻ°āĻžāĻ¨ āĻāĻ°āĻ¤ā§ āĻ¸āĻ°ā§āĻŦā§āĻā§āĻ $$Nc=10^{k}c$$ āĻ¸āĻŽā§ āĻ˛āĻžāĻāĻŦā§āĨ¤ āĻāĻ° āĻāĻ°ā§āĻĨ āĻšāĻā§āĻā§, āĻĄāĻŋāĻāĻŋāĻā§āĻ° āĻ¸āĻāĻā§āĻ¯āĻž āĻŦāĻžā§āĻžāĻ° āĻ¸āĻžāĻĨā§ āĻ¸āĻžāĻĨā§ āĻāĻĒāĻ°ā§āĻ° āĻĒā§āĻ°ā§āĻā§āĻ°āĻžāĻŽā§āĻ° āĻ°āĻžāĻ¨āĻāĻžāĻāĻŽāĻ āĻ¸ā§āĻāĻā§ā§āĻ­āĻžāĻŦā§ āĻŦā§āĻĻā§āĻ§āĻŋ āĻĒāĻžā§āĨ¤ [āĻŦāĻž, āĻŦāĻŋāĻ O āĻ¨ā§āĻā§āĻļāĻ¨ā§ āĻāĻĒāĻ°ā§āĻ° āĻĒā§āĻ°ā§āĻā§āĻ°āĻžāĻŽā§āĻ° āĻ°āĻžāĻ¨āĻāĻžāĻāĻŽ $$O(10^{k})$$]

āĻĒā§āĻ°ā§āĻā§āĻ°āĻžāĻŽāĻŋāĻ-āĻ āĻ°āĻžāĻ¨āĻāĻžāĻāĻŽ āĻ¸ā§āĻāĻā§ā§āĻ­āĻžāĻŦā§ āĻŦāĻžā§āĻž āĻā§āĻŦāĻ āĻĻā§āĻāĻā§āĻ° āĻāĻāĻāĻŋ āĻāĻĨāĻžāĨ¤ āĻāĻžāĻ°āĻŖ āĻāĻ¨āĻĒā§āĻā§āĻ° āĻāĻāĻā§āĻāĻžāĻ¨āĻŋ āĻĒāĻ°āĻŋāĻŦāĻ°ā§āĻ¤āĻ¨ā§ āĻĒā§āĻ°ā§āĻā§āĻ°āĻžāĻŽā§āĻ° āĻ°āĻžāĻ¨āĻāĻžāĻāĻŽā§ āĻ°āĻžāĻ¤āĻĻāĻŋāĻ¨ āĻĒāĻ°āĻŋāĻŦāĻ°ā§āĻ¤āĻ¨ āĻšā§ā§ āĻ¯ā§āĻ¤ā§ āĻĒāĻžāĻ°ā§āĨ¤

āĻŽāĻ¨ā§ āĻāĻ° āĻ¤ā§āĻŽāĻžāĻ° āĻāĻžāĻā§ āĻ¯āĻĻāĻŋ āĻā§āĻ¨ āĻŽāĻšāĻžāĻā§āĻˇāĻŽāĻ¤āĻžāĻ§āĻ° āĻ¸ā§āĻĒāĻžāĻ° āĻāĻŽā§āĻĒāĻŋāĻāĻāĻžāĻ° āĻāĻā§ āĻ¯ā§ $$200$$ āĻĄāĻŋāĻāĻŋāĻā§āĻ° āĻāĻāĻāĻž āĻ¸āĻāĻā§āĻ¯āĻžāĻ° āĻā§āĻĒāĻžāĻĻāĻā§ āĻŦāĻŋāĻļā§āĻ˛ā§āĻˇāĻŖ āĻĒā§āĻ°ā§āĻā§āĻ°āĻžāĻŽ ā§§ āĻĻāĻŋā§ā§ $$1$$ āĻ¸ā§āĻā§āĻ¨ā§āĻĄā§ āĻŦā§āĻ° āĻāĻ°āĻ¤ā§ āĻĒāĻžāĻ°ā§āĨ¤ āĻ¤āĻžāĻšāĻ˛ā§ $$210$$ āĻĄāĻŋāĻāĻŋāĻā§āĻ° āĻāĻāĻāĻž āĻ¸āĻāĻā§āĻ¯āĻžāĻ° āĻā§āĻĒāĻžāĻĻāĻā§ āĻŦāĻŋāĻļā§āĻ˛ā§āĻˇāĻŖ āĻāĻ°āĻ¤ā§ āĻāĻŽā§āĻĒāĻŋāĻāĻāĻžāĻ°āĻāĻŋāĻ° āĻ¸āĻŽā§ āĻ˛āĻžāĻāĻŦā§ $$10^{210-200}=10^{10}$$ āĻ¸ā§āĻā§āĻ¨ā§āĻĄ $$\approx 317$$ āĻŦāĻāĻ°!

āĻāĻŽāĻĻā§āĻ° āĻā§āĻŦāĻ¨āĻāĻž āĻā§āĻŦ āĻā§āĻ, āĻāĻžāĻ¨ā§? āĻāĻāĻāĻž āĻĒā§āĻ°ā§āĻā§āĻ°āĻžāĻŽā§āĻ° āĻāĻāĻāĻĒā§āĻ āĻĻā§āĻā§ āĻ¯āĻžāĻā§āĻžāĻ° āĻāĻ¨ā§āĻ¯ āĻāĻŽāĻžāĻĻā§āĻ° $$317$$ āĻŦāĻāĻ° āĻŦā§āĻāĻā§ āĻĨāĻžāĻāĻž āĻ¸āĻŽā§āĻ­āĻŦ āĻ¨āĻžāĨ¤ āĻ¤āĻžāĻ āĻā§āĻŦ āĻĢāĻžāĻ¸ā§āĻ āĻā§āĻ¨ āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽ āĻĻāĻ°āĻāĻžāĻ°āĨ¤

āĻĒā§āĻ°ā§āĻā§āĻ°āĻžāĻŽ ā§§-āĻā§āĻ āĻāĻ¨ā§āĻāĻāĻžāĻ¨āĻŋ āĻĢāĻžāĻ¸ā§āĻ āĻŦāĻžāĻ¨āĻžāĻ¨ā§ āĻ¯āĻžā§ āĻ¯āĻĻāĻŋ āĻāĻŽāĻ°āĻž $$N-1$$ āĻāĻ° āĻĒāĻ°āĻŋāĻŦāĻ°ā§āĻ¤ā§ $$\sqrt{N}$$ āĻĒāĻ°ā§āĻ¯āĻ¨ā§āĻ¤ āĻĒā§āĻ°āĻ¤āĻŋāĻāĻž āĻ¸āĻāĻā§āĻ¯āĻž āĻĻāĻŋā§ā§ āĻ­āĻžāĻ āĻĻā§āĻāĨ¤ āĻā§āĻ¨āĻ¨āĻž āĻĒā§āĻ°āĻ¤āĻŋāĻāĻŋ āĻā§āĻ¤ā§āĻ°āĻŋāĻŽ āĻ¸āĻāĻā§āĻ¯āĻžāĻ° $$\sqrt N$$-āĻāĻ° āĻŽāĻžāĻā§āĻ āĻāĻ¨ā§āĻ¤āĻ¤ āĻāĻāĻāĻž āĻā§āĻĒāĻžāĻĻāĻ āĻĨāĻžāĻā§āĨ¤ āĻāĻ° āĻ¯āĻĻāĻŋ āĻā§āĻĒāĻžāĻĻāĻ āĻ¨āĻž āĻĒāĻžāĻā§āĻž āĻ¯āĻžā§, āĻ¤āĻŦā§ āĻ¸āĻāĻā§āĻ¯āĻžāĻāĻŋ āĻĒā§āĻ°āĻžāĻāĻŽāĨ¤ āĻāĻ āĻĒāĻ°āĻŋāĻŦāĻ°ā§āĻ¤āĻ¨ā§āĻ° āĻĢāĻ˛ā§ āĻāĻŽāĻžāĻĻā§āĻ° āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽā§āĻ° āĻ°āĻžāĻ¨āĻāĻžāĻāĻŽ āĻšāĻŦā§ $$10^{\frac k 2}c$$ [āĻŦāĻž $$O\left(10^{\frac k 2}\right)$$]. āĻāĻŋāĻ¨ā§āĻ¤ā§ āĻāĻāĻžāĻ āĻ¯ā§ āĻ¸ā§āĻāĻā§ā§ āĻšāĻžāĻ°ā§ āĻŦāĻžā§ā§!

āĻāĻ° āĻĨā§āĻā§ āĻĢāĻžāĻ¸ā§āĻ āĻāĻŋ āĻā§āĻ¨ āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽ āĻ¨ā§āĻ? āĻāĻ¤ā§āĻ¤āĻ°āĻāĻž āĻšāĻā§āĻā§, āĻšā§āĻ¯āĻžāĻ āĻāĻā§āĨ¤ āĻ¤āĻŦā§ āĻ¸ā§āĻāĻŋ āĻāĻžāĻ¨āĻ¤ā§ āĻšāĻ˛ā§ āĻ¤ā§āĻŽāĻžāĻ° āĻŽāĻĄā§āĻ˛āĻžāĻ° āĻāĻ°āĻŋāĻĨāĻŽā§āĻāĻŋāĻ āĻ¸āĻŽā§āĻĒāĻ°ā§āĻā§ āĻšāĻžāĻ˛āĻāĻž āĻĒāĻžāĻ¤āĻ˛āĻž āĻ§āĻžāĻ°āĻŖāĻž āĻ˛āĻžāĻāĻŦā§āĨ¤

āĻ¯āĻĻāĻŋ $$a$$ āĻāĻŦāĻ $$b$$ āĻā§ $$n$$ āĻĻāĻŋā§ā§ āĻ­āĻžāĻ āĻāĻ°āĻ˛ā§ āĻāĻāĻ āĻ­āĻžāĻāĻļā§āĻˇ āĻĨāĻžāĻā§, āĻ¤āĻžāĻšāĻ˛ā§ āĻāĻŽāĻ°āĻž āĻ˛āĻŋāĻāĻŋ $$a \equiv b\pmod{n}$$. āĻāĻāĻžāĻā§ āĻĒā§āĻž āĻšā§ $$a$$ is congruent to $$b$$ modulo $$n$$. āĻ¯ā§āĻŽāĻ¨: $$57\equiv 112\pmod{55}$$.

āĻ˛āĻā§āĻˇā§āĻ¯ āĻāĻ° āĻ¯ā§, āĻ¯āĻĻāĻŋ $$n$$ āĻĻāĻŋā§ā§ $$a$$-āĻā§ āĻ­āĻžāĻ āĻāĻ°āĻ˛ā§ $$r$$ āĻ­āĻžāĻāĻļā§āĻˇ āĻĨāĻžāĻā§, āĻ¤āĻŦā§ $$a\equiv r\pmod{n}$$ āĻ˛āĻŋāĻāĻž āĻ¯āĻžā§āĨ¤ āĻ¯ā§āĻŽāĻ¨: $$57\equiv 2\pmod{55}$$.

āĻ¯ā§āĻā§āĻ¨ āĻĒā§āĻ°ā§āĻŖāĻ¸āĻāĻā§āĻ¯āĻžāĻā§ āĻ¯āĻĻāĻŋ $$55$$ āĻĻāĻŋā§ā§ āĻ­āĻžāĻ āĻāĻ°, āĻ¤āĻŦā§ āĻ¤ā§āĻŽāĻŋ $$0$$ āĻĨā§āĻā§ $$54$$ āĻāĻ° āĻŽāĻžāĻā§ āĻā§āĻ¨ āĻāĻāĻāĻŋ āĻ­āĻžāĻāĻļā§āĻˇ āĻĒāĻžāĻŦā§āĨ¤ āĻ¤āĻžāĻšāĻ˛ā§, āĻ¤ā§āĻŽāĻŋ āĻ¯āĻĻāĻŋ āĻāĻ¨ā§āĻāĻā§āĻ˛ā§ āĻ°âā§āĻ¯āĻžāĻ¨ā§āĻĄāĻŽ āĻĒā§āĻ°ā§āĻŖāĻ¸āĻāĻā§āĻ¯āĻžāĻ° āĻ¨āĻžāĻ, āĻāĻĻā§āĻ° āĻŽāĻžāĻā§ $$\pmod {55}$$-āĻ āĻāĻ¨āĻā§āĻ°ā§ā§ā§āĻ¨ā§āĻ, āĻāĻ°ā§āĻĨāĻžā§ $$55$$ āĻĻāĻŋā§ā§ āĻ­āĻžāĻ āĻāĻ°āĻ˛ā§ āĻāĻāĻ āĻ­āĻžāĻāĻļā§āĻˇ āĻĨāĻžāĻā§, āĻāĻŽāĻ¨ āĻĻā§āĻāĻŋ āĻĒā§āĻ°ā§āĻŖāĻ¸āĻāĻā§āĻ¯āĻž āĻĒāĻžāĻā§āĻžāĻ° āĻāĻŋāĻā§āĻāĻž āĻ¸āĻŽā§āĻ­āĻžāĻŦāĻ¨āĻž āĻĨāĻžāĻā§, āĻ¤āĻžāĻ āĻ¨āĻž? āĻ¯āĻ¤ āĻŦā§āĻļāĻŋ āĻ¸āĻāĻā§āĻ¯āĻž āĻ¨ā§āĻŦā§, āĻāĻ āĻ¸āĻŽā§āĻ­āĻžāĻŦāĻ¨āĻžāĻ āĻ¤āĻ¤ āĻŦāĻžā§āĻŦā§āĨ¤

āĻāĻŦāĻžāĻ°, āĻāĻāĻ āĻ¸āĻāĻā§āĻ¯āĻžāĻā§āĻ˛āĻŋāĻ° āĻŽāĻžāĻā§ $$\pmod {5}$$-āĻ āĻāĻ¨āĻā§āĻ°ā§ā§ā§āĻ¨ā§āĻ āĻĻā§āĻāĻŋ āĻ¸āĻāĻā§āĻ¯āĻž āĻĒāĻžāĻā§āĻžāĻ° āĻ¸āĻŽā§āĻ­āĻžāĻŦāĻ¨āĻžāĻ āĻĨāĻžāĻā§āĨ¤ āĻāĻŋāĻ¨ā§āĻ¤ā§ āĻāĻ āĻ¸āĻŽā§āĻ­āĻžāĻŦāĻ¨āĻž $$\pmod{55}$$-āĻ āĻāĻ¨āĻā§āĻ°ā§ā§ā§āĻ¨ā§āĻ āĻšāĻā§āĻžāĻ° āĻ¸āĻŽā§āĻ­āĻžāĻŦāĻ¨āĻžāĻ° āĻā§ā§ā§ āĻāĻ¨ā§āĻ āĻŦā§āĻļāĻŋāĨ¤ āĻā§āĻ¨āĻ¨āĻž, $$\pmod{5}$$-āĻ āĻ¤ā§ āĻāĻžāĻ˛āĻŋ $$0$$ āĻĨā§āĻā§ $$4$$ āĻĒāĻ°ā§āĻ¯āĻ¨ā§āĻ¤ āĻ­āĻžāĻāĻļā§āĻˇ āĻāĻ¸āĻ¤ā§ āĻĒāĻžāĻ°ā§āĨ¤

āĻāĻ āĻ§āĻžāĻ°āĻŖāĻžāĻā§ āĻŦā§āĻ¯āĻŦāĻšāĻžāĻ° āĻāĻ°ā§ āĻā§āĻĒāĻžāĻĻāĻā§ āĻŦāĻŋāĻļā§āĻ˛ā§āĻˇāĻŖā§āĻ° āĻāĻāĻāĻŋ āĻāĻŽā§āĻāĻžāĻ° āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽ āĻ°ā§ā§āĻā§, āĻ¯āĻžāĻ° āĻ¨āĻžāĻŽ āĻĒā§āĻ˛āĻžāĻ°ā§āĻĄā§āĻ° āĻ°ā§($$\rho$$) āĻāĻ˛āĻā§āĻ°āĻŋāĻĻāĻŽāĨ¤ āĻĒāĻ°āĻŦāĻ°ā§āĻ¤ā§ āĻĒāĻ°ā§āĻŦā§ āĻāĻāĻŋ āĻ¨āĻŋā§ā§ āĻāĻ˛ā§āĻāĻ¨āĻž āĻāĻ°āĻŦāĨ¤

# Guidelines to Open a Successful Math Club

[I run Mymensingh Parallel Math School (MPMS), a free-for-all math club whose members (including me) have consistently won many prizesÂ  in Regional, National and International Mathematical Olympiads. Naturally, many math enthusiasts often ask me for tips on starting math clubs. So, 4 years ago, I wrote the following short note. I have decided to republish it here for future references.]

Unlike seeking for philosopher’s stone, starting a math club is very easy. You see, it requires only two things: a few classrooms and some members. Even a ‘teacher’ is not needed because the classes can find their way all by themselves! Although first a few month they need an instructor to teach them how to walk all-alone.

Through this tender age you have to be a bit careful. Try to drive the class in a relaxed mood so that everybody feels free to join in the discussion. It’s a very, very important thing for encouraging everyone to share his comments and ideas with others. In fact continuing this practice one day enables them to take the duster and the chalks in own hands. Moreover, we advise you to look for the true dedicated persons amongst the members. They will run it and never leave it. In this process MPMS has got its perfect structure.

May be the mostly asked questions are all about selecting class-topic. And yeah, this is too difficult to answer. Actually you can choose anything of your choice. There is neither any limitation nor any boundary. Math may appear boring sometimes. So why you don’t look at physics or literature then? In MPMS, physics, chemistry, economics, literature, biology-even philosophy take place frequently in the chaos. Also it is wise to discuss attractive topics like combinatorics at the early stage. Later you may go through harder things day by day depending on everybody’s capability to cope with it.

So…turn off your computer and come out to the field. See you at the BdMO National… đ

# An interesting application of AM-GM to prove the upper bound for the harmonic numbers

Harmonic series is a very well-known divergent series defined by
$\sum_{k=1}^\infty \frac 1 k =Â 1+\frac 1 2 +\frac 1 3+\frac 1 4\cdots$

The partial sum of first $$n$$ terms of this series is called the $$n$$th harmonic number. In other words, $H_n = \sum_{k=1}^n\frac 1 k$

Although there is no nice and simple formula for computing $$H_n$$, we can, however, do some approximation. For example, Euler proved $H_n = \ln(n)+\gamma+\varepsilon_n < \ln(n)+1$

where $$\gamma$$ is theÂ EulerâMascheroni constant and $$\varepsilon_n\approx \frac 1 {2n}$$. I shall prove this bound here with AM-GM Inequality, which says, for positive real $$a_i$$s, that
$\frac 1 n \left(\sum_{i=1}^n a_i\right)\ge \sqrt[n]{\prod_{i=1}^n a_i}$

So we can write $1+\sum_{k=2}^n \frac{k-1}{k}> n\sqrt[n]{\prod_{k=2}^n \frac{k-1}{k}}=n\sqrt[n]{\frac{1}{n}}$
The inequality is strict since the $$\frac {k-1}k$$s are not equal. Also note that

$\sum_{k=2}^n \frac{k-1}{k}=\sum_{k=1}^n 1-\frac{1}{k}=n-H_n$

Plugging it back to the main inequality, we derive that

$1+n-H_n>n\sqrt[n]{\frac{1}{n}}$

And by rewriting

$1+n\left(1-\sqrt[n]{\frac{1}{n}}\right)>H_n$

Now, all we need to prove is

$\ln(n)\ge n\left(1-\sqrt[n]{\frac{1}{n}}\right)$

Assume $$e^m = n$$ and $$\dfrac {m} {e^m} = x$$. The previous inequality can be rewritten as

$m \ge e^m(1-e^{-x})$

It can be further simplified to

$x+e^{-x}\ge 1$

Now, the derivative of $$f(x)=x+e^{-x}$$ is $$1-e^{-x}$$, which is non-negative in $$[0, \infty )$$. And we also have $$f(0)=1$$. Therefore, we definitely have $$\displaystyle x+e^{-x}\ge 1$$ and we are done.

Remarks:

1. $\ln(n)\ge n\left(1-\sqrt[n]{\frac{1}{n}}\right)$
A weird inequality. You can even see from the previous proof that
$\lim_{n\to\infty}n\left(1-\sqrt[n]{\frac{1}{n}}\right) = \ln (n)$
Perhaps, with some luck, it can be used to derive some more interesting results. Gotta think later.
2. In my proof, the $$1$$ beside $$\ln(n)$$ just sat there to initiate the AM-GM. If we replace it by some function $$\lambda(n)$$ and do the calculation, we might be able to optimize our inequality down to the $$\gamma$$ bound. But I’m done for today. Anyone interested might give it a shot.