Thursday, 21 March 2013

Finding Prime Numbers with Leaping Frogs

Imagine a pond that contains a long line of lily pads, each labelled with a number, starting with '2', '3', and so on.

A scary stork enters the pond, looking for frogs!  Each turn, the stork will move to a new lily pad, starting with lily pad 2.

When the stork reaches a lily pad, it looks for frogs:
  • If the lily pad has no frogs on it, the stork finds one in the water. Take a new frog token and write the lily pad's number on its back. Put it on the lily pad with the stork.
  • If the lily pad already has frogs on it, the stork won't look in the water, so this lily pad does not get a frog of its own.
The stork then shouts, "Boo!"  This scares the frogs, who jump away. All the frogs jump forward a number of lily pads equal to the number written on their backs.  Frog #2, for example, will make the first leap from lily pad #2 to lily pad #4, and then later to lily pad #6. (It's okay for frogs to share lily pads.)

Stop after however many turns you like.  When you're done, the numbered frogs represent all the prime numbers that you found (at least from numbers 2 to whatever lily pad you stopped at).

When a stork first reaches a lily pad, all the frogs there are the prime factors of that number.  For example, when the stork reaches lily pad #20, the stork will find frogs 2 and 5 there.  (20 = 2 x 2 x5.)  Lily pad 19, however, is empty when the stork arrives arrives: the newly minted frog 19 indicates that 19 is a prime number, and there are no other prime factors (other than 1).

To summarize:
  1. Move the stork forward one lily pad (on the first turn, place it on lily pad 2).
  2. If the lily pad has no frogs on it when the stork gets there, make a new frog with the lily pad's number.
  3. All the frogs on the stork's lily pad jump forward a number of pads equal to their number.