Mathematics desk
< March 12	<< Feb \| March \| Apr >>	March 14 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

March 13

Identification of prime numbers generated by a formula

How can the prime numbers generated by a formula like n(n+1) + 1 be identified with a general procedure to find which positive integer n gives a prime when n takes consecutively increasing values starting from 1? Thanks.--82.137.13.235 (talk) 14:56, 13 March 2018 (UTC)[reply]

See Formula for primes. –Deacon Vorbis (carbon • videos) 15:23, 13 March 2018 (UTC)[reply]

Some numbers can be eliminated because they have small or known factors but apart from that there is no known method other than making a primality test on each number, e.g. with trial division to the square root. The Bunyakovsky conjecture predicts there are infinitely many primes of form n(n+1) + 1 = n² + n + 1, but this has not been proved for any polynomial of degree above 1. OEIS:A002384 shows the first n values and links a table with the first 10000 values. This data can be computed in a fraction of a second with a simple PARI/GP script:

for(n=1, 10^5, if(isprime(n*(n+1)+1), print1(n", ")))

Seeing that line is all you need to experiment with other formulas if you download PARI/GP which is free. You don't need to know programming if you can just replace the limits and formula. PrimeHunter (talk) 16:02, 13 March 2018 (UTC)[reply]

If you use PARI/GP to search large primes then use ispseudoprime instead of isprime. It doesn't make a full primality proof but it's far faster and almost guaranteed to only give primes in practice. PrimeHunter (talk) 16:09, 13 March 2018 (UTC)[reply]

Does PARI/GP identify (with a script line) multiples of 3, 5, 7,... from that formula? Is there some (recursive) regularity to show for wich n the result is M3, M7, etc? (I suppose that this might be easier to identify than primes, isn't it?)--82.137.15.71 (talk) 21:09, 18 March 2018 (UTC)[reply]

isprime(x) computes the value of x and starts with trial factoring by small primes including 3, 5, 7. If no small prime factor is found then other primality tests are used. isprime(x) does not use the form of x if it is given as a formula like above. For many formulas including all polynomials in one variable, a specific prime factor p occurs at regular intervals. Prime sieves can use this to be faster than making trial factoring of each candidate, but the above script does not do this. PrimeHunter (talk) 22:44, 18 March 2018 (UTC)[reply]