| Home | Sign up! | Projects | Seminars | Research Notes | Today's Lecture | About |
Member ID: 47

Karan Sahni

Email
k6346589@rediffmail

Profile: I am a Junior Year student of Computer Information Systems at Ansal Institute of Technology, affiliated to Coastal Carolina University.

Prof. Ashay Dharwadker's Courses (3):

CourseSemesterGrade
Algorithm Design - IFall 2002View
Probability & StatisticsSpring 2003View
Algorithm Design - IISpring 2004View



Projects (1)


Project ID: 45
Course: Algorithm Design - II
Topic: Sorting Algorithms Visualization
Description: My Part of the project was to create working C++ Sorting programs from the various Algorithms. We had decided to make the project comprehensive. So, we included all the sorting algorithms we knew:
  1. Bubble Sort
  2. Insertion Sort
  3. Selection Sort
  4. Merge Sort
  5. Quick Sort
  6. Batcher's Odd-Even Merge Sort
  7. Shell Sort
  8. Heap Sort
  9. Radix Sort
  10. Bucket Sort

Team Manifesto

The first (and probably the most important) thing that any computer programmer learns are the various algorithms for SORTING data. They are absolutely critical for a complete understanding of the whole computer science field itself. But it can get quite confusing at times. Especially, when one wants to understand how each one of them works? Or, How each one of them is different from the other?

We think we have an answer to that. Suppose you wish to introduce somebody to the game of FOOTBALL. A verbal discription would not be very helpful. The best solution would be to show a visual of the football game to that person.

Same is the case with Sorting Methods. Through this project, we give a visual discription of the various Sorting Algorithms, with the aim of making learning easy and fun.

But the solution also gives rise to a more complex problem. How do we represent the sorting algorithms visually. The solution is to create unique visualization schemes to represent the status of data elements at various instances of time.

This method of representation gives rise to a more complex field in mathematics known as Dynamical Systems.

After the main idea of the project was concieved, the elements of the project were distributed to the various team members.

Team Members:

  • Karan Sahni (Algorithms - Coding Sorting Algorithms into C++ Programs)
  • Parul Yadav (Visualizations - Creating Visualization Schemes in OpenGL)
  • Devina Sibal (Visualizations - Creating Visualization Schemes in OpenGL)
  • Prakash (Win32 Integration - Integrating all components in Visual C++ Environment)


Seminars (1)


Seminar ID: 53
Course: Algorithm Design II
Topic: Mersenne Primes
Description: Many early writers felt that the numbers of the form 2^n-1 were prime for all primes n, but in 1536 Hudalricus Regius showed that 2^11-1 = 2047 was not prime (it is 23.89). By 1603 Pietro Cataldi had correctly verified that 2^17-1 and 2^19-1 were both prime, but then incorrectly stated 2^n-1 was also prime for 23, 29, 31 and 37. In 1640 Fermat showed Cataldi was wrong about 23 and 37; then Euler in 1738 showed Cataldi was also wrong about 29. Sometime later Euler showed Cataldi's assertion about 31 was correct.

Enter French monk Marin Mersenne (1588-1648). Mersenne stated in the preface to his Cogitata Physica-Mathematica (1644) that the numbers 2^n-1 were prime for n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257 and were composite for all other positive integers n < 257. Mersenne's (incorrect) conjecture fared only slightly better than Regius', but still got his name attached to these numbers.

Definition: When 2^n-1 is prime (where n is also a prime) it is said to be a Mersenne prime.

It was obvious to Mersenne's peers that he could not have tested all of these numbers (in fact he admitted as much), but they could not test them either. It was not until over 100 years later, in 1750, that Euler verified the next number on Mersenne's and Regius' lists, 2^31-1, was prime. After another century, in 1876, Lucas verified 2^127-1 was also prime. Seven years later Pervouchine showed 2^61-1 was prime, so Mersenne had missed this one. In the early 1900's Powers showed that Mersenne had also missed the primes 2^89-1 and 2^107-1. Finally, by 1947 Mersenne's range, n < 258, had been completely checked and it was determined that the correct list is:

n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 and 127.

Are there infinitely many Mersenne primes? Equivalently we could ask: Are there infinitely many even perfect numbers? The answer is probably yes (because the harmonic series diverges).

Another question that I am personally confused with is the fact that actually in the form 2^p-1, p has to be prime or just be an odd number?


Research Notes (1)


Research Note ID: 64
Course: Algorithm Design - II
Topic: Mersenne Primes
Description: Many early writers felt that the numbers of the form 2^n-1 were prime for all primes n, but in 1536 Hudalricus Regius showed that 2^11-1 = 2047 was not prime (it is 23.89). By 1603 Pietro Cataldi had correctly verified that 2^17-1 and 2^19-1 were both prime, but then incorrectly stated 2^n-1 was also prime for 23, 29, 31 and 37. In 1640 Fermat showed Cataldi was wrong about 23 and 37; then Euler in 1738 showed Cataldi was also wrong about 29. Sometime later Euler showed Cataldi's assertion about 31 was correct. Enter French monk Marin Mersenne (1588-1648). Mersenne stated in the preface to his Cogitata Physica-Mathematica (1644) that the numbers 2^n-1 were prime for

n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257

and were composite for all other positive integers n < 257. Mersenne's (incorrect) conjecture fared only slightly better than Regius', but still got his name attached to these numbers.

Definition: When 2^n-1 is prime it is said to be a Mersenne prime.

It was obvious to Mersenne's peers that he could not have tested all of these numbers (in fact he admitted as much), but they could not test them either. It was not until over 100 years later, in 1750, that Euler verified the next number on Mersenne's and Regius' lists, 2^31-1, was prime. After another century, in 1876, Lucas verified 2^127-1 was also prime. Seven years later Pervouchine showed 2^61-1 was prime, so Mersenne had missed this one. In the early 1900's Powers showed that Mersenne had also missed the primes 2^89-1 and 2^107-1. Finally, by 1947 Mersenne's range, n < 258, had been completely checked and it was determined that the correct list is:

n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 and 127.

See the table of known Mersenne primes below.

Perfect Numbers and a Few Theorems: Many ancient cultures were concerned with the relationship of a number with the sum of its divisors, often giving mystic interpretations. Here we are concerned only with one such relationship:

Definition: A positive integer n is called a perfect number if it is equal to the sum of all of its positive divisors, excluding n itself.

For example, 6 is the first perfect number because 6=1+2+3. The next is 28=1+2+4+7+14. The next two are 496 and 8128. These four were all known before the time of Christ. Look at these numbers in the following partially factored form: 2.3, 4.7, 16.31, 64.127. Notice they all have the same form 2^(n-1)(2^n-1) (for n = 2, 3, 5, and 7 respectively)? And that in each case 2^n-1 was a Mersenne prime? In fact it is easy to show the following theorems:

Theorem One: k is an even perfect number if and only if it has the form 2^(n-1)(2^n-1) and 2^n-1 is prime. [Proof.]

Theorem Two: If 2^n-1 is prime, then so is n.

So the search for Mersennes is also the search for even perfect numbers! You may have also noticed that the perfect numbers listed above (6, 28, 496, 8128) all end with either the digit 6 or the digit 8--this is also very easy to prove (but no, they do not continue to alternate 6, 8, 6, 8,...). If you like that digit pattern, look at the first four perfect numbers in binary:


110
11100
111110000
1111111000000

(The binary digit pattern is a consequence of Theorem One.) It is not known whether or not there is an odd perfect number, but if there is one it is big! This is probably the oldest unsolved problem in all of mathematics. When checking to see if a Mersenne number is prime, we usually first look for any small divisors. The following theorem of Euler and Fermat is very useful in this regard.

The Lucas-Lehmer Test: Mersenne primes (and therefore even perfect numbers) are found using the following theorem: Lucas-Lehmer Test: For p odd, the Mersenne number 2^p-1 is prime if and only if 2^p-1 divides S(p-1) where S(n+1) = S(n)2-2, and S(1) = 4. In pseudocode this test is:
Lucas_Lehmer_Test(p):
s := 4;
for i from 3 to p do s := s^2-2 mod (2p-1);
if s == 0 then
2^p-1 is prime
else
2^p-1 is composite;

The theory for this test was initiated by Lucas in the late 1870's and then made into this simple test about 1930 by Lehmer. The sequence S(n) is computed modulo 2^p-1 to save time. This test is ideal for binary computers because the division by 2^p-1 (in binary) can be done using rotation and addition only.

Conjectures and Unsolved Problems

Is there an odd perfect number? We know that all even perfect numbers are a Mersenne prime times a power of two (theorem one above), but what about odd perfect numbers? If there is one, then it is a perfect square times an odd power of a single prime; it is divisible by at least eight primes and has at least 37 prime factors (not necessarily distinct); it has at least 300 decimal digits and it has a prime divisor greater that 1020.For more information see or

Are there infinitely many Mersenne primes? Equivalently we could ask: Are there infinitely many even perfect numbers? The answer is probably yes (because the harmonic series diverges).

Another question that I am personally confused with is the fact that actually in the form 2^p-1, p has to be prime or just be an odd number?

Last updated on Monday, 26th April 2004, 04:32:02 PM.

Prof. Ashay Dharwadker