You are not logged in or registered. Please login or register to use the full functionality of this board...
SIGN IN Join Our Community For FREE


Prime numbers
09-13-2017, 10:16 AM
Post: #1
 (Print Post)
Shocked Prime numbers
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]
Dim As Integer n,i,c,p
Dim As BOOLEAN skip
n=100
c=0
c=c+1
p=2
Print c,p
c=c+1
p=3
Print c,p
p=4
Do While c<n
    skip=FALSE
    For i = 2 To p - 1
        If p Mod i = 0 Then ' p is a composite
            p=p+1
            skip=TRUE
            Exit For
        EndIf
    Next
    If skip=FALSE Then ' p is prime
        c=c+1
        Print c,p
        p=p+1
    EndIf
Loop
Sleep
End

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?
 
Why:
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.
 
What:
            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.
P1p=2
P2p=6
P3p=30
 
How:
            Using P1p:Starting with the next prime number 3 add (2)
            3+2+2+2+2+2+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)
            7  + 
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
 
            NOTICE:
            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:
P1p=50%
P2p=33.2%
P3p=26.5%
P4p=22.7%
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.
P11p=15.7%
P12p=15.6%
 
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
 
7,11,13,17,19,23,29,31,37,41,
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...
Find all posts by this user
Like Post
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:
http://www.thejoyfulprogrammer.com/qb64/...hp?tid=994
Find all posts by this user
Like Post



Forum Jump:


User(s) browsing this thread: 1 Guest(s)




QB64 Member Project - ARB Checkers
QB64 Member Project - Score 4
QB64 Member Project - Rotating Background
QB64 Member Project - Exit
QB64 Member Project - Martin Fractals version two
QB64 Member Project - Kings Valley verion one
QB64 Member Project - Quarto
QB64 Member Project - Connect Four
QB64 Member Project - Othello
QB64 Member Project - Inside Moves
QB64 Member Project - Qubic
QB64 Member Project - Pivet version one
QB64 Member Project - Spiro Roses
QB64 Member Project - Foursight
QB64 Member Project - Amazon
QB64 Member Project - Swirl
QB64 Member Project - Dreamy Clock
QB64 Member Project - Kobolts Monopoly
QB64 Member Project - Pivot version two
QB64 Member Project - Line Thickness
QB64 Member Project - Sabotage
QB64 Member Project - Color Triangles
QB64 Member Project - Red Scrolling LED Sign
QB64 Member Project - Full Color LED Sign
QB64 Member Project - Basic Dithering
QB64 Member Project - Overboard
QB64 Member Project - Touche
QB64 Member Project - Rubix's Magic
QB64 Member Project - Blokus
QB64 Member Project - Isolation
QB64 Member Project - Martin Fractals version three
QB64 Member Project - Algeria Weather
QB64 Member Project - Kings Vallery version two
QB64 Member Project - Color Rotating Text
QB64 Member Project - Martin Fractals version four
QB64 Member Project - Input
QB64 Member Project - Spinning Color Wheel
QB64 Member Project - Bowditch curve
QB64 Member Project - OpenGL Triangles
QB64 Member Project - Dakapo
QB64 Member Project - Domain
QB64 Member Project - RGB Color Wheel
QB64 Member Project - MAPTRIANGLE
QB64 Member Project - 9 Board
QB64 Member Project - Kings Court
QB64 Member Project - Point Blank
QB64 Member Project - Splatter
QB64 Member Project - STxAxTIC 3D World
QB64 Member Project - Martin Fractals version one