Category Archives: Prime Numbers

You Can Help Search for Large Prime Numbers

Scientist have begun to realize that they can tackle big problems by harnessing the power of the internet to enlist “citizen scientists” to “crowdsource” their projects. The search for large prime numbers is one such project. Citizen mathematicians can become part of the search for prime numbers by joining the Great Internet Mersenne Prime Search (GIMPS). Mersenne primes (prime numbers of the form 2n-1) are extremely rare (only 48 are known).

All you need to participate is a computer, an internet connection, and patience. Simply download the GIMPS software from their website and start it running. The program runs in the background in the lowest priority, so it shouldn’t affect your computer performance. The patience is needed because you may need to run the program for weeks to complete a primality test. I downloaded the program last week and have been running it ever since, and I’m only up to 3%. It helps if you have a computer that is running most of the day. You can learn more about the math involved in the primality testing on the GIMPS math page.

And, if just knowing that you are helping advance the field of mathematics isn’t enough to entice you, there is also a $3,000 cash award to participants finding a prime having fewer than 100,000,000 digits and a $50,000 award to the first participant to find a prime with greater than 100,000,000 digits.

MarinMersenne

Mersenne primes are named for Marin Mersenne (1588– 1648), French theologian, philosopher, mathematician and music theorist.

Cicadas: Mathematicians of the Insect World

800px-Magicicada_species

Source: Wikimedia Commons (Author: Bruce Marlin)

Cicadas are coming to the East Coast this year. This year marks the end of the 17-year life-cycle for this particular population of cicadas. Periodical cicadas (Magicicada septendecim) spend most of their lives underground sucking fluids from roots, but emerge after 13 or 17 years (depending on the population) to mate and then die.

What does this have to do with math?

13 and 17 are both prime numbers, and therefore cannot be divided evenly by any other numbers (besides 1 and themselves). Researchers believe that prime number life-cycles help the periodical cicadas avoid predators and parasites. For example, a cicada with a 17-year cycle and a parasite with a two-year cycle would meet only twice in a century (year 34 and year 68). A 17-year cicada would only meet a 5-year parasite once in a century, year 85 (5 x 17). Also, the prime number cycles keep different populations from meeting and interbreeding. Since the life-cycle is determined by genes, interbreeding between 13-year and 17-year cicada populations would throw off their clockwork cycle.

How do the cicadas know when to emerge? They count, of course. Cicadas feed on the roots of trees that flower every year. Scientists at University of California-Davis were able to make some cicadas hatch a year early by transplanting them onto potted trees and forcing the trees to flower twice in one year.

Read more at:

Science News for Kids: Prime Time for Cicadas

The Baltimore Sun: Mathematicians explore cicada’s mysterious link with primes

 

Prime Patterns

There is no known formula for finding prime numbers. All numbers must be tested to determine whether they are prime or not. There are some interesting patterns that pop up in prime numbers, but you never know how long they will hold.

For example:

PrimePatterns1

PrimePatterns2

These types of numbers, where all the digits are the same number except one, are known as near repdigit primes.

Another pattern can be found when adding and subtracting factorials (!). The factorial of a number is the product of that number and all other positive integers less than that number. So for example, 4! = 4 x 3 x 2 x 1.

Alternating adding and subtracting factorials, as shown below, yields primes numbers until you get to 9!.

PrimePatterns3

If you want to see if a number is prime, or find out the factors of number that isn’t prime (those number are called composite), you can check numbers from 1 to 100,000,000 at cpnumbers.com.

Twin Primes

 In an earlier post, I explained what prime numbers are and how to find them using a sieve. In this post, I will tell you a little about twin primes.

Twin primes are pairs of prime numbers separated by a non-prime (composite) number. So, using  our sieve (shown below with prime numbers highlighted, and twin primes in red with darker yellow highlighting), we can see that the twin primes up to 100 are:

  • 3, 5
  • 5, 7
  • 11, 13
  • 17, 19
  • 29, 31
  • 41, 43
  • 59, 61
  • 71, 73

TwinPrimeSieve

The twin prime conjecture states that there are an infinite number of these pairs. This proposition is called a conjecture because it has not been proven. This video from Nova, says that the twin prime conjecture was proposed by Euclid, but it seems that some believe it was actually first proposed by Alphonse de Polignac.

Prime Numbers: What are they and how do you find them?

A prime number is a natural number (i.e., the counting numbers: 1, 2, 3, 4…), greater than 1, that has no divisors except 1 and itself. For example, 5 is prime because no numbers divide into it evenly except 1 and 5. The number 4 is not prime, because in addition to 1 and 4, it can be divided evenly by 2. Numbers that are not prime are called composite numbers.

The most basic method of checking whether or not a number is prime (a property called primality) is called trial division. Basically, this consists of dividing the number (we’ll call it n) by every integer (or whole number) that is greater than 1 and less than or equal to the square root of the number. If any of these divisions results in an integer, then n is not a prime. So, using a small number as an example, to test if 13 is a prime number, we would divide it by all integers from 1 to 3 (the square root of 13 is around 3.6). None of these divisions result in an integer, so 13 is prime.

Another method for finding all primes up to a given number, is called a prime number sieve. The oldest example is the sieve of Eratosthenes (shown in the animated gif below). This sieve is useful for relatively small primes. To make your own sieve of Eratosthenes up to 100, start with a number grid up to 100 (10 row, with 10 numbers in each row row).

  1. Cross out 1, since prime numbers must be greater than 1.
  2. The first prime number is 2.  Cross out all multiples of 2 (the even numbers).
  3. The next prime number is 3. Cross out all multiples of 3 (in other words, count by three’s: 3, 6, 9, 12…).
  4. The next prime is 5 (4 has already been crossed out). Cross out all multiples of 5.
  5. The next number remaining is 7 (the next prime). Cross out all remaining multiples of 7.
  6. All remaining numbers are prime numbers. (No other numbers have multiples below 100 that have not already been crossed out.)

You can download my worksheet with these instructions and a grid here.

Sieve_of_Eratosthenes_animation

You may have read something about prime numbers in the news recently. The largest known prime, was discovered by a mathematician at University of Central Missouri, Curtis Cooper. This newly discovered prime number is 17,425,170 digits long! Of course, finding primes this large require powerful computers and algorithms more advanced than the sieve above, but I’ll leave that for a future post.