Category Archives: Maths

The Maths Behind Logistic Regression

I got it wrong 🙁

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.

Continue reading The Maths Behind Logistic Regression

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\]

Continue reading Prime Counting Function and Chebyshev Bounds

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)
        lead += 1
        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){
        if(lead == power){
            hare = tortoise;
            power *= 2;
            lead = 0;
        }
        tortoise = f(tortoise);
        lead++;
        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}}\).

āχāĻ¨ā§āϟāĻŋāϜāĻžāϰ āĻĢā§āϝāĻžāĻ•ā§āĻŸā§‹āϰāĻžāχāĻœā§‡āĻļāύ āĻĒāĻ°ā§āĻŦ ā§Ļ

āχāĻ¨ā§āϟāĻŋāϜāĻžāϰ āĻĢā§āϝāĻžāĻ•ā§āĻŸā§‹āϰāĻžāχāĻœā§‡āĻļāύ: āĻĒāĻ°ā§āĻŦ ā§§ āĻĒā§‹āϞāĻžāĻ°ā§āĻĄā§‡āϰ āϰ⧋ (rho) āĻāϞāĻ—ā§‹āϰāĻŋāĻĻāĻŽ

āφāĻŽāϰāĻž āϕ⧇āύ āχāĻ¨ā§āϟāĻŋāϜāĻžāϰ āĻĢā§āϝāĻžāĻ•ā§āĻŸā§‹āϰāĻžāχāĻœā§‡āĻļāύ āĻ•āϰāĻŋ

āχāĻ¨ā§āĻŸā§‡āϜāĻžāϰ āĻĢā§āϝāĻžāĻ•ā§āĻŸā§‹āϰāĻžāχāĻœā§‡āĻļāύ āĻ…āĻ°ā§āĻĨ āĻšāĻšā§āϛ⧇ āĻāĻ•āϟāĻž āĻĒā§‚āĻ°ā§āĻŖāϏāĻ‚āĻ–ā§āϝāĻžāϕ⧇ āĻ‰ā§ŽāĻĒāĻžāĻĻāϕ⧇ āĻŦāĻŋāĻļā§āϞ⧇āώāĻŖ āĻ•āϰāĻžāĨ¤ āϝ⧇āĻŽāύ \(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.