09-13-2017, 10:16 AM
Post: #1(Print Post)
A “computer programming forum”wouldn’t be complete without a topic discussing prime numbers and / or prime number theories. Since I couldn’t find such discussion here, I thought I would mention a thing or two about it.
What do prime numbers or prime number theories have to dowith computer programming?
If you are new to computerprogramming then this topic is completely relevant because aside from the infamous “Hello World” program, a program to find and print out the first hundred primes serves as a perfect example of what a computer program is.
Note: In this example there are obvious optimizations to be made and this is where the discussion begins.
Code Snippet: [Select]
Learning how to program includesthe idea of an expected result. If you write a program to list prime numbers and the list includes composites then you know there’s something wrong with your program as the result are unexpected. Reviewing your program in an effort to correct it so that it will produce the expected results is a process commonly referred to as “de-bugging”. If you are designing or testing computer hardware and the list includes composites, then you may have a problem with your ram and / or cpu. I often tell people this is the case at most schools to include MIT. In fact it was MIT that got me interested in prime numbers in the first place. No, I never went to school. I am self taught which is not saying much, because I only know enough to realize I have much to learn.
If you are an experiencedprogrammer then prime number theory could be you next big interest. Prime number theory, the investigation of various techniques to find prime numbers and / or probable primes (numbers that are likely to be prime) can involve elaborate programs, testing your skills as a programmer. While small primes are gems in their own right, the larger primes are like diamonds to me, rare and hard to find, yet infinite in number. My investigation of prime numbers has been one of my greatest adventures aside from sailing the seven seas. In my investigation I wrote several programs testing various algorithms. I used FB of course, along with the GMP library to handle large numbers as I was working towards finding a billion digit prime. And yes, that’s a billion digits (1 x 10 to the 1 billionth power), not 10 to 12 digits. And no, I’m nowhere closer to finding one now then I was several years ago.
At the time I did not give too muchthought to existing algorithms designed by others because I wanted to develop my own original algorithm. I wanted to attempt to think out side of the box and see if I could figure something out that hasn’t been thought of before. Note, I didn’t and still don’t consider myself bright enough to be able to understand / comprehend most intense theories cuz I ain’t so good at math ya know.
Out of all my investigation, mybest work was based on what I called “Patterns in Primorials” Once I figured this to be “The One Technique”, naturally I looked for specific related published works of which I couldn’t find any at that time. It wasn’t until a few years later that I found a fellow at some university discussing what he coined “Constellations in Primorials” or something like that. I believe I figured it out on my own, uninfluenced, but not necessarily before anyone else. While the patterns are pretty cool in themselves, they also serve to be quite useful. This is to say that if you’re going to build a house, a good hammer will make the job easier.
What is a primorial?
Similar to factorial (1*2*3*4), primorial is the product of primes(2*3*5*7*11).
So what are “Patterns in Primorials” and how and why are thepatterns useful?
Similar to a sieve, the pattersreduce the number of numbers to test for primality in a given range. For example if you wanted to find primes in the range 1 million to 2 million then you could list the million numbers and begin the process of elimination which would be to first exclude those that are multiples of 2 (ie. All the even numbers). With half of the numbers remaining (ie. All the odd numbers) you would then exclude those that are multiples of 3, but before you do that you might as well exclude those that are multiples of 5 first because they all end in 5 which are easy to identify. This will leave you a list of numbers that will only end with 1,3,7 or 9. But a sieve would eliminate multiples of 2 then 3 then 5 then 7 then 11 and not 4,6,8 or 9 as these would only be multiples of 2 and 3 anyway which are already excluded.
A“primorial pattern” is a sequence of numbers that repeat. The numbers in the pattern are the gaps between primes and composites that are not multiples of those primes within the primorial.
The first primorial is called P1 which is equal to 2.
The second primorial is called P2 (2*3)
The third primorial is called P3 (2*3*5)
P1p a pattern of repeating (2)’s
P2p a pattern of repeating (2,4)’s
P3p a pattern of repeating (4,2,4,2,6,2,6)’s
Notice the sum of the gaps is equal to the primorial.
Using P1p:Starting with the next prime number 3 add (2)
produces5,7,9,11,13,15 all of which are not multiples of 2
Using P2p:Starting with the next prime number 5 add (2,4)
5 + 2+4 +2+4 + 2+4 + 2+4
produces7,11,13,17,19,23,25,29 all of which are not multiples of 2 or 3
Using P3p:Starting with the next prime number 7 add (4,2,4,2,6,2,6)
4+2+4+2+6+2+6 + 4+2+4+2+6+2+6 + 4+2+4+2+6+2+6
produces11,13,etc… all of which are not multiples of 2,3 or 5
P1pproduced a list of numbers that are all primes up to 3^2
P2pproduced a list of numbers that are all primes up to 5^2
P3pproduced a list of numbers that are all primes up to 7^2
By using the patterns to produce a list of numbers to checkfor primality, effectively reduces the number of numbers to check for primality. The Percentage of Remaining numbers to check in a given range are approximately:
P5p=20.6% Example:out of 100 trillion, P5p lists 20.6 trillion numbers.
P6p=18.9% Meaningit is not necessary to investigate more then 80 trillion
P7p=17.8% ofthem as they are simply multiples of 2 or 3 or 5 or 7 or 11.
P8p=16.9% Ofthe 20.6 trillion number there will be many composites.
P9p=16.2% Thecomposites will be multiples of 13, 17, 19, 23, etc… up to
P10p=15.9% thesquare root of the number you are checking for primality.
As you can see P1p provides the most significant savingswhile P2p to P12p provide additional savings to an increasingly lesser degree. None the less, a savings in time and computer cycles and this is why I call the smaller primes “GEMS”
Next, how to create the patterns. P3p, starting at 7 listnumbers that are not multiples of 2,3 or 5
The gap between 7 and 11 is: 4
The gap between 11 and 13 is: 2
The gap between 13 and 17 is: 4
The gap between 17 and 19 is: 2
to be continued on next post if there is an interest in this topic...
The following 2 users Like owen's post:
easylangs, Waltersmind (Admin)
09-13-2017, 12:48 PM
Post: #2(Print Post)
RE: Prime numbers
I think this conversation shouldn't have been posted in the socializing section. Bplus found a better section in this forum to continue the discussion. Please go to:
User(s) browsing this thread: 1 Guest(s)