heyy folks,

this is sudden yeah and i'll explain why and how. Only yesterday I got a strange wall post on google plus from a friend of mine. It said "Extended Wilson Theorem". Naturally i was curious and I started reading that link [from his blog] and the rest of the articles about prime numbers.

http://mathematicswithvidura.blogspot.com/

( BIG THANK TO Vidura for putting this into ma attension :) )

Then I found this article which says about the 6m ± 1 theory. It says that

And then I was thinking along the line of increasing the efficiency of prime number generation using this, since I always get stuck in trying to generate huge lists of prime numbers. So I generated a few 6m ± 1 numbers and observed its properties.

m 6m-1 6m+1

1 5 7

2 11 13

3 17 19

4 23 25

.

.

.

16 95 97

.

.

.

40 239 241

see the red ones? those the NON primes when applied to that number sequence,

so here are those numbers in a list, and a factor of them are listed, and GUESS WHAT?

25 -> 5

35 -> 5

49 -> 7

55 -> 5

65 -> 5

77 -> 7

.

.

.

125 -> 5

133 -> 7

ALL of these numbers have a PRIME NUMBER as one of it's factors other than itself and one :D

Hell yeah, so i formulated this hypothesis which I cannot prove mathematically at the moment.

NOTE: I dont know whether this was proven beforehand, but i only found this today, so my apologies for lack of knowledge whether this is already proven or not

So need not to say that using this we can speed up the prime generation pretty pretty fast

NOTE:

I only got to know about Knut's algorithm later, as it seems it clearly says that

which is as same as mine, so this ISNT a new algo, it's same as Knuts, but still worth looking on it

EDIT:

On a later notice, this is actally 3x faster than Knuth's due to the use of

Prime Generation Algorithms compared

1) Naiive

Lets look at the textbook way of generatin primes

Now considering the running time of this algorithm,

if the upper limit is N

this would take approximately O(N^2) time complexity considering all factors

2) Using the above hypothesis

so, given this we can actually bring down the time complexity to

O(N*sqrt(N)/6)

~~but since sqrt(N) <<<<< N for very large values AND no of primes below a very large number is considerably low,~~

rephrasing:

lets consider finding whether there's a factor for a number of range 10^8

the normal algorithm will loop over sqrt(N) times that's 10^4 times

but since we are looping only over our previously collected collection of primes

and there's only 1229 primes below 10^4, we loop only 1229 time

see the difference? :)

but since sqrt(N) <<<<< N for very large values AND no of primes below a very large number is considerably low,

we can say it's O(N) for very large numbers

of course i cant prove this yet, but i'm running the codes at the moment, so as sooon as i get positive [or negative] results i'll update it here :)

this is sudden yeah and i'll explain why and how. Only yesterday I got a strange wall post on google plus from a friend of mine. It said "Extended Wilson Theorem". Naturally i was curious and I started reading that link [from his blog] and the rest of the articles about prime numbers.

http://mathematicswithvidura.blogspot.com/

( BIG THANK TO Vidura for putting this into ma attension :) )

Then I found this article which says about the 6m ± 1 theory. It says that

Every prime number except 2 and 3 can be expressed in the form 6m ± 1BUT not ALL numbers that can be expressed as above are primes.

And then I was thinking along the line of increasing the efficiency of prime number generation using this, since I always get stuck in trying to generate huge lists of prime numbers. So I generated a few 6m ± 1 numbers and observed its properties.

m 6m-1 6m+1

1 5 7

2 11 13

3 17 19

4 23 25

.

.

.

16 95 97

.

.

.

40 239 241

see the red ones? those the NON primes when applied to that number sequence,

so here are those numbers in a list, and a factor of them are listed, and GUESS WHAT?

25 -> 5

35 -> 5

49 -> 7

55 -> 5

65 -> 5

77 -> 7

.

.

.

125 -> 5

133 -> 7

ALL of these numbers have a PRIME NUMBER as one of it's factors other than itself and one :D

Hell yeah, so i formulated this hypothesis which I cannot prove mathematically at the moment.

NOTE: I dont know whether this was proven beforehand, but i only found this today, so my apologies for lack of knowledge whether this is already proven or not

When m takes different values of the expression, E = 6m ± 1 , E gives prime numbers or composite numbers that have prime numbers as one or more of its factors

So need not to say that using this we can speed up the prime generation pretty pretty fast

NOTE:

I only got to know about Knut's algorithm later, as it seems it clearly says that

if n is prime, it's not divisible by any prime number upto squareroot(n)

which is as same as mine, so this ISNT a new algo, it's same as Knuts, but still worth looking on it

EDIT:

On a later notice, this is actally 3x faster than Knuth's due to the use of

*6m ± 1*rulePrime Generation Algorithms compared

1) Naiive

Lets look at the textbook way of generatin primes

- lim -> the upper limit upto which the primes whould be generatedS -> set of all prime numbers foundloop i = 1 to lim
- if i == 1 : continue
- if i==2 or i==3
- S.add(i)
- continue;
- isPrime = true
- loop j = 2 to sqrt(i)
- if j%i == 0
- isPrime = false
- break;
- end loop
- if isPrime : S.add(i)
- end loop

Now considering the running time of this algorithm,

if the upper limit is N

this would take approximately O(N^2) time complexity considering all factors

2) Using the above hypothesis

- lim -> the upper limit upto which the primes whould be generated
- S -> set of all prime numbers found
- if lim > 2 : S.add(2)
- if lim > 3 : S.add(3)
- loop i = 1 to ...
- //now we dont check ALL numbers, just the ones according to 6m +/- 1 theory
- n -> 6*m - 1
- //if the value is larger than the limit we stop
- if n > lim : break
- if isPrime(n) : S.add(n)
- n -> n+2
- if isPrime(n) : S.add(n)
- end loop
- function isPrime(n)
- //we will check whether a prime from our generated list is a factor of n
- sq = sqrt(n)
- loop each element i in S:
- //we only need to check till i<=sq
- if i > sq : break
- if n%i == 0
- return false
- end loop
- return true
- end function

so, given this we can actually bring down the time complexity to

O(N*sqrt(N)/6)

rephrasing:

lets consider finding whether there's a factor for a number of range 10^8

the normal algorithm will loop over sqrt(N) times that's 10^4 times

but since we are looping only over our previously collected collection of primes

and there's only 1229 primes below 10^4, we loop only 1229 time

see the difference? :)

but since sqrt(N) <<<<< N for very large values AND no of primes below a very large number is considerably low,

we can say it's O(N) for very large numbers

of course i cant prove this yet, but i'm running the codes at the moment, so as sooon as i get positive [or negative] results i'll update it here :)

Superb that you yourself figured out the connection between 6m±1 and prime numbers and used it to optimize the code :D

ReplyDeleteFound it in the official explanation of Project Euler Q #7. Thumbs up!