Animated Sieve of Eratosthenes

Posted on April 11, 2013 by Brent

Here’s something I made yesterday! (Note, I strongly suggest watching it fullscreen, in HD if you have the bandwidth for it.)

Can you figure out what’s going on? The source code for the animation is here; I was inspired by Jason Davies’ visualization which was in turn inspired by this.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

This entry was posted in arithmetic, counting, pattern, pictures, primes, video and tagged diagrams, Eratosthenes, primes, sieve, visualization. Bookmark the permalink.

12 Responses to Animated Sieve of Eratosthenes

Joseph Nebus says:

April 12, 2013 at 12:21 am

Reblogged this on nebusresearch and commented:
The Math Less Traveled has a lovely video here, animating the Sieve of Eratosthenes, one of the classic methods of finding all of the prime numbers one wants. I suppose it won’t eliminate writing out and crossing off numbers for extra credit on a math test. I actually remember that being one test I had in, I believe, seventh grade, for reasons that I don’t think I ever got. Possibly the teacher wanted to have an easy time grading, or was giving everyone a break from too much computation by shifting to evaluation of our crossing-out abilities.
Charles Gilbert says:

April 12, 2013 at 8:47 am

Brent –

Could you take a look at “Sloppy Computing” and give your opinion ? Specifically, does this form of computing dramatically increase computer power for math programs (Like simulators) ?
- Brent says:
  
  April 12, 2013 at 9:21 am
  
  Yes, I think “sloppy computing” is a very cool idea. Ultimately, I think it’s primarily more about reducing power usage than it is about increasing speed — as computers get smaller, power consumption and heat dissipation are becoming major limiting factors. Sloppy computing could indeed be very useful for certain types of computations such as simulation.
goldenoj says:

April 12, 2013 at 9:02 am

I love it. Gorgeous, and gives a lot of feel for the sieve.

Is there anyway to add a counter in the lower left – to show what number you’re at?
- Brent says:
  
  April 12, 2013 at 9:24 am
  
  Oh, a counter in the lower left is a good idea!
md2perpe says:

April 12, 2013 at 9:43 am

This gave me the idea to form the infinite product $f(x) = \sin{\frac{\pi x}{2}} \, \sin{\frac{\pi x}{3}} \, \sin{\frac{\pi x}{4}} \, \sin{\frac{\pi x}{5}} \, \ldots$ . The primes will be those integer $x$ where $f'(x) \neq 0$ .
- Jim says:
  
  April 12, 2013 at 4:38 pm
  
  The infinite product you give converges to zero for every value of x so f(x) = 0 identically.
  So f'(x) = 0 identically.
  - Per Persson says:
    
    April 12, 2013 at 4:51 pm
    
    Thanks, I actually suspected that. Can you find a way to account for this by for example defining a sequence of functions $f_n(x) = C_n \prod_{k=2}^{n} \sin{\frac{\pi x}{k}}$ and setting $C_n$ so that the sequence converges?
Jim says:

April 16, 2013 at 8:31 pm

Cn = (n!)/(pi^(n-1) x^(n-1)) .
- Per Persson says:
  
  April 26, 2013 at 11:18 am
  
  Of course… For large $k$ we will have $\sin{\frac{\pi x}{k}} ~ \frac{\pi x}{k}$ and taking $C_n = n!/(\pi^n x^n)$ will compensate for those factors.
  Have you studied what the limit function will look like?
  - Per Persson says:
    
    April 26, 2013 at 11:21 am
    
    It should say $\sin{\frac{\pi x}{k}} \sim \frac{\pi x}{k}$ .
Pingback: Criba de Eratóstenes animada | Actualidad informática