# Formulae for both identifying or generating primes; Shows arranged distribution. Solved; basically trial division.

While looking at numbers and considering $n < p < 2n - 2$ and $p = 3n\pm 1$, where $p$ is any prime number, I was able identify a property for numbers $c=3n\pm 1$ where $c$ is a composite number:

Let $P_n$ be primes where $P_1 = 3, P_2 = 5,...,P_n=p$.

Every composite $c$ in $n \to x$ is of the form:

• $P_{1 \to n}y$

or

• ${P_n }^2$

Since this is true, only $n$ primes for $P_n = \pi(\sqrt{limit})-1$, where $\pi(x)$ is the prime counting function, is needed to identify all primes $P_n < p < limit$. In that case, the number of primes used to determine if $n=p$ are considerably less than in other functions that tests primes, and it's a bit more elegant, not brute-force, no randomness, e.g.

So it is possible that finding primes from $3,...,\infty$ could be done (had it not tended towards infinity, pun) by testing odd numbers consecutively and increasing $n$ for every $c = {P_n}^2$.

To test this, I needed a function to see if the number is of the form $3n\pm 1$:

$e_n(x)=\left\{\begin{matrix} 0, & x\pm 1 \not\equiv 0 \: \mod\,3\\ 1, & \end{matrix}\right.$

Then I needed to check if the number is composite based on $P_{1 \to n}y$:

$k_n(x)=\left\{\begin{matrix} 0, & x \equiv 0 \: \mod\,\forall\in \{ P_1,...,P_{n-1} \}\\ 1, & \end{matrix}\right.$

I also needed to check if ${P_n }^2$ where $n = \pi(\sqrt{limit})-1$:

$t_n(x) = \left\{\begin{matrix} 0, & x = \,({P_n}^2)\\ 1, & \end{matrix}\right.$

Then I summed it all into one function:

isPrime$_n(x) = t_n(x) \mid k_n(x) \mid e_n(x),\,\,$ if $\,\, {\pi(\sqrt x)} = n$

Where $\mid$ is logical operator AND.

From this it's easy to create an algorithm which yields primes, and only primes, without sieving or performing complex calculations.

Example pseudo-code:

n = 1: Counts number of primes in use by algorithm
N = {3,5,7,9,...,limit}: All natural odd numbers from 3 to limit
P = {3}: The first odd prime number, the others found are appended

for all numbers x in set N do:
if not t(x,n):
n = n + 1, next
if not k(x,n):
next;
if e(x,n):
Append x to P, next


This yields primes and only primes.

Here's an example that uses Python to generate primes based on this principle: (Please excuse bad formatting.)

def k(x,n):
for y in range(n):
if x%primes[y]==0:
return False
return True

def e(x,n):
global primes
def xpm(x):
return x+1,x-1
x = xpm(x)
if not (x[0]%3==0 or x[1]%3==0):
return False
return True

def t(x,n):
global primes
if x!=(primes[n-1]**2):
return True
return False

## The number of primes used, n, is printed as n but;
## if the limit has a prime power close or at the limit,
## like 55, then n is most likely incorrect because
## the next number that is 0 MOD(primes[n-1]) is primes[n-1]*primes[n-2]

n = 1           ## n is 1, since primes[n-1] == 3
## primes[n-1] is 2
limit  = 1000   ## The limit of numbers to test if prime

for x in range (5,limit + 1,2):  ## For all odd numbers x to limit

if not t(x,n):          ## if x % primes[n-1] == 0, then x is composite.
n += 1              ## Increment n, because primes[n-1]**2 was
continue            ## encountered, then continue

if not k(x,n):          ## if x % primes[0 -> n-1] == 0, then
continue            ## x is composite, continue

if not e(x,n):          ## if (x+-1) % 3 == 0, then
continue            ## x is composite

primes.append(x)        ## x is prime so append it to the prime list

print ("Number of primes used to generate "+str(len(primes))+": "+str(n-1))
print ("Largest prime used: "+str(primes[n-1]))


Yields primes for any limit, but the code is not optimized so don't expect sieve speed, since it is actually testing each number, not sieveing them.

Although slow compared to good sieves, it ran and finished in < 3 seconds with $limit = 10^6$. This resulted in 78497 primes, generated from $P_1,...,P_n$ where $n = 167 = \pi(\sqrt{limit})-1$, which is the number of primes under $10^6$-1, accounting for 2.

So my question is:

Is this well known and understood from before? In that case, where might I find more information on the topic?

I ask because after weeks of research I have not found a function, except sieves, which doesn't exactly check numbers for primality, that needs no more than $\pi(\sqrt x)$ primes to generate a series of primes.

If I've missed an important point that makes this common knowledge, please tell me so that I may fell the sting of toiling for nothing instead of reading...

Kindest regards,

John

-

You've re-discovered trial division.

-
You really don't see the point... – JohnWO Apr 19 '13 at 1:09
@JohnWO: I understand the algorithm perfectly well. $k_{\pi(\sqrt x)}(x)$ is precisely trial division by the primes up to $\sqrt x$. This is a useful algorithm for testing small numbers for primality, don't feel bad that you weren't the first to find it. – Charles Apr 19 '13 at 1:54
I'm sorry if you think I implied that you didn't. My point was to defog the relationship between the primes, prime powers, and the product of primes. – JohnWO Apr 19 '13 at 2:12

You have taken the first step to finding Meissel's prime counting formula.

Take a look at this: http://en.wikipedia.org/wiki/Prime-counting_function

-
I can see no use of Bertrand's postulate in your algorithm, and the fact that all primes after 3 are one more or less than a multiple of 3 is most definitely not a result of Euler but a remarkably obvious fact stemming from the fact that they aren't divisible by 3, and there's nothing else for them to be. – Sharkos Apr 19 '13 at 1:35
I see the connection you're referencing and it makes sense, thanks. Regarding Bertrand's postulate, it was the trail of though, as described in the question. – JohnWO Apr 19 '13 at 1:52
It's rather discourteous to delete comments when somebody else already responded without acknowledging this. – Sharkos Apr 19 '13 at 1:54

This is the completely standard simplest way to test primality using a list of primes. I suspect it doesn't have a name, since it's simply the only thing to do. The logic is as follows; I think you've overcomplicated it by treating lots of cases separately.

• If a number $n$ is not prime, it has at least two prime factors $p,q$. Since $pq\le n$ at least one of them must be $\le \sqrt n$ or they would multiply to something bigger than $n$.
• Therefore, a primality test working only by checking divisibility by possible factors should check all primes within $2, \cdots, \sqrt n$

For an example of the algorithm you discuss, see the end of the first paragraph of the Wikipedia article http://en.m.wikipedia.org/wiki/Trial_division

-
I am not checking all primes from $2,..,\sqrt n$ but for $P_1,...,P_n$ where $n$ is $\pi (\sqrt{limit})$. – JohnWO Apr 19 '13 at 1:24
But $m=\pi(\sqrt x)$ tells you how many primes are at most $\sqrt x$ so $P_m$ is the last prime smaller than $\sqrt x$ by definition, so this is exactly the range $2,,\cdots,sqrt x$ – Sharkos Apr 19 '13 at 1:28
That is not the same. If I where to test numbers $3 -> n$ it would be considerably slower as it does not consider for powers. I suggest you reread if you miss my point. My code does not contain it because it was just a quick fix I put together, but it's in the comments. It is beside the point anyway, as I wanted input on what the formula implies in terms of the relationship between the numbers and if there was any information on that subject. – JohnWO Apr 19 '13 at 1:46
I didn't say all numbers in that range, I said all primes. I have read your Python code because your language is unclear, and it is clear than your k(x,n) function does exactly what I have described. – Sharkos Apr 19 '13 at 1:50
I know that you said prime numbers, and that was what "numbers" was referencing in that context; "Comments" was referencing the comments in my code. Sorry the unclear language. – JohnWO Apr 19 '13 at 1:59

Would you be able to modify your code to give your function a modifiable starting point?

What I mean by that is currently, in your code, N starts at 3 and goes up 5, 7, 9...etc., with P also starting at 3.

Could it be modified so that N started at say, 1000001 (first odd number past 1mil), and P started at 1000003 (first prime past 1mil)?

-
Short answer: Yes – JohnWO Apr 19 '13 at 1:39