Archive for » September, 2016 «

Playing with a Computational Model of the Sieve of Eratosthenese to find Prime Numbers

Sieve of Eratosthenese

Sieve of Eratosthenese

I have just read about the Sieve of Eratosthenese from this Scientific American article from Facebook and was inspired to give it a try to see how it works, info  especially because the math and programming seemed simple enough. I worked with a dataset of 1-1000. I also tried up to 100, information pills 000. My browser to freaks out with a dataset larger than that.

I have also tried to setup my process so there would be no numbers that would be worked on more than once for each round of multiple removal. I am calling this the Square Prime Reduction Method (SPRM).

In order to do so, anorexia I would look for a pattern that would identify the remaining numbers. The farther along I worked the harder it became. Below I will list my notes, the pattern used for cumulative reduction, and the amount of dataset reduction, and the dataset size required for pattern recognition. This is the result of about a day of work.

See my notes here and the results of my scripting work here.

Square Prime Reduction Method (SPRM)

Using this cumulative multiple removal method it seems that the beginning for each reduction round is the square of the next prime number (i.e. for 2 it is 4; for 3 it is 9; for 5 it is 25; etc). For each reduction round I:

  1. start at the square of the next prime
  2. run a clean script routine as if I were removing all of the multiples which showed zeros for the multiples already removed
  3. find the pattern for its remaining multiples
  4. code to remove the remaining multiples

With each successfully processed prime, we are able to further reduce the pool of unprocessed numbers. To reveal all primes under 1000 I would have to follow this process up to the square of the prime of 31 which is 961.

Prime Multiple Reduction (PMR)

I started with a dataset of 1-1000 to see if I could get it to work. Starting with 2 I processed the removal or the multiples of each prime number as I encountered them and then I moved up the list. It also seemed to scale fine for 10,000 and 100,000 and my observations and tenuous rules seem to work as the dataset scales.

Multiples of 2

First, in any given number set we can get rid of half of the numbers because they are even, meaning evenly divisible by 2, so that speeds up things considerably.

Pattern Complexity: Obvious

Pattern: Ummm…well… Every other number! =)

Dataset Reduction: This resulted in a reducing the possible number pool by 49.9% (499).

Multiples of 3

Second, we can get rid of every third number because they will evenly divisible by 3, although I will have to compensate for the missing even numbers.

Pattern Complexity: Obvious – 1 extra step

Pattern: In writing the code for this I noticed the following pattern after removing the even numbers: start with 3 and then add 6 and remove that

Dataset Reduction: This resulted in a reducing the possible number pool by about 16.6% (166).

Multiples of 5

Then, removing multiples of 5 becomes slightly more tricky since we have removed numbers divisible by prime numbers 2 and 3 creating quite a few holes in its multiple list.

Pattern Complexity: Easy – 2 extra steps

Pattern: The pattern for multiples of 5: start at 5, increment by 30, remove that number and then remove the number @ -10.

Dataset Reduction: This resulted in a reducing the possible number pool by 6.6% (66). Not a whole lot, but we are getting closer.

Multiples of 7

Removing Multiples of 7 was much more difficult since we have removed a broad swath of numbers ~ 72.7% of the number pool so there were a lot of holes. Stay on Target!

Pattern Complexity: Moderate – 8 extra steps

Pattern: To find the pattern for multiples of 7 I copied the result of a straight removal by 7 and put it into a text file and looked for how the number of zeros (already removed multiples) stacked up between the number of those numbers remaining which were divisible by 7. There was a visual pattern and from there I had to figure it out. I found a repeating pattern of previously removed multiples: 3/1/3/1/3/5/1/5. Turning that into a computational model was fun!

My second idea, which was used, was the opposite sort of implementation than what I used for the multiples of 5. With 5 I went up and then back. With 7 seven I programmatically worked my way forward to the next iteration.

Dataset Reduction: This resulted in a reducing the possible number pool by 3.2% (32).

Multiples of 11

Because I needed to jump the max number out from 1,000 to 10,000 in order to try to see a pattern, attempting to remove multiples of 11 was too difficult to fully pursue.

Pattern Complexity: Difficult – with the numbers and observations below I expect the pattern would be near 32 and 512 extra steps.

Pattern: I was able to see a vague pattern in about 5,000 items, but was not going to pursue that due to lack of time and quality pattern recognition and visual analysis tools.

Dataset Reduction: ?? – given the numbers which I will display below I expect a reduction of about 1.98%

Observations

Larger Dataset Needed for Pattern Recognition

To compensate for the plethora of removed numbers as you go further and further through the primes it seems like we need an increasingly larger data set for analysis in order to see the pattern.

  • for 3: I do not remember exactly, but I expect that the pattern was obvious near 20 items.
  • for 5: I do not remember exactly, but I expect that the pattern was obvious near 75 items.
  • for 7: about 500 to recognize the pattern
  • for 11: I bumped it up to 10,000 and a pattern of sort was seen near 5,000

Possible rule: To find the pattern for each successive prime we will need a dataset 10 times larger than the previous one. With this, I am not really taking into account the first two since the pattern is super simple to find because there is minimal processing and with a number reduction which is very easy to compensate for.

Or perhaps the dataset has to do with the number of multiples removed and the remaining number of numbers remaining from the prime’s square value.

That is supremely annoying. I would need better tools to play with larger numbers. =O

Increasing Complexity in Pattern

As each square is processed it will become more and more difficult to process the pattern to prevent processing already removed numbers. As mentioned above the dataset requirements grow in order for us to see the pattern, but also so does the work required to process the pattern to remove subsequent multiples. This is also biased by my limitations, biases, and inexperience with such work. I definitely need to get through processing the pattern for 7 before I can have a clearer picture, but, since I am stopping here, I will throw out the following tenuous rule:

Possible Rule: Based on my very limited work the complexity increase with each prime processed is one of these 3 ideas: the square of the previous number of complexity steps * 2; the cube of the previous number of complexity steps; or the number of previous complexity steps * 4.

This was more evident from processing 5 and 7:

  • 2 – 0 extra programmatic steps
  • 3 – 1 extra programmatic step
  • 5 – 2 extra programmatic steps
  • 7 – 8 extra programmatic steps
  • 11 – I expect near 32, 128, or 512 extra programmatic steps

Keep in mind, this is probably not close to wholly accurate given my limited data and processing (up to 7), but it might give you a place to start with in understanding the complexity of finding the multiples in each successive prime generation using this technique. I really need to find out how many extra steps are required for 11 to have a better idea about my observations.

Diminishing Returns with each Processing Generation

When we start with 2 we remove half of the numbers and as we process each generation we reduce fewer and fewer numbers which will seem to result in diminishing returns from processing each generation.

  • 2 – 49.9%
  • 3 – 16.6%
  • 5 – 6.6%
  • 7 – 3.3%
  • 11 – I expect this will be near 1.98%

I expect there is a mathematical relationship to be found here, but I am not sure what yet. I also expect that for any given dataset that proportionally numbers will be found. At some point, depending on the size of your dataset, may not be worth the extra work to try to find a pattern and just working on a brute force technique to process.

Possible Rule: Law of Diminishing Returns – the % of multiples removed as compared to the previous generation is roughly equal to the delta removed by the previous generation + 10%. This average increase may also be increase be a few % points too assuming that the delta from 2-3-5 has any real bearing on further results.

Square Primedat

Possible Rule: It appears that once you get done removing a prime’s multiples from a dataset (and all previous primes’ multiples) then all numbers up until the square of the next prime will be prime numbers.

Closing

Working through the primes through 7 gives us to a total reduction of 76.5 of the dataset up to 1000. =O My primes are correct up the the next square which is for 11 @ 121. I would need to process that and then the prime numbers list would be correct until the next square – 13 @ 169. I am expecting that this will be the patttern if we were to continue. Since I need a really large dataset to see the pattern for 11 I think I will stop now. Hopefully, someone will find this useful. =) I am sure there are much more complex mathematical relations here than I able to discern with my limited knowledge (not a mathematician), time, tools, and experience.

Possible Rules

Here is the collection of the potential observed rules from above so we can have them all in one place:

  • Increasing Dataset Size: To find the pattern for each successive prime we will need a dataset 10 times larger than the previous one.
  • Increasing Pattern Complexity: The increase with each prime processed is the one of these 3 ideas: the square of the previous number of complexity steps * 2; the cube of the previous number of complexity steps; or number of complexity steps * 4.
  • Law of Diminishing Returns: the % of multiples removed as compared to the previous generation is roughly equal to the delta removed by the previous generation + 10%
  • Square Prime Rule: Once you get done removing a prime’s multiples from a dataset (and all previous prime’s multiples) then all numbers up until the square of the next prime will be prime numbers.

Data Analysis

The info for primes 11, 13, 17 are predicted based on my limited observational projections here:

prime # of non-repeating numbers reduced % of total numbers reduced % delta in reduction from previous gen dataset required to see pattern extra programmatic steps
prime # of non-repeating
numbers reduced
% of total numbers
reduced
% delta in reduction
from previous gen
 dataset required to see pattern extra programmatic
steps
1
2 499 49.90% 49.90% 0
3 166 16.60% 33.27% 30 1
5 66 6.60% 39.76% 75 2
7 33 3.30% 50.00% 500 8
11 19.8 1.98% 60.00% 5000 512 or 128 or 32
13 13.86 1.39% 70.00% 50000 134,217,728 or 524,288.00 or 128
17 11.088 1.11% 80.00% 500000 2.41785E+24 or 36,028,797,018,964,000 or  512

Flash Fiction – “Callie, Morning Drama” (~ 1,030 words, modern)

Note: This is sort of a prequel to my first flash fiction attempt titled Flash Fiction – “Callie” (~ 700 words, medical modern).

Melanie stood there with her hands thrust angrily upon her hips as she looked up the dark wooden staircase and then yelled “Callie, unhealthy hurry up or you will be late for school. Conner’s principal is going to be really angry if he’s late again. Come on, child! It does not take that long to brush your teeth!

They were always waiting for their little Callie and it made everyone cross. They were not sure if Callie was just slow for a 9-year-old or doing it for the attention. Her husband, Jeff, even pondered the possibility that perhaps Callie was a budding Time Lord whose sense of time was different than everyone else’s. Her two other children, Connor, age 12, and Crystal, age 6, looked at her, their faces scrunched up in annoyance. Even Crystal was standing with her arms crossed because she would most likely miss play time and possibly even their morning snack time and, today, Conner could lose his place on the middle school football team if he was late to school… again.

Calliiie!!” Melanie yelled. She looked back to Conner and Crystal. “Conner, go help Crystal into her seat and wait for us in the car so we can leave as soon as she gets done.” Conner muttered “Ugghh” under his breath as he gave Crystal a little push toward the door to the garage. Crystal angrily shrugged his hand off her shoulder in a way that looked like a spasm. Looking back to him, she narrowed her eyes in an icy stare and then her pigtails jerked about as she stomped towards the garage. Shaking his head Conner could be heard grumbling “Uggh!” louder this time as he walked after Crystal, his red football helmet under his left arm. This was how it was every morning no matter how they tried to change things so that Callie (and the rest of the family) could be on time.

This seemingly irreparable morning drama had manifest as Callie has grown older, more independent, and responsible for her own routine. This morning drama set Melanie’s days wrong and made her cranky because she was usually late to work. Melanie has become her office’s ‘late person’ and she has never been that person, nor did she ever want to be. She has heard that her supervisor, Teri, who also has kids, gets to work on time, usually a 10 or so minutes early. ‘God, how different would things be if they never had Callie.’ she spitefully thought to herself. Her husband, Jeff, never had to deal with the morning drama because he had to leave an hour early to get to work, and he never understood why she was always so cranky when she got home.

Ok, Callie, you are going to have to take the bus home tonight, so mommy can make up the lost time from your teeth brushing time-warp.

Callie’s voice whined down “But Mom, I hate the bus. The older kids are mean to me.

Cross that Callie had the temerity to be upset with this, Melanie growled “Well, consider getting done on time in the morning and this would not have to happen. It is your choice, little girl! Let’s go!

Callie stomped down the stairs, her pale cheeks and ears were red and her lips were pursed in anger. Sternly Melanie said, “Get in the car!” After Callie ran out to the car Melanie stalked after her grumbling the whole time. She snapped up her phone so she could call their schools and her office to let them know that they were all going to be late… again.


Tired from a long day at work Melanie returned home after six o’clock. She walked in and saw Jeff cooking and Conner at the table working on his math homework. She sat her purse and briefcase down on the counter, hung up her coat, and then, unceremoniously plopped down into a chair at the table. Jeff started to speak “How’d…”.

Don’t ask!” she quickly cut him off. Connor looked up at his mom and then quickly looked back down. He could feel the tension and the stress in her, so he decided that now was not a good time to talk about his football practice problems.

She quietly asked “Crystal?

Just started a bath.

She could smell the garlic aroma from the sauce he was working on for spaghetti, Callie’s favorite. Still grumpy about this morning’s events she rolled her eyes, straightened up a little, and cleared her throat.

Callie in her room trying to avoid me?” There was a pause as Conner looked up and Jeff turned around, confused.

We thought you were picking her up as usual. I was expecting her to walk through the door after you.

Melanie’s eyes and mouth went wide and her mind started running. She stumbled out “I, I told her to take the bus home after school, because I was going to be at work late.” She stood up quickly, the chair slid away, groaning in protest against the wooden floor. Her heart pounded in fear as she quickly picked up the phone from the table and started to make a call. Jeff turned down the burners for the spaghetti and the sauce and then picked up his phone too. Jeff heard the fear in her voice and then, calmly, said to Conner “Conner, why don’t you finish your homework in your room, while mom and I make some calls.” Without making a noise Conner, not sure what this meant, picked up his books and quietly walked to his room.

They each made some calls to Callie’s friends, to the school, posted to Facebook, and then, finally, called the police. All they found out was that some of the kids saw her at the bus stop after school. Jeff pulled Melanie close as she started to sob, eyes red as tears streaked down her cheeks. He rocked her in his arms as she repeated through choked tears “Where’s our Callie, Jeff? Where’s our little girl?

Her phone rang. Jeff Answered. It was the FBI.