Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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]

primes = [3]    ## Start with the first odd prime
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

share|improve this question

4 Answers 4

up vote 2 down vote accepted

You've re-discovered trial division.

share|improve this answer
    
You really don't see the point... –  JohnWO Apr 19 '13 at 1:09
2  
@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

share|improve this answer
2  
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

share|improve this answer
    
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
1  
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)?

share|improve this answer
    
Short answer: Yes –  JohnWO Apr 19 '13 at 1:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.