Associated Topics || Dr. Math Home || Search Dr. Math

Prime Number Formula

```
Date: 11/11/2001 at 18:10:27
From: Ri
Subject: Prime number formula

I have to find out the formula Leonhard Euler used to find prime
numbers.  I just need the formula so I can put it into a spreadsheet.

Thank you.
```

```
Date: 11/11/2001 at 19:21:56
From: Doctor Paul
Subject: Re: Prime number formula

Following is a somewhat celebrated result of Euler:

The function f(x) = x^2 + x + 41 is prime for x = 0, 1 ,..., 39

f(41) is obviously not prime because
f(41) = 41^2 + 41 + 41 = 41 * (41 + 1 + 1)

f(40) = 40^2 + 40 + 41

But notice that another way to write 40^2 is:

40^2 = 40^2 + 2*40 + 1 - 2*40 - 1 = (40 + 1)^2 - 2*40 - 1

Then

f(40) = 40^2 + 40 + 41 = (40 + 1)^2 - 2*40 - 1 + 40 + 41 = 41^2

hence f(40) isn't prime either.

This quadratic was the record holder for centuries as a consecutive,
distinct quadratic prime-producer for an initial range of input
values. It is not, however, the current record holder. That
distinction goes to the function:

f(x) = 36x^2 - 810x + 2753

which is prime for x = 0, 1, ... , 44

I do not know who this result is attributed to.

For more, see the June/July issue of "The American Mathematical
Monthly" (any university library will have it) for an article entitled

- Doctor Paul, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search