a number, X, can be found to be prime by dividing the first sqr(X) integers into X. not sure why it works though.
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 )
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.
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...
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.
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.
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. ,
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\).
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.
That's very interesting. Why would a formula work for a few thousand but suddenly fail when it reaches a certain prime?
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)
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.
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!