- Ok.... working on what stmaddox found and what i found out myself its possible to determine in an easy way without sieving if a number is prime or not.

If (((LastPTot * n)*(LastPSize*(LastP-1)) /n) mod n)>0 then the n is prime.

But let me explain:

The number 3 has a pattern-size of 1 and a pattern-total of 6.

The number 5 has a pattern-size of 2 and a pattern-total of 30

The number 7 has a pat.size of 8 and a pat-total of 210

etc.. see previous posts by stmaddox and me about how to calculate pattern size and pattern-total. (or see VB code below)

What this new formula does is basicly start at number 3 knowing thats a prime and then trying the next number.

the next number has a pattern size of (last pattern size * (last prime-1))

the next number has a pattern total of (last pattern total * next number).

In case of 4 that is a pattern total of 24 and a pattern size of 2.

we then do 24*2=48, 48/4= 12, 12/4 = 3.0 (no remainder => thus not prime)

then we try 5. pattern total of 30, pattern size of 2

we do 30*2= 60. 60/5= 12 , 12/5 =2.x (remainder => thus prime)

then we try 6. pattern total of 180, pattern size of 8

we do 180*6=1440. 1440/6=240, 240/6=40.0 (no remainder, not prime)

then we try 7. pattern total of 210, patsize of 8

210*8=1680. 1680/7= 240. 240/7=34.x (remainder.. thus prime)

It works all the way the first 100 primes or so. Though of course the numbers get awfully big.

prime: 3, time needed: 00:00:00

prime: 5, time needed: 00:00:00

prime: 7, time needed: 00:00:00

prime: 11, time needed: 00:00:00

prime: 13, time needed: 00:00:00

prime: 17, time needed: 00:00:00.0156250

prime: 19, time needed: 00:00:00

prime: 23, time needed: 00:00:00.0312500

prime: 29, time needed: 00:00:00.0312500

prime: 31, time needed: 00:00:00.0156250

prime: 37, time needed: 00:00:00.0937500

prime: 41, time needed: 00:00:00.0625000

prime: 43, time needed: 00:00:00.0468750

prime: 47, time needed: 00:00:00.0937500

prime: 53, time needed: 00:00:00.1875000

prime: 59, time needed: 00:00:00.2343750

prime: 61, time needed: 00:00:00.0937500

prime: 67, time needed: 00:00:00.3281250

prime: 71, time needed: 00:00:00.2500000

prime: 73, time needed: 00:00:00.1562500

prime: 79, time needed: 00:00:00.4531250

prime: 83, time needed: 00:00:00.3906250

prime: 89, time needed: 00:00:00.7031250

prime: 97, time needed: 00:00:01.0312500

prime: 101, time needed: 00:00:00.5781250

prime: 103, time needed: 00:00:00.2968750

prime: 107, time needed: 00:00:00.6406250

prime: 109, time needed: 00:00:00.3437500

prime: 113, time needed: 00:00:00.7656250

prime: 127, time needed: 00:00:02.9687500

prime: 131, time needed: 00:00:00.9375000

etc...

basicly in formula shape the prime check is as follows:

LastPtot = Last Pattern Total

LastPSize = Last Pattern Size

LastP = Last Prime (and pattern)

n = current number being tested

If (((LastPTot * n)*(LastPSize*(LastP-1)) /n) mod n)>0 then the n is prime.

here is the code i used to test the formula:

s = ""

p = "3"

curpatsize = "1"

curtot = "6"

tim1 = Now

TextBox1.Text = ""

For i = 1 To 99

tsp = Now.Subtract(tim1)

TextBox1.Text += "prime: " + p + ", time needed: " + tsp.ToString() + vbCrLf

tim1 = Now

Application.DoEvents()

lasttot = curtot

lastp = p

curpatsize = Module1.IntMultiply(curpatsize, IntSubtract(lastp, 1))

ok = 0

Do

p = IntAddition(p, 1)

curtot = IntMultiply(lasttot, p)

test = IntDivide(IntMultiply(curtot, curpatsize), p)

If InStr(test, "r0") > 0 Then test = Mid$(test, 1, Len(test) - 2)

test = IntDivide(test, p)

If InStr(test, "r0") = 0 Then ok = 1

Loop While ok = 0

Next i

bottom line: seems to work as a charm.

kind regards,

Victor Reijkersz - Peter Thanks for your comment. I admit I am technically wrong in that

since 2 is the only even prime, I usually skirt around that special case by

always prefacing my remarks with ³in the set of odd numbers only,² which

I neglected to do, much to my regret since I am getting flak from around

the world. I do that because prime 2 always obfuscates the issue, as it is

doing in this very instance.

So, to correct, the locus for ALL primes except 2 is 6n+1 or 6n-1,

which of course is not to say that all 6n+-1 are prime. Another way to

define 6n+-1 is 3n+2+4, where both are one and the same. The distinction I

am making is that 3n+2+4 is descriptive (to me) of all non-multiples >3 to

infinty, while 6n+-1, makes it appear that there is something profound and

revealing about this infinite set when in fact it has been staring us in the

face from the very outset as 3n+2+4. If you look at in this light, it will

all come together. Thus, the search for a pattern in 6n+1-1 is all in vain.

A list of prime numbers (go primes.utm.edu ) has provided this information

forever. Thanks for your interest. Regards. Marty

From: Peter Kosinar <goober@...>

Date: Wed, 4 Aug 2010 00:08:38 +0200 (CEST)

To: Matteo Mattsteel Vitturi <mattsteel@...>

Cc: <primenumbers@yahoogroups.com>

Subject: RE: [PrimeNumbers] Re: Easy formula for next prime... cant make it

any easier.

Matteo,

> > Wrong. 6n+/-1 represents all -odd- integers not divisible by 3 and,

An expression (e.g. 2n+1) represents a set S if every number from set S

> > consequently, it represents all primes with the exception of 2 and 3. This

> > is where it differs from your form 3n+2+4, which guarantees the "not

> > divisible by 3" condition, but not the "is odd" one.

>

> I don't thing i understand very well what you're saying about 6n+/-1 that

> should represent all primes.

can be written in the form prescribed by the expression. It's not

necessary for all the numbers of that form to belong to set S.

For example, the form 2n+1 represents all odd integers. Thus, it can also

be used to represent each and every odd prime, odd square or odd perfect

number -- since all of these are just subsets of the set of odd numbers.

Peter

[Non-text portions of this message have been removed]