Author Archives: Sarah Devore

Sarah and Sequences and Series

When we were doing the lab on iteration, there was a proof that we encountered that had heavy use of some of the theorems involving infinite series. While there was a chapter on this in my Calculus II class, I think it would be interesting to explore more about series in the context of a more proof-based class. I think this will also be a nice addendum to the first lab on iteration, because we are going to be looking in much more detail into the question of general convergence and divergence. It doesn’t look like we’re going to be doing a lot of strict proving in this lab, but instead we are gong to given the opportunity to explore series in more detail and really be able to explore some of the facets that may have been glossed over in a busy Calculus class. We will be exploring convergence, divergence, the harmonic series, the natural logarithm and Euler’s constant. I’ve never encountered Euler’s constant outside of some proofs that I saw in other labs.

Congruent mod 4 primes

One of the last sections in our primes lab had to do with an interesting distribution of primes that are congruent to 1 and 3 mod 4. This means that our prime number, n, is congruent to either 1 (mod 4) or 3 (mod 4). We can divide these up into two sets of primes numbers:

$\pi_1(n)$= #{primes p| p $\leq$ n and p = 1 + 4k, for some positive integer k}

$\pi_3(n)$= #{primes p| p $\leq$ n and p = 3 + 4k, for some positive integer k}

So the question is, how many primes actually fit into these two sets?

 

n

$\pi(n)$

$\pi_1(n)$

$\pi_3(n)$

$\pi_1(n)$/$\pi(n)$

$\pi_3(n)$/$\pi(n)$

10

5

1

1

.2

.2

25

9

3

4

.33

.44

50

15

6

7

.4

.47

100

26

11

12

.42

.46

1000

168

80

86

.48

.51

10000

1229

609

618

.5

.5

100000

9592

4783

4807

.5

.5

As we can see, as our n approaches infinity, the two sets comprise together roughly 100% of the primes. There are some primes missing, as evidenced with n is small. 2 is a good example of one that doesn’t work with this relationship. But, as we can see, when n gets really large, the relationship holds really well.

Through this, we can make an extension of our very first proof, where we found that there are an infinite number of primes.

Let’s prove: If $\pi(n) \geq \pi_1(n) + \pi_3(n)$, then as n approaches infinity, $\pi_1$ and $\pi_3$ are infinite sets.

We already know that $\pi(n)$ is an infinite set, so our question is whether $\pi_1(n)$ and/or $\pi_3(n)$ are also infinite. As n approached infinity, $pi_1(n) \approx 0.5\pi(n)$, and $pi_3(n) \approx 0.5\pi(n)$. So, we can plug in our values: $\pi(n) \geq 0.5\pi(n) + 0.5\pi(n)$, and since $\pi(n)$ is an infinite sets, it is the sum of two infinite sets. So, as n approaches infinity, $\pi_1$ and $\pi_3$ also approach infinity, so they are also infinite sets. This is what we wanted to prove in the first place, so we are done.

The Sieve of Eratosthenes

Because there was a question in our first post about what a sieve is, it would be good to give a quick example of what a sieve is supposed to do, and what it looks like.

For the sake of an example, we are going to sieve all of the primes from 2-30, in other words we are going to separate the primes from the non-prime numbers in the set.

 

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

 

Let’s strikethrough all of the multiples of 2 greater than 2.

 

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

 

Now, let’s strikethrough all of the multiples of 3 greater than 3.

 

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

 

Now, you may be saying to me, but why didn’t you make 6, 12, 18…green too? Well, they’ve already been highlighted once in blue, so there’s no real reason to do more work than I have to.

 

So, let’s continue with 5.

 

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

 

I’m going to continue going up using the non-crossed out numbers as a guide, and highlighting the multiples of those non-highlighted numbers.

 

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

 

Because I only chose to go up to 30, we are actually done. The non-crossed out numbers are our prime numbers:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29

 

So, here are some closing thoughts about the sieve “method” of finding primes:

Pro: Easy algorithm, an easy way to loop through a set of numbers to find the primes, easy to program by hand

Con: Can take a long time with larger numbers, eats memory in larger number sets.

 

And just for a thing to brighten your day, here is a poem that I found about the sieve on Wikipedia. I take no credit because it’s not mine, but I thought it was a fun way to think about the sieve method. More information can be found at the wikipedia page on the topic, including a very cool animation of the sieve from 2-120.

 

Sift the Two’s, and Sift the Three’s,

The Sieve of Eratosthenes.

When the multiples sublime,

The numbers that remain are prime.

 

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Previous Post: Prime-Generating Functions

Prime Number Lab: Post 1

Prime numbers are important to study because they are largely the basis for what we consider to be modern number theory. Understanding prime numbers and their distribution can help us solve problems in fields such as cryptology. Prime numbers have also been looked at since mathematics as we understand it came into being. So, by studying prime numbers, we are studying a vast history of research and theorems that mathematicians have discovered over the years.

We relate this motivation to process with an introduction into the process of finding primes, and move onto proving why we can find these primes by proving that the list of primes is infinite.
Our first observation begins with the Sieve method, which is the most basic method to find primes, but also the most computationally expensive as the numbers we work with get larger.
Euclid’s proof shows that the Sieve method can be used infinitely to find any number of primes we desire.

Euclid’s Proof of Infinite Primes:
Theorem: There are an infinite number of primes.

For the sake of argument, let’s let there be a finite number of primes, so n primes exist.

Let’s let M be an integer greater than 1. Like all integers greater than 1, it is either prime, or composite. Let’s let M be composite, so M is the product of primes. So, let M be the product of all the primes in our list. This means that M=p1*p2*p3*…*pn. What do we know about M+1? Well, it’s an integer greater than 1, so it’s either prime or composite. Let’s let M be prime. Then, either M+1 is a prime not on our list. Uh oh :(.

Now, let’s let M+1 be composite. This means that p|(M+1), where p is a prime from our list. But, that same p would also divide M. This is a contradiction because consecutive numbers are co-prime. This means that they cannot share a divisor greater than 1. So there must be a prime not on our list which divides M+1. So, there is at least one more prime that is not included in our list, so our list cannot be complete. Thus, the set of all primes is an infinite set, and there are an infinite number of primes.

To Next Post: Expanded Motivations and Definitions