Wednesday, 28 December 2016

Checking whether a number is prime or not...


First of all, this must be clear that 1 is neither prime nor composite. To answer why, I found this great answer on Quora which you must read : This answer.

Let n be a number which we want to find whether it is prime or not. Then we do not need to check if it divides any of the number between 2 and ( n - 1). We also do not need to check if it divides any of the number between 2 and n / 2. We only need to check if divides any of the number between 2 and square root of n.


As we can see in the below given graph that sqrt(x) is much less then x / 2. The meeting point of these graph is x = 4 which is very small number and we do not need to be concerned about it.


Plot of the graphs of sqrt(x) and x/2

But the problem is that, as we can see in the below mentioned function IsPrime loop runs sqrt(n) times and we try to conclude that time complexity of the program is O(sqrt(n)) which is not true. The time complexity to check whether a number is prime or not is actually exponential. This is called pseudo-polynomial time. In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is polynomial in the numeric value of the input, but is exponential in the length of the input – the number of bits required to represent it.

These kind of algorithm are called weakly NP - Complete. When the algorithm takes exponential time but a pseudo-polynomial time algorithm exists then it called weakly NP - Complete.

/*See this C code before further reading*/
int IsPrime(int n) {
int i, number = (int)sqrt(n);
for (i = 2; i <= number; i++)
if (n % i == 0)
return 0;
return 1;
}
If you go on Stack Overflow to find the fastest way to check whether a number is prime or not then we will find many answers which claims that they are pretty fast or one-liners but the problem is that many of them are not even giving correct answers. Also some programs are not as fast as they claim it to be. For many general purpose use, my function above gives correct and fast answers.


Also, there is Sieve of Atkin which gives all the primes below a certain number. The pseudo code, explanation and code to Sieve of Atkin can be easily found on the internet. For reference, read Wikipedia and Stack Overflow.

Saturday, 24 December 2016

Josephus Problem, my exploration

Intro is taken from Wikipedia. In computer science and mathematics, the Josephus problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game.

People are standing in a circle waiting to be executed. Counting begins at a specified point in the circle and proceeds around the circle in a specified direction. After a specified number of people are skipped, the next person is executed. The procedure is repeated with the remaining people, starting with the next person, going in the same direction and skipping the same number of people, until only one person remains, and is freed.

The problem — given the number of people, starting point, direction, and number to be skipped — is to choose the position in the initial circle to avoid execution.
(Following picture is taken from a Numberphile video on YouTube)




Here, counting will in done in clockwise manner. n will be the number of people in the circle waiting to be executed. k will decide which person should die such that (k - 1) people will be skipped and kth person will be killed. For example, if k =  2 then 1st person will skip himself and will kill the 2nd person, then 3rd person will skip himself and kill the 4th person and so on.

For k = 1, everybody will kill himself and nth person will be the answer since that position will be the one on which last execution is possible.
For any k > 1, algorithm is very easy to write using queues, linked lists, arrays and dynamic  programming, but we will be looking at the mathematics side of the problem for k = 2.

Suppose, initially there are 2n persons in the circle. We start clockwise with first person killing 2nd person(taking k = 2 and first person could be anybody but once chosen should not change). After the first round, all the even numbered people will be killed and n people with odd numbering will remain(namely 1, 3, 5, ..., 2n - 1). We can rename these people 1, 2, 3, ..., n. After the renaming, we will find the answer to this new problem with n person. Let the answer to this new problem is yth person(y is any natural number less than or equal to n). So the answer to our original problem with 2n persons will be (2*y - 1)th person.

Therefore, using recursion we can write, M( 2*n ) = 2*M( n ) - 1. Here, M( n ) is the answer to above problem with k = 2 and n persons. M( 1 ) = 1.

Similarly, for 2*n + 1 persons, we can find, M( 2*n + 1 ) = 2 * M( n ) + 1. Again, M( 1 ) = 1.

Before I state my foolish conclusion, I must state that there is another solution to this problem with order of one time complexity.

Just moving the last 1-bit in n's binary form to the first position will give us the answer. For example,

n = 41 = 32 + 8 + 1 = 0b(101001)
answer = 0b(010011) = 19
OR
n = 19 = 16 + 2 + 1 = 0b(10011)
answer = 0b(00111) = 0b(111) = 7
OR
n = 7 = 4 + 2 + 1 = 0b(111)
answer = 0b(111) = 7

But how are we getting the answer just by shifting 1 bit of the the problem's input. Wikipedia has the answer but I am also stating my result here.

If we apply the above two recursion equations to solve this problem, we will get something like this :
M( n ) = 2^k + (2^p1 + 2^p2 + ...) - (2^q1 + 2^q2 + ...) ± 1. The last one is added is n is odd and subtracted if n is even. This plus-minus thing for 1 need not be specified. I just wanted to show that I invested a lot of time in this problem !

Observe carefully :
M(14) = 2 * M(7) - 1
          = 2 * (2 * M(3) + 1) - 1
          = 4 * (2 * M(1) + 1) + 2 - 1
          = 8 + 4 + 2 - 1
and 14 = 8 + 4 + 2.
Again observe carefully :
M(41) = 2 * M(20) + 1
          = 2 * (2 * M(10) - 1) + 1
          = 4 * (2 * M(5) - 1) - 2 + 1
          = 8 * (2 * M(2) + 1) - 4 - 2 + 1
          = 16 * (2 * M(1) - 1) + 8 - 4 - 2 + 1
          = 32 - 16 + 8 - 4 - 2 + 1
and 41 = 32 + 8 + 1.
What do we observe here? State the given n in its sum of power of two like 19 = 16 + 2 + 1. Then the answer will contain these power of two and negative of sum of power of two which are not in n less then the highest power already present in n(If you get this, don't worry, I explained it again down under). M(19) = 16 - 8 - 4 + 2 + 1 = 7. Tada!

If n = 2 ^ 5 + 2 ^ 3 + 2 ^ 2 then it do not have 2 ^ 4, 2 ^ 1 and 2 ^ 0. So M( n ) = 2 ^ 5 + 2 ^ 3 + 2 ^ 2 - 2 ^ 4 - 2 ^ 1 - 2 ^ 0. This is what happens if we take the last 1-bit in a binary number and put it as the first bit of the same number.

I know everything was boring in this blog but I am not getting time to write something more useful. Sorry!

Tuesday, 20 December 2016

Exploring Tower of Hanoi - 3

Intro from my last blog : This is more of an article than a blog but it is my exploration. On solving for different n's , I found that the bottom disk always moves only once. Similarly, second disk from the bottom moves 2 times. Third from the bottom always moves 4 times. And so on, they form the series => 1, 2, 4, 8, ... , 2^(n - 1) . The sum of these is of course equal to 2^n - 1 which was already mentioned above.





It been a while since we have been looking at the old Tower of Hanoi problem with same constraints. What if we have more than 3 towers ? This time we are exploring the Tower of Hanoi when the number of disks, n > 0 and number of towers, p > 2. 

Many of the mathematicians have tried at this problem and if we google their research we will get to some non - trivial and rigorous mathematics. Just google it, and find them yourself.

I don't want to go into mathematics because firstly I don't get it and secondly it is not proven yet that fits all possible combinations of n and p to find the minimum moves. I have written a C code which use dynamic programming to find and print minimum moves for any given n and p such that n > 0 and p > 2. What it does is, it splits the very first pile of disks at some k which is varying from 1 to n. After each split, the problem is divided into two sub problem of k disks and n - k disks.

What happens next will blow your mind !!! This k disks and p - 1 towers problem is solved first and recorded in a 2 - D matrix of moves which stores moves for x disks and y towers. Then n - k disks and p towers problem is solved afterwards. Both of them are only stored in the matrix if they are smaller then the previous problem. This is why, initially matrix was filled with infinity.

The result for k disks and p - 1 towers and n - k disks and p towers is added and also stored in the same matrix if it less then the previously stored value. This will be enough for finding the minimum number of moves for n disks and p towers.

To print the actual moves along with the number of moves, we will need another matrix which will store the best split for x disks and y towers. Number of moves will be printed in the same way as the the number of moves were calculated.

Both of the matrix will be filled at the same time and the printing of the moves will be done separately after both of the matrix are filled. Whole of this can be done with only the best split array but then the time complexity will be higher. It is an example of time-memory compensation. This size of the array needed will be n x (p - 3).


I know that nobody would like to read somebody else's code but for the completeness of this blog I think that I should give the code as well. Though this problem may look easy to some of you but it was a great challenge for me. I wrote this code just after I learnt dynamic programming. At that time, I knew very less things related to programming. Here I present the C implementation for this problem : Github Gist

Friday, 16 December 2016

Exploring Tower of Hanoi - 2

Intro from my last blog : This is more of an article than a blog but it is my exploration. On solving for different n's , I found that the bottom disk always moves only once. Similarly, second disk from the bottom moves 2 times. Third from the bottom always moves 4 times. And so on, they form the series => 1, 2, 4, 8, ... , 2^(n - 1) . The sum of these is of course equal to 2^n - 1 which was already mentioned above.





Suppose that our movement about the towers is restricted. We have three towers named A, B and C. Our n disks of different sizes are on tower A and we need to transfer disks to tower C via B. But we can only send disks from A to B, from B to C and from C to A. All other movement is restricted. What will be the minimum moves for this problem ?

In the original Tower of Hanoi problem, moving disk from any tower to any other tower will have the same number of minimum moves. But in this problem, moving disk from A to C and from A to B will have different number of minimum moves.

Let us assume that we need M( n ) moves for moving n disks from A to C.
Recursive steps to calculate M( n ) (moving disk from A to C) are : 
Step 1 : Move (n - 1) disks from tower from A to C recursively. Moves required are M(n - 1).
Step 2 : Move nth disk from A to B. Only one move is required.
Step 3 : Move all of (n - 1) from C to A recursively. Lets assume that moves required are N(n - 1).
Step 4 : Move nth disk from B to C. Only one move is required.
Step 5 : Move all of (n - 1) disks from A to C recursively. Moves required are M(n - 1).
Step 6 : ???
Step 7 : Profit. (Task complete !!!)
Total moves required, M( n ) = 2 * M(n - 1) + N(n - 1) + 2

Now we need to calculate N(n - 1). But before that, what is the difference between N( n ) and M( n ). M( n ) is the number of moves to move n disks from A to C. N( n ) is the number of moves to move n disks from A to B.
Recursive steps to calculate N( n ) (moving disk from A to B) are : 
Step 1 : Move (n - 1) disks from tower from A to C recursively. Moves required are M(n - 1).
Step 2 : Move nth disk from A to B. Only one move is required.
Step 3 : Move all of (n - 1) from C to B recursively. Moves required are M(n - 1).
Step 4 : ???
Step 5 : Profit. (Task complete !!!)
Moves required, N( n ) = 2 * M(n - 1) + 1

Therefore, total moves required to move n disk from A to C, M( n ) = 2 * M(n - 1) + 2 * M(n - 2) + 3.

I know that nobody would like to read somebody else's code but for the completeness of this blog I think that I should give the code as well. Here is the code in C to implement this : Github Gist

Tuesday, 13 December 2016

Exploring Tower of Hanoi - 1

This is more of an article than a blog but it is my exploration. On solving for different n's , I found that the bottom disk always moves only once. Similarly, second disk from the bottom moves 2 times. Third from the bottom always moves 4 times. And so on, they form the series => 1, 2, 4, 8, ... , 2^(n - 1) . The sum of these is of course equal to 2^n - 1 which was already mentioned above.







Now, we are given n disks and the bottom two disks are of same size then what will be the number of moves. The answer is simple from the above result. The bottom disk will move only once. Second disk from bottom has the same size that of bottom disk and it will also move only once. Third disk will move 2 times. Fourth disk will move 4 times. And they will for series like this => 1, 1, 2, 4, ... , 2^(n - 2). The sum of this series will be 2^(n - 1) + 1. So the minimum moves to transfer n disks from one tower to another given 3 tower, n disks such that bottom two disks have same size will be 2^(n - 1) + 1.

Similarly, if we are give n disks with top two disks same, minimum moves = 2^(n - 1) + 1 + 2^(n - 2). Also we can also find for any kth disk to same and more than one disk to be same.

I know that nobody would like to read somebody else's code but for the completeness of this blog I think that I should give the code as well. Here is a C implementation of very generalised form of Tower of Hanoi problem with as many disks of same size as the user wants : Github Gist