# Happy 3.1415926 (π) day : 3-14

### Happy 3.1415926 Day !

In every year, π day is celebrated on March 14th (3.14).

π is a super star in mathematics. It is mysterious and people keep exploring it. It is proven that this constant has no end hence it is irrational, that means it cannot be represented as a fraction. π is bigger, as big as the whole universe. In deed π is not the only irrational number we got. But π attracted many and we keep loving it.

Even though there is no known benefit of calculating the value of π people insist of doing it. For many engineering applications, having value of π for 3 or 4 decimal places would be sufficient. Other sophisticated scientific advanced might need much more accuracy but I am pretty sure, it is enough to know first 100 digits of π. But today, humans have calculated 22,459,157,718,361 digits[1] of π.

There are quite many activities are organized for the π day worldwide other than enjoying delicious pies. One of the interested things is ,contests on memorizing decimal places of π. The current world record is 70030 digits[2].

To celebrate the π day I have calculated π for 7 decimal places using Gregory and Leibniz series. It is one of the most primitive ways of calculating π though.

### Happy 3.1415926 Day !

PS: Following script gives 7 decimal digits of π.

ans = 0
for k in range (1,100000000):
temp = ((-1)**(k+1)/(2*k-1))
ans = ans + (temp*4)
print (ans)


# Social Media restriction in Sri Lanka

Currently in Sri Lanka, there is a restriction against leading social media applications such as Facebook, WhatsApp, Viber, Instagram etc. That does not mean the use of such services are illegal with in the country. There is no law to support it. This is not a ban, but just a restriction temporary imposed by the ISPs based on a request made by the government to control the tens situation arose within the country in last week.

Even though the direct access is restricted, it is possible to access these services through Proxy Servers and VPN (Virtual Private Network) applications. There are some false information, being circulated that the use of either social media services or VPN applications are illegal. There is no ground for such misleading information.

No action can be taken against anyone as long as the services are used in the right manner. Use indirect methods to access these services and use them but do not get involved in spreading racism.

At this moment, it is reported that access of some VPN services are also restricted. But there are plenty of VPN services out there which can be used for the purpose.

Do raise your voice against this restriction !!

Do use social media services responsibly !!

# Euler’s Totient Function – Counting Primes

Euler came up with this function more than 200 years back. At that time this function drew less attention, indeed it had no much value as there is no direct application other than in number theory. However, today this function plays a major role in cyber security applications.

Euler’s Totient Function, also known as Phi Function, Prime Counting Function or $\displaystyle \varphi(n)$ is used to count number of co-primes prior to a given integer. In other words, the function outputs number of co-primes which are less than the given number.

Co-primes are integers which does not share any common factors. For an example even though 8 is not a prime, it is a co-prime of 15. Because 8 = 2*2*2 and 15 = 2*5, therefore it can be seen that 8 or 15 does not share a common factor.

If a given integer is a prime, obviously all the integers less than the given number are co-primes to the given prime. Therefore, it is easy to calculate $\displaystyle \varphi(n)$ if n is a prime. When n is a prime; in $\varphi(n) = \displaystyle (n - 1)$

When n is not a prime, $\displaystyle \varphi(n)$ can be calculated as follow:

First, the number should be broken into prime factors, then after it is a matter of applying the following equation:

$n = \displaystyle p_1 * p_2 * ....... p_m$ (prime factors of n)

$\varphi(n) = \displaystyle n \prod_{i=1}^{m} ( 1 - \frac{1}{p_i} )$

### Multiplicative Property

This is another interesting property of $\displaystyle \varphi(n)$ which can be used to compute $\displaystyle \varphi(n)$.

When, p and q are prime numbers:

$\varphi(n) = \displaystyle \varphi(p) * \varphi(q)$

as a fact, if p and q are prime numbers then, $\varphi(p) = \displaystyle (p - 1) * (q - 1)$

### Example

Calculating $\displaystyle \varphi(24)$ :

$24 = \displaystyle 2^3 * 3$

Using the above equation:

$\varphi(n) = \displaystyle n \prod_{i=1}^{m} ( 1 - \frac{1}{p_i} )$

n = 24, m = 2 and primes are 2, 3:

$\varphi(24) = \displaystyle 24 * ( 1 - \frac{1}{2} ) * ( 1 - \frac{1}{3} )$

$\varphi(24) = \displaystyle 24 * ( \frac{1}{2} ) * ( \frac{2}{3} )$

$\varphi(24) = \displaystyle 24 * ( \frac{1}{3} )$

$\varphi(24) = \displaystyle 8$

Will check if the answer is correct, using the besic definition:

Following are all the integers less than 24, starting from 1

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23

Remove co-prime of 24:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23

Remaining number count is 8, therefore both answers match.

### Python Implementation

It is possible to use the above equation to calculate $\varphi(n) \displaystyle$ in Python. However, it is easier to use the definition of prime counting rather than using the equation.

The algorithm would be as follow:

1. $\varphi(n) \displaystyle$ needs to be calculated.
2. Start from k = 2, counter is 0.
3. Check if the selected integer (k) is a co-prime to n.
4. If it is a co-prime increase the counter.

To check if k is a co-prime to n, GCD operation can be used.

def calculate_phi(n):
phi_n = 1
count = 0
i = 2
while (i<n):
r = gcd_euc(n, i)
i = i + 1
if(r==1):
phi_n = phi_n + 1
return phi_n


### Summary

Above mentioned methods can be used to calculate $\displaystyle \varphi(n)$ of a given integer.  Results of the phi function is often applied in cryptography.

# Square and Multiply algorithm

Square and Multiply algorithm is an interesting algorithm which is also known as binary exponentiation algorithm as well. The algorithm is very useful against calculation of large integer powers of a number.

For an example, like calculating; $\displaystyle 3^4$ (which is multiplying 3, four times), this is pretty straight forward:

$3 * 3 = \displaystyle 3^2$
$3^2 * 3 = \displaystyle 3^3$
$3^3 * 3 = \displaystyle 3^4$

In order to get the answer 3 rounds of calculations are required.

In that same manner, to calculate $\displaystyle 5^{13}$, 12 rounds of multiplication rounds are required. Nevertheless it is possible to use the following method and reduce number of required rounds.

$5^1 * 5^0 =\displaystyle 5^1$
$5^1 * 5^1 = \displaystyle 5^2$
$5^2 * 5^2 = \displaystyle 5^4$
$5^4 * 5^4 = \displaystyle 5^8$
$5^8 * 5^4 = \displaystyle 5^{12}$
$5^{12} * 5^1 = \displaystyle 5^{13}$

Above is a short cut method to obtain the answer, however things might go weird when the exponent is really large, for example something like $\displaystyle 3^{105}$ or $\displaystyle 2^{846}$.

Even using the shortcut method seems quite cumbersome but better than the first method.

However, in such situations Square and Multiply method comes handy. Even in the second method, we have applied Square and Multiply operation to get the answer. Using this algorithm make it easier to apply the logic behind, especially when it needs to be implemented as a computer program.

Taking back the earlier example, check the operations carried out:

$5^1 * 5^0 =\displaystyle 5^1$
(Square) $5^1 * 5^1 = \displaystyle 5^2$
(Square) $5^2 * 5^2 = \displaystyle 5^4$
(Square) $5^4 * 5^4 = \displaystyle 5^8$
(Multiply) $5^8 * 5^4 = \displaystyle 5^{12}$
(Multiply) $5^{12} * 5^1 = \displaystyle 5^{13}$

what if the above is arranged as follow:

$5^1 * 5^0 =\displaystyle 5^1$
(Square) $5^1 * 5^1 = \displaystyle 5^2$
(Multiply) $5^2 * 5^1 = \displaystyle 5^3$
(Square) $5^3 * 5^3 = \displaystyle 5^6$
(Square) $5^6 * 5^6 = \displaystyle 5^{12}$
(Multiply) $5^{12} * 5^1 = \displaystyle 5^{13}$

Even though that there is no much improvement in computational rounds, the second approach aligns with the Square and Multiple method. So as you might already have understood, the Square and Multiple method determines the combination of operations that needs to be carried out to reach to the final answer.

### Algorithm

Following steps needs to be carried out :

1. Get the binary representation of the exponent.
2. Bits are read from left to right (MSB first) and it should start with a 1.
3. Starting value$\displaystyle n^0$
4. Start scanning bits from the left.
5. As mentioned above the first bit must be 1.
6. If scanned bit is 1 then, square the value and then multiply by $\displaystyle n$
7. If scanneed bit is 0 then, square the value.
8. Repeat this for all the bits.

As an example, $\displaystyle 5^{13}$ can be taken. Binary representation of 13 is: $13_{ten} = \displaystyle 1101_{two}$

Since the first bit is 1, initially the value is squared and multiplied. Then next bit is taken, it is 1, therefore the value is square and multiplied again.  Then the third bit is 0, therefore the value is only squared. Final bit is 1, the value needs to be squared and multiplied. Pretty easy right !

Time to check this method for a larger exponent. Lets take following : $\displaystyle 3^{105}$

$\displaystyle 105_{ten} = 1101001_{two}$

Steps:
(Square  ) $3^0 * 3^0 =\displaystyle 3^0$
(Multiply) $3^0 * 3^1 =\displaystyle 3^1$
(Square ) $3^1 * 3^1 =\displaystyle 3^2$
(Multiply) $3^2 * 3^1 =\displaystyle 3^3$
(Square ) $3^3 * 3^3 =\displaystyle 3^6$
(Square ) $3^6 * 3^6 =\displaystyle 3^{12}$
(Multiply) $3^{12} * 3^1 =\displaystyle 3^{13}$
(Square ) $3^{13} * 3^{13} =\displaystyle 3^{26}$
(Square ) $3^{26} * 3^{26} =\displaystyle 3^{52}$
(Square ) $3^{52} * 3^{52} =\displaystyle 3^{104}$
(Multiply) $3^{104} * 3^1 =\displaystyle 3^{105}$

### Python Implementation

Following is the python code:

string bin(int num)

The above function takes an integer as the argument and then return the binary equivalent as a string. It starts with 0b prefix. Therefore it is required to consider [2:] of the string. As the first bit is always 1, the final output of the first step is always equal to x. That is the reason for starting the for loop from 3.

def exp_func(x, y):
exp = bin(y)
value = x

for i in range(3, len(exp)):
value = value * value
if(exp[i:i+1]=='1'):
value = value*x
return value


### Summary

Square and Multiply algorithm is a very useful algorithm which can be used to calculate values of integers having really large exponents. The number of calculation rounds is relatively less compared to the brute force method.

# Deduce remainder of large numbers [Manual Method]

Often articles are published on Python algorithms in this blog. But today’s article is all about calculating the remainder of two numbers by hand, manually.

When two numbers are divided, it produces two things. One is termed as the Quotient and the other is termed as the Remainder. Based on the application, more focus could be given either to the Quotient or to the Remainder. Today, will focus on the Remainder and find how to deduce the Remainder when a large number is divide by a comparatively small number without doing extensive calculations.

According to the Euclidean division, this can be written as follow:

let x – numerator, y – denominator, k – quotient and r – remainder

$x = \displaystyle k*y + r$

Using the above equation, will try to find the remainder of 27 / 12.

$27 = \displaystyle k*12 + r$

It is possible to try applying k = 1 ; k = 2 and then calculate r, at k = 2 we get the answer which is r = 3 . This algorithm is promising, however when the numerator (x) is relatively a large number, more computation is required.

For an example, try to find the remainder of $\displaystyle (25^{243}/12)$

Assuming this calculation is done by hand, as the numerator is a large number it is not possible to compute the remainder using the above algorithm, of course it is possible but it might take lot of computational steps and time. Therefore another approach is required.

To understand easily, will consider following generalize form; $\displaystyle (x^{p}/y)$

### Algorithm

1. Break the numerator (x) into two numbers where y needs to be a factor of one of the numbers. Let numbers are a and b, then a = k * y and x = a + b
2. When there are some combinations available for a and b try to obtain the minimum value for b which satisfies the requirement mentioned in step 1. Obtaining b = 1 is the ideal, if possible.
3. Once above steps are concluded, the equation reduces to $\displaystyle ((a+b)^{p}/y)$, further it can be deduce to $\displaystyle ((k*y + b)^{p}/y)$
4. Once it is reduced, the remainder can be easily obtained by solving $\displaystyle ((b)^{p}/y)$
5. In a scenario where b = 1, then the answer is 1 as $\displaystyle ((1)^{p}/y)$ is always 1.

Getting back to the example mentioned above, $\displaystyle (25^{243}/12)$

1. 25 can be broken into 1 and 24, a = 24 and b = 1, 12 become a factor of a therefore the combination satisfies the requirement.
2. Then solve $\displaystyle (1^{243}/12)$, which is equal to 1.

Results can be verified with the following python code as well:

<pre>print('Remainder - ',(25**243)%12)</pre>


In such scenarios, where b is not possible to take as 1, it is required to solve the equation numerically. But even though the numerator is reduced, still it requires more computational effort.

### Algorithm – part 2

When b is not equal to 1, following method can be used. It follows patterns recognition and then deduce the answer.

To understand the concept behind, will take a slightly different version of the above example, assume that it is required to calculate the remainder of $\displaystyle (26^{243}/12)$

At this time, as the numerator is 26, it is not possible to break into two numbers in which b = 1. When a = 12, b = 2. Therefore following algorithm needs to be used to deduce the remainder from the reduced equation.

The reduced equation for $\displaystyle (29^{243}/12)$ is $\displaystyle (2^{243}/12)$

Then take the reduced equation as $\displaystyle (2^{p}/12)$ where p = 243

The next part is identify the pattern by applying p = 1, p = 2, p = 3 ……… This needs to be done until a pattern can be recognized.

at p = 1 $\displaystyle (2/12)$ remainder is 2
at p = 2 $\displaystyle (4/12)$ remainder is 4
at p = 3 $\displaystyle (8/12)$ remainder is 8
at p = 4 $\displaystyle (16/12)$ remainder is 4
at p = 5 $\displaystyle (32/12)$ remainder is 8
at p = 6 $\displaystyle (64/12)$ remainder is 4

A pattern, now can be recognized. It seems when p is odd remainder is 8 and when p is even the remainder is 4 for all p when p>1. As we are looking for the remainder when p = 243 which is an odd number, as a result the remainder should be 8.

Verify the answer with the following python script.

print('Remainder - ',(26**243)%12)


Recognizing the pattern is quite cumbersome but it is always easier than working out the whole equation.

Finally, below is the mathematical proof for the above algorithm:

### Mathematical Proof

Let $\displaystyle (x^{p}/y)$ : where y ≠ 0 and x and y are positive real integers.

In Euclidean division, x = k * y + r ———————(1)

applying (1) , $\displaystyle ((k*y+r)^{p}/y)$

Term (k*y+r), can be treated as binomial expansion as a = k*y and b = r

$(a+b)^{p} = \displaystyle c_{1}*a^{p} + c_{2}*a^{p-1}*b + c_{3}*a^{p-2}*b^{2}..... + c_{p-2}*a^{2}*b^{p-2} + c_{p-1}*a*b^{p-1} + b^{p}$ ———–(2)

In equation no. 2, it can be noticed that each term has a factor of a except the last term, which is $\displaystyle b^{p}$, that means each term is divisible with no reminder except the last term. Therefore that is the only term which generates a remainder. Calculating the remainder for the last term gives the remainder of the whole equation, that is why it is possible to reduce the original equation to:

$\displaystyle ((b)^{p}/y)$

### Summary

When calculating prime numbers, it is often required to check if a given number has factors. One of the efficient ways is to divide given numbers and check if there is a remainder. For such operations this algorithm can be used specially when the numerator and the denominator are relatively large (in exponent format). Furthermore, if it is possible to break numbers into a and b (step 1 in Algorithm) such a way that b = 1, at a glance the remainder can be obtained. Therefore this is a faster technique that can be mastered to calculate the remainder manually and also can be implemented in computer aided calculations as well.

# Greatest Common Divisor (GDC)

The Greatest Common Divisor (GCD) or Greatest Common Factor is the largest integer which is a common factor of  two or more integers. In other terms, GCD is the largest positive integer that divides each given integer.

For an example, GCD of 20 and 12 is 4. GCD of 18 and 12 is 6. Further, since primes dont have factors (other than 1 and the prime itself) the GCD of any two prime numbers is 1. There is no common factors for 20 and 11, therefore GCD for 20 and 11 is also 1. GCD is not limited to 2 integers, it can be for more than two. For an example, GCD of 30,60 and 90 is 30.

In order to calculate GCD of two numbers following algorithms can be used:

## General Method

function cal_gcd(x, y)
Input: Let x and y are two integers

d = min(x,y)
while (True)
if(x mod d is zero) and (y mod d is zero)
return d
else
d = d - 1


Above algorithm can be used to calculate GCD of two numbers. With a slight modification, the code snippet can be changed so that it calculate GCD for more than two integers.

function cal_gcd_(list)
Input: list of integers
d = min (list)
while (True)
if remainder = 0 for all integers in the list when divided by d
d = d -1
else
return d

These two algorithms perform better, however once the integers are quite large, these algorithms are not efficient. For large integers, Euclid’s algorithm can be used. Python implementation of the above method mentioned below.

Python Code:

def gcd_gen_list(list_num):
d = min(list_num)
cal = True
while(cal):
counter = len(list_num)
for i in range(0, len(list_num)):
if (list_num[i] % d != 0) :
d -= 1
break
else:
counter -= 1
if((d==1) or (counter == 0)):
return d


## Euclid’s algorithm

This is a pretty interesting method. This method is based on the divisibility concept.

Let, x is divided by y, so that the result is k and remainder is r. In such a case it can be expressed as;

x = k . y + r

Plus this method uses the following theorem.

GCD of integer x and y is equal to GCD of integer y and r.

Repeating this concept till remainder reaches zero.

Pseudocode algorithm:

function gcd_euc
Input: Let x and y are integers

calculate r (r = x mod y)
while (r is not 0)
calculate r (r = y mod r)
return r


This method is pretty straight forward and very fast when compared to the method mentioned above for large integers.

Python code:

def gcd_euc(x, y):
r = x%y
while (r != 0):
x = y
y = r
r = x%y
return int(y)


## Dijkstras Algorithm

This is another algorithm which can be used to compute GCD of two integers. It uses subtraction of numbers to calculate the GCD.

Pseudocode algorithm:

function gcd_dijk
Input: Let x and y are integers

while (x != y)
If x > y Then
x = x - y
Else:
y = y - x
return x


Python code:

def gcd_dijk(x, y):
while(x!=y):
if(x>y):
x = x-y
else:
y = y-x
return x


## Binary method

The Binary method also known as Stein’s algorithm is also one of the algorithms to compute GCD. It is quite more complex than Dijkstras Algorithm. However unlike
Dijkstras Algorithm it uses division by 2, therefore it is possible to use bit operations.

Pseudocode algorithm:

function gcd_binary
Input: Let x and y are integers

while (x != y)
factor = 1

If x is 0 Then
return factor * y
If y is 0 Then
return factor * x

If x is even AND y is even Then
factor = factor * 2
x = x / 2
y = y / 2

If x is even AND y is not even Then
x = x / 2

If x is not even and y is even Then
y = y / 2

If x is not even AND y is not even Then
If x > y Then
x = (x - y ) /2
Else
y = (y - x) / 2

return factor * x


Python code:

Python implementation is provided below. Note that bit-wise operator >> and << have been used instead of multiplication of 2 or division by 2.

def gcd_binary(x, y):

factor = 1
while(x!=y):

if (x==0 or y==0):
return factor*(x+y)

if (is_even(x) == False and is_even(y) == False):
if(x>y):
x = (x-y) >> 1
continue
else:
y = (y-x) >> 1
continue

if(is_even(x) and is_even(y)):
x = x >> 1
y = y >> 1
factor = factor << 1 continue if(is_even(x)==True and is_even(y)==False): x = x >> 1
continue
else:
y = y >> 1
continue

return factor * x

def is_even(x):
y = x >>1
if(y<<1==x):
return True
else:
return False


All methods other than the General Method can be used to calculate GCD for 2 integers at once. In order to calculate GCD for more than two integers, it is possible to calculate GCD for pairs and then select the lowest GCD for all the pairs.

Python code:

def gcd_list(numList):
numListSize = len(numList)
GCDList = list()
for i in range(0, numListSize):
for j in range(0, numListSize):
if(i!=j):
ans = gcd_binary(numList[i], numList[j])
GCDList.append(ans)
return min(GCDList)


All methods can be found in bmaths library under bmaths_gcd.py
bmaths library is released under GNU General Public License v3.0

# Local Authority Election 2018 – Parsing Results (Python Script)

The official results of the Local Authority Election 2018 just released via https://election.news.lk/ . If any one is looking for a script to parse the results, check the below link.

https://github.com/bckurera/elec_res_parse

The direct connection socket to the site has been removed. Therefore follow below steps unless you want to add your own socket to read the site (check my earlier post on Python Socket programming):

1. Open the relevant result page and save it in your local PC.
2. Rename the file name to 98.html (or change the file name in the script)
3. Execute the script.