There is also a formula first noticed by Leonhard Euler which proves that the set of primes is endless. The formula is

x²+x+41 is always a prime no. if x is an integer.

This cannot be true: just take x = 41 for instance, which clearly factorises into non-trivial factors. Euler found that this polynomial produces 40 distinct primes for the first 40 values.

In fact, it can be shown that such a polynomial cannot exist.

]]>x²+x+41 is always a prime no. if x is an integer.

That is not always true. Try x = 41.

]]>x²+x+41 is always a prime no. if x is an integer.]]>

I am switching to this thread because I think this tread is more appropriate for posts dealing with primes. I have previously posted on the "help me" thread.

I am a small time prime hobbyist and have previously posted two "algorithms" that I have developed roughly on my own devices, although I have learned of similar formulations by other researchers/mathematicians, so my stuff might be "copies" or inferior models of what have already been done. I will post my first two "algorithms posted elsewhere on this site for information and comment/criticism!

#1

The 1st algorithm is a variation on the Sieve of Eratosthenes, but actually not a real sieve, but rather a combination of sieve and modulo operations. I discovered recently that there are similar sieves out there (e.g by David Turner of St Andrews University and others -See Wikipedia) so not too sure about the uniqueness of this algorithm therefore. However I did develop the sieve on my own, and I suspect it would be slightly different (and perhaps inferior) to the others. It involves the following; (#1) Take number line of positive integers, 1,2,3....... (#2) strike out all multiples of 2 leaving odd numbers (#3) Identify/mark "3" as a (new) prime number since "3" is not divisible by any positive integer (excluding "1") smaller than itself without leaving a remainder. Calculate square of the newly identified prime (9 in this case). For all odd numbers between 3 and 9 divide by the first prime "2" -all primes less that square root of 9,....nothing to eliminate since 4, 6 & 8 were already eliminated, leaving 5 & 7 as new primes. Now take next prime namely "5". Square of this prime is "25" Now divide all the (odd) numbers remaining on the number line between 9 & 25, by all the identified primes less than "5", namely "2" & "3" . "2" can actually be dropped since all the even numbers had already been eliminated from the number line. This operation eliminates "15,18 & 21", identifying 11,13,17,19 & 23 as primes. (#4) Now do the same for the odd numbers between "25" and the next prime (7=49), dividing with the identified primes less than the square root of (49=7), repeating this operation step by step. The beauty of this operation/algorith is that it identifies primes well ahead of the primes being used in the "sector" being appraised.

#2

My second algorithm is much more curious. We all know that the seemingly random distribution of primes have been a source of amazement to mathematicians for centuries, making it impossible to predict accurately a pattern or the next prime number. However, I have discovered that adding primes together in a particular way (in fact the summing operation of primes seem to produce many solid patterns)-namely consecutive sum of primes produces very REGULAR curves (with coefficients of determination(R^2) of "1" or close to "1"), using the regularity of the obtained curve to "predict" the next prime. This I can do to an accuracy which appear to be an improvement of the estimation provided by the Prime Number Theorum (PNT), and the curve functions anywhere in a series of prime numbers as opposed to the PNT which is more accurate as it approaches infinity. One of the summations is like this (consecutive sum); Add the first two together. Then to the sum add the next prime. To this sum add the next prime number and so on....(p+p), (p+p+p),(p+p+p+p).....This produces a curve of almost perfect slope, whereby it is possible to the predict the NEXT prime by using a trend line or the polynomial equation of the formula. If this curve is true one could potentially predict primes or the location of primes to great numbers. Although I tested the series of consecutive primes in the "Series Encylopedia(OEIS)" it exists, but graphing this series to determine prime numbers has not been done before I think.

I would appreciate further comment.

]]>1 No. not factorable by 2 in (2)

There are 2 No.'s not factorable by 2 or 3 in (6)

There are 8 No.'s not factorable by 2 or 3 or 5 in (30)

There are 48 No.'s not factorable by 2 or 3 or 5 or 7 or in (210)

times 48 by (prime -1) to get the next number of no.'s. i.e. =480 no.'s in (2310) not factorable by 2,3,5,7, or 11.....and so on.]]>

6+/-1 5..

30+/- 1 7..

210 +/- 1 11..

2310 +/- 1 13..

equals primes......to a certain point above highest prime squared. e.g.>9,25,49,121 or 169 accordingly. And so on but the numbers get very big but you can do this up to infinity.

]]>http://en.wikipedia.org/wiki/Largest_known_prime_number

How is 17,425,170 a prime number? It is divisible by 2.

Thanks

It clearly says in plain English that this number is the number of digits of the largest known prime number. You're welcome?

]]>x = prime

y = anything other than 1 and x

z = composite

a = decimal

x/1=x. x/x=1. x/y=a.

z/1=z. z/z=1. z/y=y.

For something else on prime numbers... go to my Sieve of Eratosthenes post.]]>

Welcome to the forum!

]]>Welcome to the forum!

]]>For prime numbers (r), under 5 squared; r = 3p +/- 2 or 4

For prime numbers (i), under 7 squared; i = 5r +/- 6 or 12 or 18 or 24

For prime numbers (m), under 11 squared; m = 7i +/- 30 or 60 or 90 or 120 or 150 or 180

For prime numbers (e), under 13 squared; e = 11m +/- 210 or 420 or 630 or 840 or 1050 or 1260 or 1470 or 1680 or 1890 or 2100

(A no. divisible by a, but not divisible by a group b +/- A no. divisible by group b, but not a = A no. not divisible by a or b.)

* Some rules give 1 but this is not prime.

]]>I am looking for one. I have one written for Mathematica but not for anything else just yet.

The Miller - Rabin does not need to factor the number. It is quite fast, but it is not deterministic. It can only provide a probabilty that the number is composite. Of course this probabilty can be made very, very small.

]]>I haven't try AKS method yet, if you could provide me the link of any program using that method let me know. I know, ECM is not for proving and disproving but the guy had incorporated Rabin-Miller probabilistic test in the program and it would tell you whether the number is prime or not at the end of factorization. Anyway, it would be a great help if you could provide me a link where to download or use AKS method. For your information I haven't got into programming for quite long time and to write a program for checking primality on my own would take some times.

By the way, thanks for your suggestion and idea it is a great help.

]]>Depends on what you mean by better. The ECM is for factoring a number not for proving or disproving primality. Factoring is much harder problem than proving primality.

There are two types of tests for primality that I know of. The AKS developed by 3 Indian fellows and Rabin Miller which is a probabilistic test.

]]>