Prime Numbers!

Prime Numbers:

Prime Numbers are those natural numbers divisible only by 1 and themselves.These are building blocks of natural number arithmetic.

Some interesting things about prime numbers.

1)Any Natural number can be expressed uniquely as product of powers of distinct primes.This procedure of finding the powers of primes contained in a number is called Prime Factorization.

2)There are infinitely many prime numbers.

3)If a number N is not prime, then it should have a factor less than sqrt(N).Hence the procedure to test whether a number is prime or not is of complexity O(sqrt(N)).

Prime Twin Pairs


One of the first things noticeable about tables of primes is that there are many instances of pairs of prime numbers with the form n and n + 2.

Examples are 11 and 13, 17 and 19, 29 and 31, 101 and 103, 881 and 883, and so on.

These are sometimes called prime twin pairs. No one has ever determined if this is an interesting property of numbers or just a curious coincidence.
The instances of pairs of prime numbers decrease for ever larger numbers.

Palindromic Primes

One of the more curious prime number puzzles that mathematicians have examined is the occurrence of palindromic primes.

A palindrome is a word or phrase that reads the same forward or backward. Some examples of palindromic primes are 101, 131, 151, 181, 313, 353, 727, 757, 787, 79997, 91019, 1818181, 7878787, 7272727, and 3535353. There is an infinite number of palindromic primes.


Sieve of Eratosthenes

The Sieve of Eratosthenes is an algorithm for generating a list of all prime numbers up to a given integer N. It does this using O(N) space .

We begin by making a table of integers 2 to N.We find the smallest integer i, that is not crossed out,print i and cross out i, 2i , 3i, .........When i >sqrt(N) the algorithm terminates and further numbers which aren't crossed out printed.

Q1)Suggest ways to improve it further.

Solution:The improvement in terms of space requirements that can be done is accomodating only odd numbers as 2 is the only even prime.
considering time complexity, we can limit the strike off to multiples of prime P greater than P*P ,hence reducing the number of numbers traversed.



What is the complexity of this algorithm?

Solution:Nlog(N)

Q2)In the above mentioned facts about primes ,the second one claims that there are infinite number of primes.Prove it

Solution:Let there be finite number of primes say K.let the primes be P1,P2,....,Pk.
now consider the number N=P1*P2*P3*P4....*Pk + 1.
clearly none of the above k primes divide N.Hence N is also a prime contradicting our initial assumption.

Q3)Show that (N^4 + 4N) is a prime number if and only if N=1. (really simple)

Solution:let f(N)=N^4 + 4N.
f(1)=5 which is prime.
for N greater than 2 we can write f(N)=N(N^3+4) as product of 2 numbers both of which are greater than 1.Hence it is composite.
Hence proved.


Relative Primes

When gcd(m, n) = 1, the integers m and n have no prime factors in
common and we say that they’re relatively prime.

Euler's Phi Function

Euler's Phi function, also known as the totient function, is a function that, for a given positive integer N, calculates the number of positive integers smaller than or equal to N that are relative prime to N. (Note that except when N = 1, only integers strictly smaller than N are counted.

Mathematical Definition

\phi(N) = \Big|\, \{ i ~~|~~ 1\leq i\leq N ~\land~ \gcd(i,N)=1 \} \Big|
where | | indicates the cardinality of the set.

Features of Euler's Phi Function

1) φ(p) = p - 1 for p prime, because all numbers smaller than p are relatively prime to p.

2) φ(N) is even for all N > 2, because if k is relatively prime to N, so is N - k, and they are distinct.

3) It is a multiplicative function in the number-theoretic sense: φ(MN) = φ(M)φ(N) whenever gcd(M,N) = 1.

4)\phi(p^k) = p^k-p^{k-1} = p^{k-1}(p-1) = p^k\left(1-\frac{1}{p}\right), because among the integers from 1 to pk, the integers not relatively prime to pk are precisely those divisible by p, and there are pk - 1 of them.

5)Let N = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_r^{\alpha_r} be the prime factorisation of N. That is, the pis are distinct primes and each αi is a positive integer. Then \phi(N) = (p_1^{\alpha_1}-p_1^{\alpha_1-1})\cdots(p_r^{\alpha_r}-p_r^{\alpha_r-1}) = N \left( 1 - \frac{1}{p_1} \right)\left( 1 - \frac{1}{p_2} \right) \cdots\left( 1 - \frac{1}{p_r} \right)

If you have perhaps gone through the above facts,you can try solving the below mentioned
programming problems which test the basics

http://acm.uva.es/p/v101/10168.html

http://acm.uva.es/p/v106/10699.html

http://acm.uva.es/p/v107/10789.html

http://acm.uva.es/p/v108/10852.html

http://acm.uva.es/p/v108/10871.html

http://acm.uva.es/p/v109/10924.html

http://acm.uva.es/p/v1/160.html

http://acm.uva.es/p/v2/294.html

http://acm.uva.es/p/v4/406.html

http://acm.uva.es/p/v5/516.html

http://acm.uva.es/p/v5/543.html

http://acm.uva.es/p/v5/583.html

Remember that the solutions to these problems should be efficient in terms of time and space complexities.


post your valuable comments so that we can learn better through discussion.

Solutions to all the above problems shall be posted soon!!

Interesting Aspects of Factorization

Factorization:
It is the procedure of expressing an integer as a product of 2 or more numbers.If we express it as the product of powers of distinct primes ,it is called prime factorization.Now we shall look at some interesting aspects of this factorization.

Number of factors or divisors of a given number:

Given a number N,one might have a number of ways of expressing it as the product of 2 numbers A,B. i.e N=A*B.
So How many in number are the divisors of a number?

The answer to it lies in simple prime factorization!!

Let the prime factorization of N yields N=2^a1 * 3^a2 * 5^a3 *......Pk^ak
where Pk is the biggest prime factor of N and ak is its power.

Now it shouldn't take one much time to understand that any factor of N can be obtained by depriving one or more of the above primes,a share of their exponents.

ie any factor M of N is =2^b1 * 3^b2 *...................* Pk^bk
where b1 <= a1 , b2 <= a2 ,...........,bk <= ak.

Hence if N=P1^a1 * P2^a2 * .........*Pk^ak then
the no of divisors of N=(a1+1)*(a2+1)*.......*(ak+1).



Sum of divisors of a number

Now getting along with the above explanation , we can also calculate the sum of all the divisors of a number.

N=P1^a1 * P2^a2 * .........*Pk^ak

Now let F(N)=(1+P1 + P1^2 + ...+P1^ak)*(1+P2+P2^2+...+P2^a2)* ......... *(1+Pk+Pk^2+...+Pk^ak).

Expanding this as a polynomial ,we get (a1+1)*(a2+1)...*(ak+1) terms!!
which is nothing but the no of factors we deduced above.And each of the terms is themselves a factor.Hence the sum of divisors of N is given F(N).

F(N)=(1+P1 + P1^2 + ...+P1^ak)*(1+P2+P2^2+...+P2^a2)* ......... (1+Pk+Pk^2+...+Pk^ak)

Now we shall see another interesting aspect of this factorization.

Is the number of divisors of a number N even or odd?

Please ponder over this question for a little while... before seeing the answer.
Because you might regret missing out such a little,yet interesting feature which one could have seen as early as in 6th standard.

Folks!! you don't actually need primes to answer this question.

Any number N can be expressed as N=A*B where A <=sqrt(N) and B >=sqrt(N).
Now start with A=1 and B=N and start increasing A and decreasing B with A*B=N as the constraint.Now one can clearly see that both A and B approach sqrt(N) in this procedure.

In each iteration as we had A < B we can say that the no of factors are even .

But a peculiar thing yet not rare , can happen.
A=B=sqrt(N).Then we have only 1 factor as A=B.
This can arise only if N is a perfect square!!

Hence driving the point home, we conclude that no of divisors is odd if N is a perfect square, even otherwise.
So one needn't enumerate all the prime factors of a number!!



Some interesting questions

1.All the positive numbers can be expressed as a sum of one, two or more consecutive positive integers. For example 9 can be expressed in three such ways, 2+3+4, 4+5 or 9. Given an integer ,you will have to determine in how many ways that number can be expressed as summation of consecutive numbers.

Click here for solution


2.Computing the exact number of ways that N things can be taken M at a time can be a great challenge when N and/or M become very large.So given 5<=N<=100 5<=M<=100 and M<=N.Compute the EXACT value of: N!/(M!*(N-M)!)
The final value of C will fit in a 32-bit Pascal LongInt or a C long.
So deduce an approach based on this assumption given.

Click here for Solution

Factorial - Number of 0's in 100!

A common interview question asked these days is how many zero's does 100! contain?
`
Many of us do say it is 24 ,but how many of us care to know the smart way of doing it?

And what is the same for 1000! ?

We will now look into this smart method of finding the no of zeroes in N! where N is any natural number.

One hundred factorial (100!) is a huge number of 158 digits.We add a zero to the tail of a number whenever we multiply by 10, which is 2 x 5. There are lots of twos as factors of 100!, but not as many fives, so the number of zeros will be the same as the number of fives. The factors 5, 10, 15, 20, ... each contribute a five, and 25, 50, 75, and 100 each add an extra. So the total is (100 / 5) + (100 / 25) = 24.

So the best way to calculate the number of zeroes at the end of N! is finding the number of 5's in the prime factorization of N!.

Now coming to this task of figuring out the number of 5's,

In general ,if P is any prime,then the no of P's in N! is given by
Sum (floor(n/p^i)) for p^i <= n

This apparently weird formula can be explained with ease!!

consider the numbers 1,2,3,.........,,N.Every pth number is divisible by p.So all those multiples of p put together contribute floor(N/p) to the power of p.

Similarly every p^2th number is divisible by p^2.And each of them have already contributed 1 to power of p in previous iteration,as each of them are divisible by p.So each of them contribute an additional 1, which means they all together contribute floor(N/p^2) to the already sum.

These terms of contribution go on till we have p^i <= N,hence the summation
Sum (floor(n/p^i)) for p^i <= n

Now, the statement no of 5's in 100! =floor(100/5)+floor(100/25) is easily understood.

Now coming to the task of calculating no of 0's in 1000!.
It is given by S= floor(1000/5) + floor(1000/25) + floor(1000/125) + floor(1000/625)=249.

Well having made this task simple,we shall look at questions based on this.

Questions

1) write a program that can compute the last non-zero digit of any factorial for ( 0 <= N <= 10000). For example, if your program is asked to compute the last nonzero digit of 5!, your program should produce 2 because 5! = 120, and 2 is the last nonzero digit of 120.
Click Here For Solution


2)If you have already solved the above problem, then give a generalized method to find the last x non-zero digits of N factorial
Click Here For Solution