brainwagon

A friend of mine was working on a programming exercise, and it turns it out was based on a chunk of math which I thought I should have seen before, but either have not seen or have forgotten. It’s basically that the products of all primes less than some number n is less than or equal to eⁿ and in the limit converges to precisely eⁿ. First of all, I wrote a chunk of code to test it out, at least for primes less than a million. Here’s the code I wrote (I swiped my rather bizarre looking prime sieve code from a previous experiment with different sieving algorithms):

[sourcecode lang=”python”]
from random import randint
from math import sqrt, ceil, floor, log
import time
import sys
from math import *

def sieveOfErat(end):
if end < 2: return []

#The array doesn’t need to include even numbers
lng = ((end/2)-1+end%2)

# Create array and assume all numbers in array are prime
sieve = [True]*(lng+1)

# In the following code, you’re going to see some funky
# bit shifting and stuff, this is just transforming i and j
# so that they represent the proper elements in the array

# Only go up to square root of the end
for i in range(int(sqrt(end)) >> 1):

# Skip numbers that aren’t marked as prime
if not sieve[i]: continue

# Unmark all multiples of i, starting at i**2
for j in range( (i*(i + 3) << 1) + 3, lng, (i << 1) + 3):
sieve[j] = False

# Don’t forget 2!
primes = [2]

# Gather all the primes into a list, leaving out the composite numbers
primes.extend([(i << 1) + 3 for i in range(lng) if sieve[i]])

return primes

sum = 0.
for p in sieveOfErat(1000000):
sum += log(p)
print p, sum/p
[/sourcecode]

Most of the code is just the sieve. In the end, instead of taking a very large product, we instead take the logarithm of both sides. This means that the sum of the logs should be nearly equal to n. The program prints out the value of the prime, and how sum compares to the value of p. Here’s a quick graph of the results:

Note, it’s not monotonically increasing, but it does appear to be converging. You can run this for higher and higher values and it does appear to be converging to 1.

This seems like a rather remarkable thing to me. The relationship between e and primes seems (to me) completely unobvious, I wouldn’t have any idea how to go about proving such a thing. A quick search on Wikipedia reveals this page on the primorial function but similarly gives little insight. Recalling Stirling’s approximation for ordinary factorials suggests that these large products are related to exponentials (Stirling’s approximation not only has a factor of e in it, but also the square root of two times pi as well), but the idea that the product of primes would precisely mimic powers of e seems deeply mysterious…

Any math geniuses out there care to point me at a (hopefully simple) explanation of why this might be? Or is the explanation far from simple?