Friday, April 15, 2011

More explorations of primes

So I decided to add a little more to detail to the statistics generation for my c++ implementation of the Sieve of Eratosthenes. I added code to tally the occurrences of twin primes, prime triplets, and prime quadruplets.

Twin primes are defined as the set p, p+2 . Prime triplets are defined as either the set p, p+2, p+6 or p, p+4, p+6. Prime quadruplets are defined as the set p, p+2, p+6, p+8.

I also modified the implementation to use the bit being cleared as being a prime and a bit being set a composite. This allowed me to remove the O(n) code that initialized the bit array to a set state.

Here are the results of a run for 1 billion:

snits@jsni-linux:~/proj/cxx=>time ./tps2 1000000000
50847534 primes between 2 and 1000000000, 3424506 twin primes,
759256 prime triplets, and 28388 prime quadruplets.
The greatest prime is 999999937

real    2m27.192s
user    2m27.041s
sys     0m0.117s

Thursday, April 14, 2011

Primes and the Sieve of Eratosthenes

My nephew was working on finding how many primes are below a certain upper bound, so I was playing with this some today as well. Initially, since he was working in perl I threw together a quick perl program that built a list of primes below a certain upper bound. I also wrote a routine to determine the prime factorization of a number. The perl program would get bogged down after a while though between the algorithm implementation and just the speed of perl.

To speed things up I moved to c++ and implemented the same algorithm, and played around with using vectors to store the list of primes. That sped it up some, but it would still eventually get bogged down by the algorithm.

So finally I decided to implement the Sieve of Eratosthenes using a bit array. Now that got things going quickly. It is a fast algorithm that is pretty much bound by the amount of memory you have. On my home system it did the following for an upper bound of 1 billion:

snits@perelman:~/proj/cpp=>time ./se 1000000000
50847534 primes between 2 and 1000000000. Greatest prime is 999999937

real 1m58.563s
user 1m58.352s
sys 0m0.101s

I bumped the upper bound up to 40 billion, which would take a fair chunk of my RAM for the bit array, and it had the following results:

snits@perelman:~/proj/cpp=>time ./se 40000000000
1711955433 primes between 2 and 40000000000. Greatest prime is 39999999979

real 90m48.631s
user 90m40.850s
sys 0m3.589s

Wednesday, April 13, 2011

A Mathematician's Lament

A Mathematician's Lament: How School Cheats Us Out of Our Most Fascinating and Imaginative Art FormA Mathematician's Lament: How School Cheats Us Out of Our Most Fascinating and Imaginative Art Form by Paul Lockhart

My rating: 4 of 5 stars

A rather passionate argument about what is wrong with math education in our society. The book is based on an earlier article written by the author. The 1st part of the book is a repeat of the article, "A Mathematician's Lament", while the 2nd part is the author trying to show what is wonderful and beautiful about mathematical discovery through the use of some simple examples.

View all my reviews

Books read this year: 10

Wednesday, April 6, 2011

Euclid's Window

Euclid's Window : The Story of Geometry from Parallel Lines to HyperspaceEuclid's Window : The Story of Geometry from Parallel Lines to Hyperspace by Leonard Mlodinow

My rating: 4 of 5 stars

Interesting discussion of history of geometry from the time of the ancient Greeks through geometry's role today in String Theory and M-Theory. It covers what it considers to be the major events of the history of geometry, starting with Euclid's organizing Greek knowledge of geometry into the Elements, Descartes bringing the coordinate system to geometry, Gauss and Riemann moving geometry beyond Euclidean space, Einstein with his theory of relativity, and finally Ed Witten and his contributions to String and M-Theory. I felt like the book might have been a little rushed at the end, but that is probably because String theory and M-theory are both still young and in the process of being developed.

View all my reviews

Books read this year: 9

Saturday, April 2, 2011

Graham's Number

Someone asked a question on the Physics Forums asking for an explanation of the largeness of this number, so doing some research this is what I came up with:

It is a number that is impossible to comprehend. Going by the articles on wikipedia covering Graham's number, Knuth's up-arrow notation, Conway's chained arrow notation, and tetration(power tower),

\[\begin{align*}G = g_{64} &= 3 \rightarrow 3 \rightarrow g_{63} \\ ... \\ g_{2} &= 3 \rightarrow 3 \rightarrow g_{1} \\ g_{1} &= 3 \rightarrow 3 \rightarrow 4 \end{align*}\]

\(g_{1}\) is already insanely huge number.

\[\begin{align*} g_{1} &= 3 \uparrow\uparrow\uparrow\uparrow 3 \\ &= 3 \uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow 3 \\ &= 3 \uparrow\uparrow\uparrow (3 \uparrow\uparrow 3 \uparrow\uparrow 3) \\ &= 3 \uparrow\uparrow\uparrow (3 \uparrow\uparrow (3 \uparrow 3 \uparrow 3)) \\ &= 3 \uparrow\uparrow\uparrow (3 \uparrow\uparrow (3 \uparrow 27)) \end{align*}\]

\(3 \uparrow 27 = 7625597484987\), so \(3 \uparrow\uparrow (3 \uparrow 27)\) is 3 exponentiated by itself 7625597484987 times. Another way to write that is \(^{7625597484987}3\). That still doesn't come close to giving us the value of \(g_{1}\).

We still have to compute \(3 \uparrow\uparrow\uparrow (^{7625597484987}3)\), and all we will have accomplished is to have determined the number of \(\uparrow\) for \(g_{2}\). Considering how impossibly large \(g_{1}\) seems to be when it's Knuth up-arrow notation had a measly 4 \(\uparrow\), then imagine how \(g_{2}\) must dwarf \(g_{1}\) since it's Knuth up-arrow notation will have \(g_{1} \uparrow\). Then that continues on, each step from \(g_{2}\) to \(g_{64}\) being unbelievably larger than the previous step.