Prime Numbers

Homepage Forums Small Talk Prime Numbers

This topic contains 6 replies, has 5 voices, and was last updated by  Unseen 6 months, 3 weeks ago.

Viewing 7 posts - 1 through 7 (of 7 total)
  • Author
    Posts
  • #26057

    PopeBeanie
    Moderator

    This is purely a geeky post, with no relevance to atheism. Except at the very bottom of this post, which I’m giving y’all permission to skip down to.

    I’m neither a mathematician nor a reader of mathematical theory, but I like thinking about prime numbers. Geek readers can just skim through most of this top of this post. (In my case, this is more an exercise of learning how to explain a concept that, although will go over some people’s heads or bore most people, is a way for me to explain fact, aided by some scientific method. I.e. for me, this is and exercise on how to write real news vs fake news.)

    Calculating and printing out a long list of primes is often the first program I write when learning or playing with a new programming language. All that’s required is 1) An empty table or list to be filled with known prime numbers; 2) Given a potentially infinitely long list of numbers to test, a way to determine which of them are prime; 3) A way to add each newly discovered prime number to the growing list of primes.

    Math purists might say I’m cheating by not starting my calculations by first testing the number two, or three, but for programming ease, I first load the table with two prime numbers, three, and five. Then I start testing odd numbers, because obviously, even numbers are divisible by two and so can never be prime.

    So the first numbers to test are seven, nine, eleven, thirteen, fifteen, and so on up to as high as speed and memory allow, or until someone gets tired of watching the screen fill and scroll with increasingly large prime numbers… starting of course with the number seven.


    Producing the source of test numbers Just as every second number (two, four, six…) don’t need to be tested, so also every third, fourth, or fifth number can be eliminated as a candidate, but this method is not feasible. It’s most practical, programmatically to test every odd number for primeness. We can test the number seven by dividing it by the first prime in the list three, and since there is a remainder, we continue by testing again by dividing seven by five, the second prime in the list. Since we’ve tested seven by dividing it by every prime in the list (three and five), we can now say that seven is prime, and add it to the list of known primes (three and five).

    The next number to test is nine. Starting the test loop over, we start by dividing nine by three and learn that there is NO remainder. Therefor, nine is NOT prime. Yeah, the first non-prime! We can discard it and go on to test eleven.

    Notice the pattern of three odd numbers in a row that are prime: three, five, and seven. From now on, since every third odd number is divisible by three, we know that, by definition, the numbers nine, twelve, fifteen, eighteen and so on up the infinite list of odd numbers by three can never be found to be prime. And yet, for the sake of necessary simplicity in programming algorithms, we can’t afford to program a way to ignore every third odd number, nor every fifth number, or seventh number, and so on, so we must settle on just testing every odd number, forever.

    Increasing test efficiency On a computer, the unnecessary (third, fifth, and so on) calculations don’t cost us much (compared to the cost of programming how to ignore them), so we let it be. However, there is another easy way to reduce the necessary number of calculations, e.g. by not test dividing every odd number by every known prime in the list. E.g when testing the number eleven, we can stop testing at eleven divided by three, because we know that eleven divided by five is unnecessary. We know this because any number divisible by five must also be divisible by another prime number in the table, like three.

    I.e., the next largest non-prime number has to be three times five, or fifteen. Since both eleven and thirteen are less than fifteen, we can say they are prime. This might be harder even for geeks to keep in mind, but suffice to say, there is an easy calculation that can be added to every test number that determines the highest test divisor we must try in our growing list of primes. The highest number we must try as a divisor for testing the number eleven, is the square root of eleven.

    This square-root method of saving calculation efficiency is somewhat realizable at an intuitive level, especially when we’re testing higher numbers. E.g. assume we’ve built our table of known primes to a dozen or so: 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41. It’s pretty obvious we needn’t test the number 41 for primeness by seeing how it divides by 37! It’s less intuitively obvious, but true, that we needn’t test 41 with any divisor larger than the square root of 41 (i.e. 6 and a fraction). Se we know trying to divide by 41 by 7 or larger is unnecessary.  That’s a significant savings in calculations required, because it saves us from test dividing by all the ten prime numbers larger than 5.

    When we get into testing numbers way up into the dozens of digits, limiting test divisors to the square root of the test number saves calculation times on a logarithmic scale. I don’t (yet) know of any other significant way to enhance the efficiency of our prime-seeking algorithm(s).


    Now, onto “balphegor’s prime“! Take note, the following, amazing, perhaps even evil prime number. It’s extremely long, but easy to remember because of its thirteen zeros on either side of “666”:

    1000000000000066600000000000001

    If nothing else after skimming or ignoring 99% of my post, I hope the Godless here can appreciate that number!

    #26067

    In my case, this is more an exercise of learning how to explain a concept…..

    Here is a fine technique to help. I use it while running on the dreadmill to see how much about a concept I know.

    Yes, I read all of the post 🙂

     

    #26068

    _Robert_
    Participant

    so we must settle on just testing every odd number, forever.

     

    Nice algorithm however I think the real challenge here will be memory management and hardware failure…I have yet to see a compiler warning concerning semiconductors turning to dust.

    #26069

    Simon Paynton
    Participant

    Do you use the Sieve of Eratosthenes ?

     

    #26070

    so we must settle on just testing every odd number, forever.

    When it comes to infinity, there are just as many odd numbers as there are both even and odd numbers combined!!

    #26073

    PopeBeanie
    Moderator

    Doh! I see typos, at least, and some missing clarity. I’ll adjust the post after seeing the Feynman link.

    @simonpaynton Sieve of Eratosthenes is what I was trying to explain that costs too much programming-wise and in the computer resources it requires. And the more efficient sieve algorithms mentioned in that same wikipedia article make my head hurt! The last one, Euler’s Sieve looks most promising (for my head, anyway), and I might try that someday (thank you).

    I’ve been interested in what this exercise would look like in hexadecimal math rather than decimal. I only just now wondered if using hexadecimal might be a much more computationally efficient way to calculate for primes. Decimal math exists only to impress animals with ten fingers!

    #26099

    Unseen
    Participant

    Now, onto “balphegor’s prime“! Take note, the following, amazing, perhaps even evil prime number. It’s extremely long, but easy to remember because of its thirteen zeros on either side of “666”: 1000000000000066600000000000001

    That number is only significant if you take Christianity seriously. Otherwise, it just looks cool.

Viewing 7 posts - 1 through 7 (of 7 total)

You must be logged in to reply to this topic.