Is there any pattern in prime numbers?

Discussion in 'Physics & Math' started by At World's End, Dec 9, 2008.

  1. leopold Valued Senior Member

    Messages:
    17,455
    a number, X, can be found to be prime by dividing the first sqr(X) integers into X.
    not sure why it works though.
     
  2. Google AdSense Guest Advertisement



    to hide all adverts.
  3. temur man of no words Registered Senior Member

    Messages:
    1,330
    There are formulas that can be used to generate prime numbers, but do not give much insight, such as

    n-th prime = n-th number that can be divisible only to itself and 1.

    n-th prime = ( a subroutine written in some algorithmic language that generates n-th prime )
     
  4. Google AdSense Guest Advertisement



    to hide all adverts.
  5. Absane Rocket Surgeon Valued Senior Member

    Messages:
    8,989
    Ulam's Prime Spiral, eh?

    What's fascinating about it is that by setting any prime number as a new center allows one to create prime generating polynomials.
     
  6. Google AdSense Guest Advertisement



    to hide all adverts.
  7. LogicTech Registered Member

    Messages:
    119
    There are many ways to check whether a number is prime or not. As such some algorithms have been discovered:

    http://en.wikipedia.org/wiki/AKS_primality_test
    http://en.wikipedia.org/wiki/Fermat_primality_test
    http://en.wikipedia.org/wiki/Lucas-Lehmer_test
    http://en.wikipedia.org/wiki/Solovay-Strassen_primality_test
    http://en.wikipedia.org/wiki/Miller-Rabin_primality_test
    http://en.wikipedia.org/wiki/Elliptic_curve_primality_proving

    Not sure which ones are the best though...
     
  8. D H Some other guy Valued Senior Member

    Messages:
    2,257
    The problem of determining whether a given number is a prime is very different from the problem of determining the N[sup]th[/sup] prime number. Primes is in P. Generating primes almost certainly is not.
     
  9. gotanygum Registered Member

    Messages:
    27
    I'm fascinated by the graphical representations of eratosthenes sieve, the ulam spiral, also more recently by some others, one called 'divisor plot'

    www.divisorplot.com

    and another called 'numberspiral'

    www.numberspiral.com

    marko rodin's "phyllotaxis prime number sieve" which mimics the daisy [fibonacci] growth patterns:

    www.worldofheaven.com/messages_data...llotaxis_Prime_Number_Seive_feb_2004_en_0.pdf

    .... and lastly, the pascal triangle sieve [also interesting are 'hockey stick pattern' in the pascal triangle as well]:

    http://www.cut-the-knot.org/Curriculum/Arithmetic/PrimesFromTriangle.shtml

    maybe these are already mentioned or not...but to be able to find a formula that can show anywhere any prime number might be based on some kind of pattern, seems impossible I think.
     
    Last edited: Jan 12, 2009
  10. MITconstantine Registered Member

    Messages:
    1
    I have discovered a formula, a set of 4 very simple equations, with 2 variables which create all prime numbers and a very interesting and simple pattern emerging out of them. Prime numbers have been in my head since my MIT days. Since it is the first time I use sciforums, please, also, email me your comment.
    ,
     
  11. eram Sciengineer Valued Senior Member

    Messages:
    1,877
    Okay, show us how this works.
     
  12. Fednis48 Registered Senior Member

    Messages:
    725
    If \(X\) is not prime, there is at least one choice of integers \(a>1\) and \(b>1\) such that \(ab=X\). It's always true that \(X=\sqrt{X}\sqrt{X}\), so \(ab=\sqrt{X}\sqrt{X}\). From this expression it's clear that if one of \(a\) or \(b\) is greater than \(\sqrt{X}\), the other must be less than \(\sqrt{X}\). Therefore, by checking all integers up to and including \(\sqrt{X}\), we will always find \(a\) or \(b\).
     
  13. rpenner Fully Wired Valued Senior Member

    Messages:
    4,833
    Now trial division can be hard, but the odds are a random number has a relatively small prime.

    Let Y = 31610054640417607788145206291543662493274686990 (the product of primes less than 125).
    Then the prime factors of X are the prime factors of GCD(X,Y) and any remaining prime factors larger than 127.

    So if X = 125735444671444400940702097588558766334019182211645442537 we compute the GCD(X,Y) by Euclid's algorithm (repeatedly keeping the remainders from serial division) as follows:

    x=125735444671444400940702097588558766334019182211645442537
    y=31610054640417607788145206291543662493274686990
    a1=31610054640417607788145206291543662493262669757
    a2=12017233
    a3=11892879
    a4=124354
    a5=79249
    a6=45105
    a7=34144
    a8=10961
    a9=1261
    a10=873
    a11=388
    a12=97
    a13=0

    13 (progressively easier) divisions to learn that 97 divides X. That would have taken 25 trial divisions if we tested the prime numbers one-by-one and 96 trial divisions if we literally began testing all numbers less than or equal to \(\left\lfloor \sqrt{X} \right\rfloor = 11213181737198608382354387069\) Maybe that is not so attriactive if you see that this example is a little contrived, but the worst case no matter how large X is would be 155 or 156 progressively easier divisions, which is superior to 30 divisions of high complexity.
     
  14. eram Sciengineer Valued Senior Member

    Messages:
    1,877
    Are there many people working on this?
     
  15. eram Sciengineer Valued Senior Member

    Messages:
    1,877
    That's very interesting. Why would a formula work for a few thousand but suddenly fail when it reaches a certain prime?
     
  16. Fraggle Rocker Staff Member

    Messages:
    24,690
  17. eram Sciengineer Valued Senior Member

    Messages:
    1,877
    A pity. He could've almost won the Fields medal.
     
  18. jermy Registered Member

    Messages:
    9
    According to mathematics states there is no such pattern.Generally people are looking prime nuber for the base 10.For base 6 (in mathematcis point of veiw) there are two equation

    1. (1 + 6x)

    2.(-1 + 6x)
     
  19. funkstar ratsknuf Valued Senior Member

    Messages:
    1,390
    jermy, given your threads show, shall we say, less than expert understanding of maths, you would do well not to pretend expertise in number theory. Nobody's fooled, you know.
     
  20. RJBeery Natural Philosopher Valued Senior Member

    Messages:
    4,222
    I have such a formula! f(x) = x generates primes for all x not of the form a*b

    Please Register or Log in to view the hidden image!



    On a more serious note...

    \(f(x) = x^{2}-x+c \)[eqn 1], with c = {3, 5, 11, 17, 41}

    Any number theorists here will recognize this as Euler-Rabinowitsch prime generating polynomials. These equations will yield nothing but primes for x = 1..(c-1)!

    Now, analogous to my qualifier of x in f(x) = x above, when x is an integer of the form

    \(x = \frac{i(i-1)}{j}+i+cj \)[eqn 2], with integer i and j > 0

    then we know f(x) is composite, otherwise f(x) yields nothing but primes. Furthermore, when f(x) is composite we know that

    \(f(x) = \frac{(i^2+ij+cj^2)(i^2+(j-2)i+cj^2-j+1)}{j^{2}} \)[eqn 3]

    Enjoy!
     

Share This Page