Page 1 of 1

Can I have your prime number?

Posted: Tue Jan 27, 2009 5:12 am UTC
by A_of_s_t
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.

Re: Can I have your prime number?

Posted: Tue Jan 27, 2009 5:19 am UTC
by Qoppa
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.

Re: Can I have your prime number?

Posted: Tue Jan 27, 2009 5:28 am UTC
by auteur52
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).

Re: Can I have your prime number?

Posted: Tue Jan 27, 2009 5:35 am UTC
by t0rajir0u
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.

Re: Can I have your prime number?

Posted: Tue Jan 27, 2009 7:12 am UTC
by BlueNight
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.

Re: Can I have your prime number?

Posted: Tue Jan 27, 2009 7:19 am UTC
by Macbi
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?

Re: Can I have your prime number?

Posted: Tue Jan 27, 2009 7:58 am UTC
by BlueNight
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.

Re: Can I have your prime number?

Posted: Tue Jan 27, 2009 8:12 am UTC
by jestingrabbit
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.

Re: Can I have your prime number?

Posted: Tue Jan 27, 2009 9:15 am UTC
by phlip
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.

Re: Can I have your prime number?

Posted: Tue Jan 27, 2009 10:18 am UTC
by chapel
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.

Re: Can I have your prime number?

Posted: Tue Jan 27, 2009 12:17 pm UTC
by Ended
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.

Re: Can I have your prime number?

Posted: Tue Jan 27, 2009 2:51 pm UTC
by MartianInvader
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).

Re: Can I have your prime number?

Posted: Tue Jan 27, 2009 4:25 pm UTC
by PM 2Ring
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.

Re: Can I have your prime number?

Posted: Tue Jan 27, 2009 5:53 pm UTC
by antonfire
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.

Re: Can I have your prime number?

Posted: Tue Jan 27, 2009 5:59 pm UTC
by t0rajir0u
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.

Re: Can I have your prime number?

Posted: Tue Jan 27, 2009 6:08 pm UTC
by Brooklynxman
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.

Re: Can I have your prime number?

Posted: Tue Jan 27, 2009 6:18 pm UTC
by quintopia
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.

Re: Can I have your prime number?

Posted: Wed Jan 28, 2009 5:33 am UTC
by BlueNight
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.

Re: Can I have your prime number?

Posted: Wed Jan 28, 2009 6:03 am UTC
by t0rajir0u
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.

Re: Can I have your prime number?

Posted: Wed Jan 28, 2009 6:26 am UTC
by skeptical scientist

Re: Can I have your prime number?

Posted: Wed Jan 28, 2009 6:35 am UTC
by qinwamascot
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.

Re: Can I have your prime number?

Posted: Wed Jan 28, 2009 8:23 am UTC
by Cosmologicon
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?

Re: Can I have your prime number?

Posted: Wed Jan 28, 2009 8:57 am UTC
by qinwamascot
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.

Re: Can I have your prime number?

Posted: Wed Jan 28, 2009 11:26 am UTC
by evilbeanfiend
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

Re: Can I have your prime number?

Posted: Wed Jan 28, 2009 2:47 pm UTC
by MartianInvader
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.

Re: Can I have your prime number?

Posted: Thu Jan 29, 2009 2:42 am UTC
by chapel
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.

Re: Can I have your prime number?

Posted: Thu Jan 29, 2009 4:38 pm UTC
by PM 2Ring
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 sys

def 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 s

def 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.

Re: Can I have your prime number?

Posted: Thu Jan 29, 2009 10:18 pm UTC
by t0rajir0u
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.

Re: Can I have your prime number?

Posted: Sat Feb 07, 2009 3:53 pm UTC
by PM 2Ring
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;
}

Re: Can I have your prime number?

Posted: Sat Feb 07, 2009 11:47 pm UTC
by ST47
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.

Re: Can I have your prime number?

Posted: Sun Feb 08, 2009 6:36 am UTC
by PM 2Ring
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.