Blog

Geek Challenge Results: Fractal Snowflake

Geek Challenge Results: Fractal Snowflake

The winner of the Fractal Snowflake Geek Challenge is John Jacobsma of Dickson. Tim Jager of DMC also responded with a correct value of C, 10830.

The Fractal Snowflake Challenge was a study in recursive programming. Recursive programming is a technique where a function calls itself, usually many times, until eventually instead of calling itself, it just does something. The program had two layers of recursive programming in it:

The function MakeTriangle was what actually did something in the end. It made one of the little blue triangles we were counting.

The function Sierpinski made the triangle shaped fractal. It is called with an Order parameter, and if the order is zero, then it calls MakeTriangle. If the order parameter is > 0, it just calls itself 3 times with an order decremented by 1.

The function KochSide is responsible for jagged looking sides of the snowflake. It also takes an Order parameter; At order 0, it does nothing, but at higher orders it calls itself 4 times, and Sierpinski once, all with order decremented by 1.

The function CombinedFractal calls Sierpinski once to fill in the largest fractal triangle, then calls KochSide 3 times to fill out the jagged edge pattern on all sides of the triangle.

To solve the puzzle of counting the little triangles, the easiest way to do it was to modify MakeTriangle to simply count instead of actually making triangles. Then run the program, and it will give the answer: 10830.

John Jacobsma simplified and re-wrote the program in Java. Without any of the geometry, this program shows just the recursive nature of the problem:

package counttriangles;

public class CountTriangles implements Runnable
{
  public static void main(String[] args)
  {
    new CountTriangles().run();
  }

  @Override
  public void run()
  {
    System.out.println(combined(6));
  }

  int combined(int order)
  {
    return sierpinski(order) + 3 * koch(order);
  }

  int koch(int order)
  {
    if (order <= 0)
      return 0;
    return sierpinski(order - 1) + 4 * koch(order - 1);
  }

  int sierpinski(int order)
  {
    if (order <= 0)
      return 1;
    return 3 * sierpinski(order - 1);
  }
}

The problem can also be solved without delving into the programming, but by analyzing the pattern.  

Order 0 has just 1 triangle. Each additional order spits each triangle into 3, so it has 3 times more triangles than the previous. So, the triangle counts of Sierpinski triangles are 1, 3, 9, 27, 81, 243 and 729. Also note that the order of a Sierpinski triangle can be determined by counting the interior white triangles down the middle.

Three white triangles down the middle indicates an order 3 Sierpinski triangle:  


Next, the Koch pattern can be analyzed. A level 2 Koch snowflake is shown here with the edges marked. The level pattern in Red is repeated 4 times by pattern in Green. Each additional level continues to multiply by 4.  But the first Red pattern is performed only 3 times, for the 3 sides of the center triangle.


So, the number of triangles that make up solid Koch snowflake is 1, 3, 12, 48, 192, 768, 3072.

Since the fractal snowflake pattern is made of Sierpinski triangles instead of solid triangles, the pattern of the order of the Sierpinski triangles has to be determined. It can be observed that the central triangle is order 6, and each smaller triangle on the perimeter is seen to be 1 level smaller, down to level 0 triangles on the fringes:

Now, the two numeric sequences can be combined and summed to determine the total number of triangles:

Sierpinski Koch Total
Triangles Triangles Triangles
1 3072 3072
3 768 2304
9 192 1728
27 48 1296
81 12 972
243 3 729
729 1 729
     
Sum   10830

 

Comments

There are currently no comments, be the first to post one.

Post a comment

Name (required)

Email (required)

CAPTCHA image
Enter the code shown above:

Related Blog Posts