## Can I have your prime number?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

A_of_s_t
Posts: 180
Joined: Tue Aug 26, 2008 5:10 am UTC
Contact:

### Can I have your prime number?

Why are prime numbers important, and what repercussions would there be if the Riemann hypothesis could be proven? Why should the distribution of prime numbers affect anything at all -- especially chaos theory? Why should we even care which numbers are “prime” anyway?

Pi(x) ~ x/ln(x)

After reading a bit on the distribution of primes, I was wondering if the percentage of error associated with this function tends to 0 as x tends to infinity? The three books I have on the matter fail to mention this. They mention a few percentages of error for a few x values and fail to mention anything more.
Check out my web interzones powered by Web 3.0 technology running on Mozzarella Foxfire:
Spoiler:

Qoppa
Posts: 694
Joined: Sat Nov 24, 2007 9:32 pm UTC
Location: Yes.

### Re: Can I have your prime number?

Prime numbers are hugely important in cryptography. Also, from a purely mathematical stand point, the Riemann hypothesis is important since there are a lot of other theorems which have been proved, but only on the assumption that the Riemann hypothesis is true.

Code: Select all

_=0,w=-1,(*t)(int,int);a()??<char*p="[gd\~/d~/\\b\x7F\177l*~/~djal{x}h!\005h";(++w<033)?(putchar((*t)(w??(p:>,w?_:0XD)),a()):0;%>O(x,l)??<_='['/7;{return!(x%(_-11))?x??'l:x^(1+ ++l);}??>main(){t=&O;w=a();}

auteur52
Posts: 165
Joined: Sun Mar 23, 2008 11:08 pm UTC

### Re: Can I have your prime number?

Prime numbers are important for an endless number of reasons, but the most immediately accessible is the fact that every integer is uniquely factorable as a product of primes, i.e., 60=2*2*3*5. So for instance, the RSA algorithm for security over the internet is based on factorization of prime numbers. The repercussions of the Riemann Hypothesis depend on whether the proof is constructive or not. We already know the consequences of the Hypothesis being true or false, so we will only gain something new if the proof tells us something (and this could lead to great breakthroughs in factorization algorithms).

t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

### Re: Can I have your prime number?

Qoppa wrote:Prime numbers are hugely important in cryptography.

This. The way modern cryptography works is that decrypting a message without its private key should involve solving a "hard" problem, and factorization is one of the "hardest" problems we know. RSA, for example, bases all of its security on how hard it is to factor a product of two primes into its component primes. Anything we know about primes gives us information about factorization, so it's popularly stated (although not quite accurate) that a proof of the Riemann Hypothesis would "break cryptography." The results wouldn't be that drastic, but certainly a proof of RH would considerably advance our understanding of primes (the proof, mind you, not the result), and hence of cryptosystems that take advantage of the difficulty of prime factorization, considerably.

("Breaking cryptography" is actually much more likely of P vs. NP if you want to look at Millennium problems: a proof that P=NP makes cryptography as we understand it "impossible" (although this has to be defined in a fairly precise way, which is why I'm saying it in quotes).)

I'm not sure what you mean by chaos theory, but the prime numbers are simply fundamental from a mathematical point of view. It is often said that they are the "building blocks" of the integers, but I would prefer to say that the most interesting structures related to the integers are built from the prime numbers instead. There is a significant amount of mathematical interest in the subject for its own sake, not only for its fundamentality, but also for its extreme difficulty.

As for your last question, the limit as stated is equivalent to the statement that the percent error goes to zero. Do you want to know about convergence rate? This is a question that the Riemann Hypothesis will help settle!

Some slides from a wonderful talk about the primes are available here.
Last edited by t0rajir0u on Tue Jan 27, 2009 5:54 pm UTC, edited 1 time in total.

BlueNight
Posts: 270
Joined: Sat Aug 18, 2007 3:59 am UTC
Location: Albuquerque
Contact:

### Re: Can I have your prime number?

A_of_s_t wrote:Why are prime numbers important, and what repercussions would there be if the Riemann hypothesis could be proven? Why should the distribution of prime numbers affect anything at all -- especially chaos theory? Why should we even care which numbers are “prime” anyway?

By examining the properties of prime numbers, we learn a lot about the inherent basics of math and logic. For example, by applying a few simple rules to the concept of "counting things," we obtain things that are completely expected additionally, yet totally new multiplicatively.

By the way, there are an infinite number of primes that are two units apart because there are an infinite number of odd triangular numbers.
---------
BlueNight

Macbi
Posts: 941
Joined: Mon Apr 09, 2007 8:32 am UTC
Location: UKvia

### Re: Can I have your prime number?

BlueNight wrote:By the way, there are an infinite number of primes that are two units apart because there are an infinite number of odd triangular numbers.

Wait, what?
Indigo is a lie.
Which idiot decided that websites can't go within 4cm of the edge of the screen?
There should be a null word, for the question "Is anybody there?" and to see if microphones are on.

BlueNight
Posts: 270
Joined: Sat Aug 18, 2007 3:59 am UTC
Location: Albuquerque
Contact:

### Re: Can I have your prime number?

Macbi wrote:
BlueNight wrote:By the way, there are an infinite number of primes that are two units apart because there are an infinite number of odd triangular numbers.

Wait, what?

Check the thread on triangular numbers. Take a look at twin prime pairs, and notice how many of them are x-2 and x-4 where x is a triangular number.
---------
BlueNight

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Can I have your prime number?

BlueNight wrote:
Macbi wrote:
BlueNight wrote:By the way, there are an infinite number of primes that are two units apart because there are an infinite number of odd triangular numbers.

Wait, what?

Check the thread on triangular numbers. Take a look at twin prime pairs, and notice how many of them are x-2 and x-4 where x is a triangular number.

What we're talking about here is the twin primes conjecture.

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

You'll notice it says there that its unsolved. You might be able to turn what you've said into a proof of the twin primes conjecture, but I wouldn't hold my breath if I were you.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

phlip
Restorer of Worlds
Posts: 7572
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

### Re: Can I have your prime number?

If you're claiming that x-2 and x-4 are both prime for any x an odd triangular number, my counterexample is x = 171 = 17*18/2 = 132 + 2.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

chapel
Posts: 121
Joined: Mon Dec 01, 2008 8:52 am UTC

### Re: Can I have your prime number?

phlip wrote:If you're claiming that x-2 and x-4 are both prime for any x an odd triangular number, my counterexample is x = 171 = 17*18/2 = 132 + 2.

I think he is saying that x-2 and x-4 are both prime with high probability when x is an odd triangular number. One would be hard pressed to turn that into a proof of twin primes.

Ended
Posts: 1459
Joined: Fri Apr 20, 2007 3:27 pm UTC
Location: The Tower of Flints. (Also known as: England.)

### Re: Can I have your prime number?

A_of_s_t wrote:Pi(x) ~ x/ln(x)

After reading a bit on the distribution of primes, I was wondering if the percentage of error associated with this function tends to 0 as x tends to infinity?

It does; this is known as the prime number theorem. In general, f(x) ~ g(x) means that f and g are asymptotically equal, i.e.

limx->infinityf(x)/g(x) = 1.

Note however that the absolute error |Pi(x) - x/ln(x)| does not necessarily go to zero. In fact, finding an asymptotic bound for this difference is very closely related to the Riemann hypothesis.

edit: basically what t0rajir0u said.
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
-dubsola

Posts: 808
Joined: Sat Oct 27, 2007 5:51 pm UTC

### Re: Can I have your prime number?

It's worth mentioning that twin primes is one of the millennium problems. If you solve it, you get a million dollars (unless you're like Perelman and you don't want it).
Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!

PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

### Re: Can I have your prime number?

From Wikipedia:

In number theory, Skewes' number is any of several extremely large numbers used by the South African mathematician Stanley Skewes as upper bounds for the smallest natural number x for which

π(x) > li(x),

where π(x) is the prime-counting function and li(x) is the logarithmic integral function.

-------

There's a nice prime counting formula, due to Riemann IIRC, that uses the (ordinary) zeta function. I coded this formula in C years ago. It's quite small & I'm happy to post it here, if anyone's curious, and if that's allowed by the forum rules.
Last edited by PM 2Ring on Tue Jan 27, 2009 7:35 pm UTC, edited 1 time in total.

antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

### Re: Can I have your prime number?

MartianInvader wrote:It's worth mentioning that twin primes is one of the millennium problems. If you solve it, you get a million dollars (unless you're like Perelman and you don't want it).
No, it isn't.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

### Re: Can I have your prime number?

chapel wrote:I think he is saying that x-2 and x-4 are both prime with high probability when x is an odd triangular number.

Statements of this form are never correct asymptotically. One of the reasons why the primes are so enticing is that they have one of the most devious mixes of structure and randomness in all of mathematics: small primes often contain patterns (or appear to be described by patterns) that inevitably do not hold once you look to large enough primes (and "large enough" in some cases can be astronomical). Case in point: the Fermat primes.

The second issue here is that it is not even known whether a single quadratic polynomial takes prime values infinitely often, let alone a pair of quadratics. That's even harder than the twin primes conjecture.

Brooklynxman
Because I'm Awesome
Posts: 609
Joined: Tue Jan 20, 2009 4:27 pm UTC
Location: Here
Contact:

### Re: Can I have your prime number?

Agreeing with the above post mentioning cryptology, look up illegal primes, they are prime numbers it is actually illegal to publish do to their use in cryptology.
We figure out what all this means, then do something large and violent

The thing about changing the world...once you do it the world's all different.

I'm Angel. I beat the bad guys.

Spoiler:

quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

### Re: Can I have your prime number?

Not quite. "Illegal" primes are primes that encode, if converted to a bit sequence, an illegal piece of data, for instance the DeCSS algorithm. Whether or not they are illegal is the point of their existence--to point out the illegitimacy of criminalizing possession or use of certain kinds of data despite its representation.

BlueNight
Posts: 270
Joined: Sat Aug 18, 2007 3:59 am UTC
Location: Albuquerque
Contact:

### Re: Can I have your prime number?

chapel wrote:
phlip wrote:If you're claiming that x-2 and x-4 are both prime for any x an odd triangular number, my counterexample is x = 171 = 17*18/2 = 132 + 2.

I think he is saying that x-2 and x-4 are both prime with high probability when x is an odd triangular number. One would be hard pressed to turn that into a proof of twin primes.

Actually, I found a pattern that held up as far as I could calculate it by hand. When I checked it by computer (in MS Excel), it broke on the eighth item in the set, then completely fell apart by the twelfth.

For every positive integer, there is a corresponding triangular number. Let T(x) be the triangular number. Starting with T(5)=5+4+3+2+1+0=15, both T(x)-2=13 and T(x)-4=11 are prime.

The pattern was T(x) where x was five plus the square of an integer. T(5)=15, T(6)=21, T(9)=45, T(14)=105, T(21)=231, T(30)=465, T(41)=861, etc. The numbers climbed rather quickly, but each time corresponded with twin primes at T-2 and T-4. It broke at 19x127=2413, which was two less than T(5+8^2) = T(69) = 2415.

The selected values of T all ended in either a 5 or a 1, and were divisible by 3. However, I found a bug in Excel! It says T(5+6688^2) is 1000357353346570, but it's really 1000357353346575. Excel versus CALC.EXE, and CALC got the right answer. I guess Excel doesn't like 16-digit integers; all later values of T were similarly corrupt.
---------
BlueNight

t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

### Re: Can I have your prime number?

BlueNight wrote: it broke on the eighth item in the set, then completely fell apart by the twelfth.

That's exactly what I mean. Did you read my post? It is very easy to construct sequences that are coincidentally prime for small indices; they tend to fall apart more or less quickly, and this is no less true of twin primes.

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

### Re: Can I have your prime number?

I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

qinwamascot
Posts: 688
Joined: Sat Oct 04, 2008 8:50 am UTC
Location: Oklahoma, U.S.A.

### Re: Can I have your prime number?

It's not particularly interesting if you can't crash a desktop computer searching for an exception. Basically every major known conjecture that has some kind of "for all positive integers" has been checked to very large numbers. Excel, or basically any other program that isn't specifically built to deal with arbitrarily long integers, is not very useful.

As an extreme example, we could take the statement "all odd integers greater than 1 except 9 are prime". 3, 5, 7, 11, and 13 work. Of course, any reasonable mathematician would realize this is false, but unless we check enough values, we'll see patterns that don't really exist.
Quiznos>Subway

Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

### Re: Can I have your prime number?

t0rajir0u wrote:small primes often contain patterns (or appear to be described by patterns) that inevitably do not hold once you look to large enough primes (and "large enough" in some cases can be astronomical). Case in point: the Fermat primes.

That formula only generates primes for n < 6. More impressive I think is n2 - n + 41, which works for n < 41. Still not what I'd call astronomical, though. I know the smallest counterexample to the Polya conjecture almost a billion. Are there any prime patterns that last anywhere near that long?

qinwamascot
Posts: 688
Joined: Sat Oct 04, 2008 8:50 am UTC
Location: Oklahoma, U.S.A.

### Re: Can I have your prime number?

Cosmologicon wrote: Are there any prime patterns that last anywhere near that long?

Certainly, there must be some. Given the first billion or so primes, we could easily construct a polynomial function with extremely large degree such that f(n)=the nth prime when n is sufficiently small. But that's not interesting, because the complexity of that polynomial would be high, and even though the results are also very good, the ratio of goodness:complexity is not sufficiently large to be interesting.

If there is an interesting one, I can't think of it right now. Usually, these kinds of things go one of three ways. They remain unsolved for a while, and turn into extremely prominent problems like the collatz conjecture or riemann hypothesis. They are proven and become theorems, at which point people forget how much computer searching went on. Or they are disproven after a lot of computational effort, and become an example. I'm almost positive there are none of the second category. The goldbach conjecture and riemann hypothesis both have a lot to do with primes, but aren't really what you're looking for. I can't think of any of the third category right now.
Quiznos>Subway

evilbeanfiend
Posts: 2650
Joined: Tue Mar 13, 2007 7:05 am UTC
Location: the old world

### Re: Can I have your prime number?

prime numbers also come up a fair bit in FFTs e.g. the Good-Thomas algorithm

FFTs have all sorts of uses e.g. digital signal processing
in ur beanz makin u eveel

Posts: 808
Joined: Sat Oct 27, 2007 5:51 pm UTC

### Re: Can I have your prime number?

Cosmologicon wrote:That formula only generates primes for n < 6. More impressive I think is n2 - n + 41, which works for n < 41. Still not what I'd call astronomical, though. I know the smallest counterexample to the Polya conjecture almost a billion. Are there any prime patterns that last anywhere near that long?

PM 2Ring wrote:From Wikipedia:

In number theory, Skewes' number is any of several extremely large numbers used by the South African mathematician Stanley Skewes as upper bounds for the smallest natural number x for which

π(x) > li(x),

where π(x) is the prime-counting function and li(x) is the logarithmic integral function.

-------

There's a nice prime counting formula, due to Riemann IIRC, that uses the (ordinary) zeta function. I coded this formula in C years ago. It's quite small & I'm happy to post it here, if anyone's curious, and if that's allowed by the forum rules.

The conjecture π(x) < li(x) has been proven false, although it is known to be true at least up to 1014. It is believed the first counterexample is somewhere closer to 10300, though.
Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!

chapel
Posts: 121
Joined: Mon Dec 01, 2008 8:52 am UTC

### Re: Can I have your prime number?

t0rajir0u wrote:
chapel wrote:I think he is saying that x-2 and x-4 are both prime with high probability when x is an odd triangular number.

Statements of this form are never correct asymptotically. One of the reasons why the primes are so enticing is that they have one of the most devious mixes of structure and randomness in all of mathematics: small primes often contain patterns (or appear to be described by patterns) that inevitably do not hold once you look to large enough primes (and "large enough" in some cases can be astronomical). Case in point: the Fermat primes.

The second issue here is that it is not even known whether a single quadratic polynomial takes prime values infinitely often, let alone a pair of quadratics. That's even harder than the twin primes conjecture.

Of course they fall apart over time. I'm not suggesting that those would always be prime or even that they are prime most of the time. Instead, they would be a possible way to search for primes (but a primality test of some kind would have to be run). Similar to Mersenne/Fermat primes being a good way to identify possible candidates for prime numbers.

But, yeah, a proof of some such thing would be much harder than the twin primes conjecture.

PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

### Re: Can I have your prime number?

I think it's interesting to look at the primes from a complex POV. The Gaussian integers (complex numbers of the form a + bi, where a & b are both integers) have unique factorization. All the normal primes of the form 4n+3 are still prime in the Gaussians, all other primes have a Gaussian factor. Eg, 2 = (1+i)(1-i), 5 = (2+i)(2-i), and in general any prime of the form a²+b² can be factored as (a+bi)(a-bi). 1,-1,i & -i are units & don't count as prime factors. So generally a Gaussian prime of the form a+bi has "associates": a-bi, -a+bi, -a-bi, b+ai, b-ai, -b+ai, -b-ai.

We lose the traditional prime pairs when we go to the Gaussians, since one member of a prime pair must be of the form 4n+1. Instead we get little clusters of four Gaussian primes, surrounding a composite Gaussian integer. These seem to have some interesting properties. In this diagram http://i2.photobucket.com/albums/y43/PM2Ring/gauss2F.png of Gaussian primes, each prime has been coloured according to its residue mod 30 if its of the form 4n+3, or of the real prime that it's a factor of otherwise. All the non-trivial prime quads appear to be red in this diagram.

Further investigation shows that if z=a+bi, and z-1,z+1,z-i & z+i are all prime, then both a & b have factors or 25, IIRC (I'll check this later, & edit this post).

I'm sure this has some deep significance.

Edit: Actually, both a & b have factors or 5, so their squares have factors of 25. Here's a short list of the smallest (non-trivial) ones. Notice how all the real primes associated with each members of a quad end in 1.
Spoiler:
The number at the end of each line is the composite surrounded by the quad
641=(4, 25) 11, 601=(5, 24) 1, 701=(5, 26) 11, 661=(6, 25) 1, : 650=(5, 25)
15641=(4, 125) 11, 15401=(5, 124) 11, 15901=(5, 126) 1, 15661=(6, 125) 1, : 15650=(5, 125)
112241=(4, 335) 11, 111581=(5, 334) 11, 112921=(5, 336) 1, 112261=(6, 335) 1, : 112250=(5, 335)
96181=(9, 310) 1, 95581=(10, 309) 1, 96821=(10, 311) 11, 96221=(11, 310) 11, : 96200=(10, 310)
2221=(14, 45) 1, 2161=(15, 44) 1, 2341=(15, 46) 1, 2281=(16, 45) 1, : 2250=(15, 45)
67961=(19, 260) 11, 67481=(20, 259) 11, 68521=(20, 261) 1, 68041=(21, 260) 1, : 68000=(20, 260)
15241=(29, 120) 1, 15061=(30, 119) 1, 15541=(30, 121) 1, 15361=(31, 120) 1, : 15300=(30, 120)
19301=(49, 130) 11, 19141=(50, 129) 1, 19661=(50, 131) 11, 19501=(51, 130) 1, : 19400=(50, 130)
34721=(64, 175) 11, 34501=(65, 174) 1, 35201=(65, 176) 11, 34981=(66, 175) 1, : 34850=(65, 175)
107981=(109, 310) 11, 107581=(110, 309) 1, 108821=(110, 311) 11, 108421=(111, 310) 1, : 108200=(110, 310)
243121=(164, 465) 1, 242521=(165, 464) 1, 244381=(165, 466) 1, 243781=(166, 465) 1, : 243450=(165, 465)
222161=(169, 440) 11, 221621=(170, 439) 11, 223381=(170, 441) 1, 222841=(171, 440) 1, : 222500=(170, 440)
197641=(204, 395) 1, 197261=(205, 394) 11, 198841=(205, 396) 1, 198461=(206, 395) 11, : 198050=(205, 395)
101281=(209, 240) 1, 101221=(210, 239) 1, 102181=(210, 241) 1, 102121=(211, 240) 1, : 101700=(210, 240)
138821=(214, 305) 11, 138641=(215, 304) 11, 139861=(215, 306) 1, 139681=(216, 305) 1, : 139250=(215, 305)
144061=(219, 310) 1, 143881=(220, 309) 1, 145121=(220, 311) 11, 144941=(221, 310) 11, : 144500=(220, 310)
114941=(229, 250) 11, 114901=(230, 249) 1, 115901=(230, 251) 11, 115861=(231, 250) 1, : 115400=(230, 250)
177601=(249, 340) 1, 177421=(250, 339) 1, 178781=(250, 341) 11, 178601=(251, 340) 11, : 178100=(250, 340)

And here's the Python source used to generate the above list:
Spoiler:

Code: Select all

#!/usr/bin/env python''' Search for Gaussian prime quads.  Build a table of square sums, then filter through   the Sieve of Eratosthenes.    Written by PM 2Ring 2008.11.28'''import sysdef primes(n):  ''' Return a boolean list of primes < n '''  s = [False]*2 + [True]*(n-2)  for i in range(2, int(n**0.5) + 1):    if s[i]:      for j in range(i*i, n, i):        s[j] = False  return sdef gaussquads(n):      ''' Search for Gaussian prime quads '''  # Build a dict of prime square sums   n2 = n*n  pr = primes(n2)  sq = [(i, i*i) for i in xrange(n)]  sums = {}  for i, i2 in sq[1: -1]:    for j, j2 in sq[i+1: n: 2]:      s = i2 + j2      if s >= n2:        break      if pr[s]:        sums[(j, i)] = s          sums[(i, j)] = s            keys = sums.keys()  keys.sort()        for t in keys:    a, b = t    #if b < a: continue    #Eliminate entries that straddle the diagonal    if b <= a+1: continue             #See if this is the start of a group of 4    group = [(a+1, b-1), (a+1, b+1), (a+2, b)]    for g in group:      if g not in sums:            break    else:            group[:0] = [t]      for u in group:        s = sums[u]        #Norm=(Gaussian prime) modulus        print "%d=%s %d,\t" % (s, u, s%30),      s = (a+1)**2 + b*b      print ": %d=%s" % (s, (a+1, b))   def main():  n = len(sys.argv) <= 1 and 500 or int(sys.argv[1])  gaussquads(n)if __name__ == "__main__":  main()

Edit. Actually, the colour scheme in the linked image is based on the residue mod 10. Sorry about that.
Last edited by PM 2Ring on Sun Mar 08, 2009 2:24 pm UTC, edited 2 times in total.

t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

### Re: Can I have your prime number?

There is a whole field of number theory concerned with how primes split in various extensions of the rationals; see, for example, Chebotarev's density theorem. The results in the Gaussian integers are just the tip of the iceberg, in some sense, although they also have some special properties.

PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

### Re: Can I have your prime number?

PM 2Ring wrote:There's a nice prime counting formula, due to Riemann IIRC, that uses the (ordinary) zeta function. I coded this formula in C years ago.

Here it is, in case anyone's curious.

Code: Select all

/* *  R I E M * *  A function found by Riemann for Pi(x), the number of primes <= x. * *  These are the formulae, using a modified form of Sigma notation. *  Inf is infinity, ** is exponentiation and ! is factorial: * *  Riemann(x) = 1 + Sigma(i=1 to Inf; log(x)**i / (i! * i * Zeta(i+1))) *  Zeta(x) = Sigma(i=1 to Inf; 1/i**x) * *  Here is the function compared to some actual values of Pi(x): * *       The distribution of primes *       -------------------------- *   x            Pi(x)      Riemann(x) * * 1E1                4               5 * 1E2               25              26 * 1E3              168             168 * 1E4            1,229           1,227 * 1E5            9,592           9,587 * 1E6           78,498          78,527 * 1E7          664,579         664,667 * 1E8        5,761,455       5,761,552 * 1E9       50,847,534      50,847,455 * 1E10     455,052,511     455,050,683 * *  Written by PM 2Ring. Public Domain. *  May  8 1994 *  Oct  1 1998 Converted to C */#include <ctype.h>#include <stdio.h>#include <stdlib.h>#include <math.h>/* Default arguments */#define LO 1#define HI 1000#define MK 60#define MI 240#define LOK 5       /* Lowest Zeta function we must calculate *//* Comparison tolerance */#define CT 1E-18/* Verbose reporting flag */int verbose;/* Zeta function table parameters & pointer */int mk = MK, mi = MI;double *zeta;/* Build Zeta function table. */void MakeZeta(void){    int k;    double i, t, s;    zeta = malloc(mk * sizeof(double));    if (!zeta)    {        printf("No memory for Zeta table - Aborting.\n");        exit(10);    }    /* These ones take a long time to converge */    zeta[2] = 1.644934066848226436472415166646; /* Pi^2/6 */    /* zeta[3] = 1.2020569030229; */    zeta[3] = 1.202056903159585353;             /* 1 million terms */    zeta[4] = 1.082323233711138191516003696541; /* Pi^4/90 */    printf("Calculating Zeta table from %d to %d,"        " using %d terms per series.\n", LOK, mk, mi);    for (k = LOK; k < mk; k++)        zeta[k] = 1.;    /* First calculate series with alternating +ve & -ve terms.       This helps to minimize rounding errors */    for (i = 2., s = -1.; i < mi; i+=1., s=-s)    {        t = i * i; t = 1 / (t * t);        for (k = LOK; k < mk; k++)        {            if (t < CT)                break;            t /= i;            zeta[k] += s * t;        }    }    /* Convert alternating series to actual Zeta functions */    for (k = LOK, t = 16.; k < mk; k++, t*=2.)        zeta[k] = zeta[k] * t / (t - 1.);    /* Display whole table */    if (verbose)        for (k = 2; k < mk; k++)            printf("%d: %.20f\n", k, zeta[k]);}/* Calculate Riemann function. */double Riemann(double num){    int k;    double r, l, lt, zt;    if (num <= 1.)        return 0.;    r = 1.;    lt = l = log(num);    for (k = 2; k < mk; k++)    {        zt = (k - 1) * zeta[k];        r += lt / zt;        lt *= l / k;    }    return r;}/* Test Riemann function */int main(int argc, char *argv[]){    double lo = LO, hi = HI, lor, hir;    if (argc>1 && *argv[argc-1] == '?')    {        printf("Calculate approximate number of primes in an interval\n"            "using Riemann's Zeta function.\n Usage:\n");        printf("%s [hi] [lo] [zeta] [terms] [verbose]\n", argv[0]);        exit(10);    }    switch (argc)    {        /* WARNING: Drop-through cases! */        default:        case 6: verbose = toupper(*argv[5]) == 'V';        case 5: mi = atoi(argv[4]);        case 4: mk = atoi(argv[3]);        case 3: lo = atof(argv[2]);        case 2: hi = atof(argv[1]);        case 1:        case 0: break;    }    /* Allocate & build Zeta function table */    MakeZeta();    /* Calculate Riemann function */    lor = Riemann(lo);    hir = Riemann(hi);    printf("%.0f: %.12f\n", lo, lor);    printf("%.0f: %.12f\n", hi, hir);    printf("Number of primes is approx. = %.0f\n", hir - lor);    free(zeta);    return 0;}

ST47
Posts: 125
Joined: Tue Oct 16, 2007 6:42 pm UTC

### Re: Can I have your prime number?

Cosmologicon wrote:
t0rajir0u wrote:small primes often contain patterns (or appear to be described by patterns) that inevitably do not hold once you look to large enough primes (and "large enough" in some cases can be astronomical). Case in point: the Fermat primes.

That formula only generates primes for n < 6. More impressive I think is n2 - n + 41, which works for n < 41. Still not what I'd call astronomical, though. I know the smallest counterexample to the Polya conjecture almost a billion. Are there any prime patterns that last anywhere near that long?

Interesting on the second point. I never thought about this before, but I wonder if it's significant that it breaks at n=c.

Edit: Disregard that, I'm an idiot.

PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

### Re: Can I have your prime number?

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

Euler's prime-generating polynomial

n2 + n + 41,

which gives (distinct) primes for n=0, ... 39, is related to the Heegner number 163.

In number theory, a Heegner number is a (square-free) positive integer d such that
the imaginary quadratic field [imath]\mathbf{Q}(\sqrt{-d})[/imath] has class number 1.
Equivalently, its ring of integers has a unique factorization.

According to the Stark–Heegner theorem there are precisely nine Heegner numbers:

1, 2, 3, 7, 11, 19, 43, 67, 163.

This result was conjectured by Gauss and proven by Kurt Heegner in 1952.