Efficient Farming in Clash of Clans (TH6 to TH9 )

Hello everyone!

Today I am going to take a break from Maths, and instead write about good farming strategy in infamous mobile game Clash of Clans. Here I shall discuss strategy for th6 to th9. I started playing this addictive game around second week of January, 2016 due to persistence of one of my friends. And now it has become my favorite pastime.

Some key strategies are relevant for all town-hall levels. When you reach a new town-hall your first priority will be upgrading your army camps. So you should try to collect as much elixir as possible before the town-hall upgrade finishes. And never use gems for upgrading defenses or anything else. You will need those for buying builders.

Once you complete the army camp upgrades, your next priority will be upgrading the troops, barracks and clan-castle. The lab is the bottleneck of this game, so never keep it idle. Always try to collect enough elixir/dark elixir for the next research.

Try to complete wall-upgrade before town-hall upgrade. Lots of gold (or elixir for level 9 or higher walls) are required to upgrade walls.

To farm gold/elixir very quickly you should be in between silver II league and gold II league. Most of the dead bases are within this range, so you can collect lots of resources from the gold-mines and elixir-collectors.

My farming army consists of 4 types of troops - Giants, Wall-breakers, Archers and Goblins (GWAG combination) and healing spells (and also poison spell from TH9 to kill clan-castle troops). So I upgrade these troop first after each town-hall upgrade. I distract the defenses by deploying giants in front of the mines and collectors. The goblins can clear-off them very quickly. Beware of the mortars, as they do splash damage. Sometimes archers can take out the collectors staying out of range of any defenses. With some practice you can easily gain an idea about when to deploy giant-goblin or archers.

Starting from town-hall 8, you will need lots of dark elixir to upgrade your heroes and dark troops. The situation becomes even direr from town-hall 9. Most of the bases protect DE by keeping the storage at central position. Nevertheless you will find bases where it is placed close to the outer portion. Use wall breakers to make a path for the goblins. If you find a dead base which has higher town-hall level, then you can get lots of DE from the collectors (75% of the total capacity).

Training time for GWAG combination is very less. I am almost maxed-TH9. I can collect 60 lakh gold and 40 lakh elixir in one day. Both heroes can be upgraded to level 30 at TH9. It is very hard to keep ll the builders busy all the time. Try to keep one builder busy to upgrade the heroes all the time.

For defense, keep high level Wizard or Valkyrie in clan-castle. You can save some elixir/dark elixir by keeping army and spells in the queue. For saving elixirs, keep wall-breakers (highest elixir/space ratio) and highest level spell. For saving dark-elixir hogs/valkyrie and any dark spell.

Here are the bases and the exact army combinations I used for farming.

Town-hall 6

12 giants, 5 wall-breakers, 40 archers, 40 goblins, 2 healing spells, 5 level 5-7 wizards in clan-castle

Town-hall 7

17 giants, 6 wall-breakers, 51 archers, 52 goblins, 3 healing spells, 5 level 5-7 wizards in clan-castle

Town-hall 8

17 giants, 6 wall-breakers, 51 archers, 52 goblins, 3 healing spells, 1 poison spell, 6 level 5-7 wizards + 1 archer + 1 poison spell in clan-castle

Town-hall 9

18 giants, 6 wall-breakers, 58 archers, 60 goblins, 3 healing spells, 1 poison spell, 7 level 5-7 wizards + 2 archers + 1 poison spell in clan-castle

EDIT: Shortly after posting this I managed to get my biggest loot so far using GWAG combination.

Thanks for reading :)

Zeta Function at Negative Integers

In my previous post I mentioned that there is a connection between analytic expansion value of zeta function at negative integers and a geometrical method. It turns out that the proof is very simple. We know that $$\zeta(-n)=-\frac{B_{n+1}}{n+1}$$
where $B_n$ is the $n$th Bernoulli number. Bernoulli numbers are defined as
$$B_0=1$$
$$B_m=-\frac{1}{m+1}\sum_{k=0}^{m-1}{{m+1}\choose{k}}B_k \hspace{12 mm} m \geq 1$$
From Faulhaber's formula we know that,
$$S_k(n)=\sum_{i=1}^{n-1}i^k=\frac{1}{k+1}\sum_{j=0}^{k}{{k+1}\choose{j}}B_jn^{k+1-j}$$

Integrating $S_k(x)$ from $-1$ to $0$,
$$\int_{-1}^{0}S_k(x)dx=\frac{1}{k+1}\sum_{j=0}^{k}{{k+1}\choose{j}}B_j\int_{-1}^{0}x^{k+1-j}dx$$
$$=\frac{1}{k+1}\sum_{j=0}^{k}{{k+1}\choose{j}}\frac{B_j}{k+2-j}$$
$$=\frac{1}{(k+1)(k+2)}\sum_{j=0}^{k}{{k+2}\choose{j}}B_j$$
$$=-\frac{B_{k+1}}{k+1}=\zeta(-k)$$

So the small area enclosed by $S_k(x)$ around the $x$-axis is exactly equal to $\zeta(-k)$.

Derivation of the $\zeta(-n)$ can be found here. We need to know the value of zeta function for even positive integers to derive it. A nice proof for even positive integers is described here.

Thanks for reading :)

Finite or Infinite?

In one of the letters to G. H. Hardy, Srinivasa Ramanujan wrote that "I told him that the sum of an infinite number of terms of the series: 1 + 2 + 3 + 4 + · · · = −1/12 under my theory. If I tell you this you will at once point out to me the lunatic asylum as my goal.".

So according to Ramanujan's theory, we get the following formula, which is remarkable and seemingly impossible.
$$\sum_{n=1}^{\infty}n=1+2+3+\cdots=-\frac{1}{12}$$
When I first came to know about this formula, I was astounded. How can a divergent sum can possibly have a finite value, and also a negative one? Over past few years, I occasionally tried to understand the meaning behind this equation, with no success. Today I decided to give it a try again. I still can't fully grasp it, but I shall try my best to explain what little I understood so far.

The formula is completely incorrect if it is interpreted in traditional manner. In last post I discussed briefly about zeta function. It is defined as $$\zeta(s)=\sum_{n=1}^{\infty}\frac{1}{n^s}$$
Zeta function has finite values for $\text{Re}(s)>1$. For $\text{Re}(s)<=1$ zeta function becomes divergent. Zeta function is an analytical function, i.e. on a domain $D$ if it is complex differentiable at every point in $D$. In complex analysis there is a method known as 'Analytic Continuation' which extend the domain of an analytical function. I am not familiar with such method, so I shall use a method known as 'Cutoff regularization' which is little bit easier to comprehend.

A cutoff function $f$ is defined as $f:\textbf{R}^+ \to \textbf{R}$ which equals $1$ at $0$. We truncate our target sum at $N$. So we need to evaluate $\sum_{n=1}^{N}n$. After including the cutoff regularization, we get
$$\sum_{n=1}^{N}nf\left(\frac{n}{N}\right)$$
As cutoff function takes $1$ at $0$, so we get back our original sum when $N \to \infty$, i.e. we have to evaluate $$\sum_{n=1}^{\infty}nf\left(\frac{n}{N}\right)$$
By introducing a cutoff function, we replaced partial sums with smoothed sums. Using any cutoff function which follow above condition, we can show that the value obtained by analytic continuation is identical to the constant term of the smoothed sums. Some really heavy machinery is required to prove this and I got completely lost here. But we can easily verify it using an example.

Let $f(n/N)=e^{-n/N}$. $f(n/N)=1$ when $n \to 0$, i.e. $N \to \infty$. Now we shall try to evaluate the smoothed sum. Let $\frac{1}{N}=\theta$

$$\begin{array}{lcl}\sum_{n=1}^{\infty} ne^{-\theta n} & = & - \frac{d}{d\theta}\sum_{n=1}^{\infty} e^{-\theta n}\\
& = &  - \frac{d}{d\theta} \left( \frac{1}{1-e^{-\theta}} \right)\\
& = & \frac{e^{-\theta}}{(1-e^{-\theta})^2}\\
& = & \frac{1}{\theta^2}-\frac{1}{12}+\frac{\theta^2}{240} - \frac{\theta^4}{6048} + \frac{\theta^6}{172800}- \frac{\theta^8}{5322240} + O(\theta^9)\end{array}$$

So we got the fabled analytic expansion value $-\frac{1}{12}$ as the constant term of smoothed sum.
$$\zeta(-1)=-\frac{1}{12}$$
Using similar method to obtain the value of zeta function at other negative integers.

Analytic continuation values can be interpreted geometrically. Partial sum of first $N$ natural numbers is given by $\frac{N(N+1)}{2}$. Let $g(x)=\frac{x(x+1)}{2}$, which extends the discrete partial terms to continuous domain. I plotted the function for $x=-1.5$ to $x=1.5$.

$g(x)$ cuts x-axis at $x=-1$ and $x=0$. So the small area under x-axis is given by
$$\int_{-1}^{0} \frac{x(x+1)}{2} dx=-\frac{1}{12}$$
We got the analytic continuation value again !!

We can obtain the analytic continuation value for other negative integers in similar fashion. Due to the odd symmetry, for all negative even integers, zeta function takes the value $0$. In general
$$\zeta(-n)=-\frac{B_{n+1}}{n+1}$$ where $B_n$ is the Bernoulli numbers, which are defined as $$\frac{x}{e^x-1}=\sum_{n=0}^{\infty}\frac{B_nx^n}{n!}$$

In future, I shall try to discuss about it in detail if I manage to understand the underlying connection between analytic expansion and this geometrical method.

Thanks for reading :)

Zeta Function

Zeta function is defined as $$\zeta (s) = \sum_{n=1}^{\infty}\frac{1}{n^s}$$
Leonhard Euler proved that $$\sum_{n=1}^{\infty}\frac{1}{n^s} = \prod_{p}\left (1 - \frac{1}{p^s} \right )^{-1} \hspace{8 mm} s > 1$$
where $p$ takes only prime numbers.

This equality gives an alternative proof of infiniteness of primes. When $s \to \infty$, left-hand side goes to infinity. If there are finite number of primes, then right-hand side finite product will be equal to an infinite sum, which is a contradiction.

The proof of the above identity is not very difficult. Consider separate infinite series for each prime $p$.
$$\left (1 - \frac{1}{p^s} \right )^{-1}=\sum_{e=0}^{1}\frac{1}{p^{es}}$$
Product of infinite series of all primes will contain terms of form $$\frac{1}{(p_1^{e_1}p_2^{e_2} \cdots p_m^{e_m})^s}$$
Each number have unique prime factorization, so rearranging the terms of product of infinite series of all primes we get the infinite sum on the left-hand side of the identity.

Exact values of zeta functions and some related sums for positive integral value of $s$ is considered in this post.

Let me start with evaluating $\zeta (2)$. Consider the function $f(x)=x^2$, $x \in (-\pi, \pi)$ and $f(x+2\pi)=f(x)$

Taking the Fourier series expansion of $f(x)$,
$$x^2=\frac{\pi ^2}{3}+\sum_{n=1}^{\infty}\frac{4\cos n\pi}{n^2}\cos nx$$
Substituting $x=\pi$, we get $\zeta (2)=\frac{\pi ^2}{6}$. We can obtain other interesting sums for different values of $x$.

Euler proved that $\zeta (2n)$ is rational multiple of $\pi ^{2n}$, where $n$ is positive integer. It is not known if $\zeta (2n+1)$ is irrational for all $n$.

We can obtain some interesting sums for odd positive integers. Integrating the Fourier series expansion of $f(x)$ defined above from $0$ to $x$,

$$\frac{x^3}{3}=\frac{\pi ^2 x}{3}+\sum_{n=1}^{\infty}\frac{4 \cos n\pi}{n^3} \sin nx$$

Substituting $x=\frac{\pi}{2}$ we get, $$\sum_{n=0}^{\infty}\left [ \frac{1}{(4n+1)^3}- \frac{1}{(4n+3)^3}\right ] = \frac{\pi ^3}{32}$$

Proceeding similarly we can derive such sums for larger odd positive integers.

$$\sum_{n=0}^{\infty}\left [ \frac{1}{(4n+1)^5}- \frac{1}{(4n+3)^5}\right ] = \frac{5\pi ^5}{1536}$$

$$\sum_{n=0}^{\infty}\left [ \frac{1}{(4n+1)^7}- \frac{1}{(4n+3)^7}\right ] = \frac{61\pi ^7}{184320}$$

It seems that we can generalize this sum for all odd positive integers. Apparently, for even positive integral value of $n$, this sum is not rational multiple of $\pi ^n$, exactly opposite holds for zeta function at positive integral value of $n$.

$$\sum_{n=0}^{\infty}\left [ \frac{1}{(4n+1)^{2k+1}}- \frac{1}{(4n+3)^{2k+1}}\right ] = \frac{E(k)\pi ^{2k+1}}{(2k)!2^{2k+2}}$$

where

$$E(0)=1$$

$$E(n)=(-1)^{n+1}\sum_{i=0}^{n-1}(-1)^iE(i)\binom{2n}{2i}$$

$E(n)$ is related to A000364

This formula is based on observation. I don't have any proof yet. But I am quite certain about its correctness. I verified for $n=3,5,7,11,13,15$ using Mathematica.

I found another interesting result, again without proof.

$$\operatorname{\mathbb{R}e} \left ( \sum_{n=0}^{\infty} \left [ \frac{1}{(an+1)^3} - \frac{1}{(an+a-1)^3} \right ] \right )= \left(\frac{\pi}{a}\right)^3\text{cos}\left(\frac{\pi}{a}\right)\text{cosec}^3\left(\frac{\pi}{a}\right)$$

for any positive real number $a>1$. It might be possible to extend it for other odd positive integers.

$\textbf{EDIT}:$ It is possible to get closed form formula of above sum for other odd positive integers. $$\operatorname{\mathbb{R}e} \left ( \sum_{n=0}^{\infty} \left [ \frac{1}{(an+1)^{2k+1}} - \frac{1}{(an+a-1)^{2k+1}} \right ] \right )= \frac{2}{(2k)!}\left(\frac{\pi}{a}\right)^{2k+1}\text{cosec}^{2k+1}\left(\frac{\pi}{a}\right)\sum_{i=1}^{k}b(k,i)\text{cos}\frac{(2i-1)\pi}{a}$$
where $b(k,i)=T(2k-1,2k-i-1)$

$T$ is known as Euler's Number Triangle and defined as
$$T(0,0)=1$$ $$T(i,j)=(i-j)T(i-1,j-1)+(j+1)T(i-1,j) \hspace{4 mm} i \ge 1, 0 \le j < i$$
First few terms are given below
\[\begin{array}{ccccccccccc}
  &    &    &    &    &    &  1 &    &    &    &    &    &   \cr
  &    &    &    &    &  1 &    &  1 &    &    &    &    &   \cr
  &    &    &    &  1 &    &  4 &    &  1 &    &    &    &   \cr
  &    &    &  1 &    &  11 &    &  11 &    &  1 &    &    &   \cr
  &    &  1 &    &  26 &    &  66 &    &  26 &    &  1 &    &   \cr
  &  1 &    &  57 &    & 302 &    & 302 &    &  57 &    & 1    & \cr
1 &    &  120 &    & 1191 &    & 2416 &    &  1191 &    & 120 &    & 1 \cr
\end{array}\]

I shall conclude this post by mentioning the most famous conjecture associated with zeta function, the Riemann hypothesis. It states that "Zeta function has its zeros only at the negative even integers and complex numbers with real part $\frac{1}{2}$". Riemann derived an explicit formula of prime counting function $\pi(x)$, which is related to the zeros of zeta function. Interested reader can read about this in detail here.

Thanks for reading :)

Primes - crowning jewel of Mathematics

In this post, I shall explore some of the aspects of prime numbers. For centuries, prime numbers have drawn attention to mathematicians, professionals and amateurs alike. Most stubborn attempts to find the complete picture of prime numbers proved fruitless.

A positive integer $p$ is a prime, if it has only two divisors, $1$ and $p$ itself. There is a very simple, but elegant proof of infiniteness of prime numbers, thanks to Euclid(which dates back to 4th century BCE). The proof is based on contradiction. If we assume that prime numbers are finite and last one of them is $q$, and define a number $n$ which leaves a remainder of $1$ when divided by all the primes $\le q$. Formally $n=2 \cdot 3 \cdot 5 \cdots q+1$. As $n$ is not divisible by any prime $\le q$, either $n$ itself is a prime, or there exists a prime $>q$ which divides $n$. Both contradicts our initial assumption about prime numbers being finite. Over time, many algorithms have been formulated to count primes, some of them are very complex and require deeper understanding of number theory. So I shall not discuss about them in this post.

Prime numbers of special form have been studied in great details. Most famous of these special primes are Mersenne primes and Fermat primes.

Mersenne primes are named after Father Marin Mersenne, a French priest. Mersenne numbers are defined as $M_n=2^n-1 \hspace{1 mm}, n\geq 1$. It is not yet known whether the set of Mersenne primes are finite or infinite.

Famous mathematician Pierre de Fermat believed that numbers of form $2^{2^n}+1$ are primes, based on first $5$ values ($0\le n \le 4$). But no other Fermat primes are not known for $n>4$.

A lot of conjectures are there concerning primes. Most notable of them are Goldbach conjecture and twin prime conjecture. First one states that every even integer greater than $2$ can be expressed as the sum of two primes.

A couple of prime numbers have even been associated with superstitions. Most famous of them is the number $13$, considered as unlucky. Fear of number $13$ even has a special name, Triskaidekaphobia (it was mentioned in my favorite TV series Friends - S08E20 :) ). Other superstitious prime is the Belphegor's prime - $1000000000000066600000000000001$. It has exactly $31$ digits, inverse of $13$. It contains $666$, 'the number of the beast' at the center and have $13$ zeros on either sides. And it is also a palindromic prime.

Primes also have practical applications. Randomness of prime numbers and difficulty of factorizing lie at the heart of several public encryption schemes, which are used to secure communication systems.

Primes will most probably befuddle us for many more years to come. Where is the fun if the everything is predictable? :) As English novelist Mark Haddon said, "Prime numbers is what is left when you have taken all the patterns away."

Thanks for reading :)