Geometrical Dissections I

Closely related to the problem of tiling the plane with polygons is that of dissecting one geometrical object into pieces that can be rearranged to form another. The classic example is the following dissection of an equilateral triangle to a square, attributed to Henry Dudeney, 1907.

Day014TriToSquare

Note that the pieces are exactly the same in both polygons. It’s not hard to appreciate the beauty and elegance of this “geometrical artwork.” And it’s not hard to imagine a puzzle based on this dissection — give the puzzler these four pieces with instructions to make both a triangle and a square from the same pieces.

This led me, once upon a time, to construct an Honors Geometry course centered around geometrical dissections using  Greg Frederickson’s wonderful Dissections Plane & Fancy.

But even “simple” dissections — involving triangles and squares — weren’t so easy to create. For example, the pieces divide the base of the equilateral triangle into lengthsDay014formulaand these are some of the easier calculations! I won’t say more about that here — but you can read all about this dissection and many others in Greg’s book.

So I was fascinated by geometrical dissections — but I needed a way to make the idea accessible to my students. I thought — what could you create just by experimenting with dissections on ordinary graph paper?

Well, I have been answering this question for over 15 years now. I’ll start with some introductory ideas in this post, but this is definitely not the last word on dissections!

Let’s begin with the following puzzle.  By cutting the rectangle along the grid lines, how many pieces are needed so you can also make the square with a corner missing?Day014Puzzle1AThis seems like an easy puzzle to solve, as shown below.Day014Puzzle1BSo yes, only two pieces are necessary — but one had to be rotated. Here is the question: can this puzzle be solved with just two pieces, but with neither piece rotated?

It turns out this is possible — but a solution requires a bit more creativity. Here is one way to do it:Day014Puzzle1CThis is a solution technique commonly used in Dissections Plane & Fancy.  Why bother?  In the world of geometric dissections (and it is a growing universe, surely, as any internet search will show), finding a minimum number of pieces is the primary objective.  But of all solutions with this minimum number of pieces, “nicer” solutions require rotating the fewest number of pieces.  And rotating none at all is — in an aesthetic sense — “best.”  It is also preferable not to turn pieces over, although sometimes this cannot be avoided for minimal solutions.

Another criterion for solutions might be whether they can be hinged or not, as Greg discusses extensively in Hinged Dissections:  Swinging & Twisting.  We won’t have time to explore this topic today.

Of course there is no reason you have to start with a rectangle, and also no reason why you need to restrict yourself to just one shape.  The puzzle below shows how you can find a four-piece, rotation-invariant dissection from two smaller octagons to one larger octagon.Day014Puzzle2It is important to note that the octagons here are not regular.  A quick glance through Dissections Plane & Fancy will reveal that dissections involving regular polygons are generally rather difficult (as the initial triangle-to-square example amply shows).

Further, “two-to-one” dissections lend themselves nicely to a square grid, as the diagonal of a unit square has length square root of 2.  Take a moment to study the octagon dissection again — paying particular attention to the side lengths — to see how this plays out.  In the world of regular polygons, however, two-to-one dissections are in general quite difficult.  Visit Gavin Theobald’s web page of two-to-one dissections to see some fascinating examples.

It is not hard to create dissection puzzles of your own — a pencil, eraser (!!!), and graph paper are all you need.  What is difficult, however, is proving that you’ve found the fewest number of pieces.  And when you have, proving that your dissection is unique.  Uniqueness is virtually impossible to prove, but sometimes you can get a handle on minimality.  For example, if the octagon dissection could be done in three pieces, one of the smaller octagons would have to be uncut.  It’s not hard to see that there is no way of cutting the other smaller octagon into just two pieces to create the larger octagon.

What I enjoy about creating dissection puzzles is that there is not a single strategy you can use to solve them.  You really need to use your imagination.  Sometimes you might even surprise yourself by stumbling upon a really neat puzzle, like the one below.

Here, an 8 x 8 square with four holes (shown in black) can be dissected into three pieces to create a 6 x 10 rectangle, although one piece needs to be rotated.  There is a simple elegance about this dissection which I find appealing.Day014Puzzle3

Another grid which lends itself to creating dissections is a grid of equilateral triangles.  We won’t go into details here, but you can get the idea with the following dissection of an irregular dodecagon to an equilateral triangle in just five pieces.  (The minimal dissection with regular polygons requires eight pieces.)Day014Puzzle4I’ll leave you with two puzzles to think about.  Of course, you can just make up your own.  If you come with anything interesting, feel free to comment!

For this puzzle, my best solution is four pieces, without needing to rotate any pieces or turn any pieces over.  (Black squares are holes.)Day014Puzzle5

For the last puzzle, my best solution is five pieces — but I had to turn over and rotate two of the pieces.Day014Puzzle6

A parting suggestion:  when looking up dissections on the web, be sure to use the search words “geometrical dissections…..”

Writing Original Problems

How do students view mathematics?

Not surprisingly, many (if not most) students see mathematics as a set of known problems to be solved — changing a few numbers here and there, perhaps — but essentially, all of mathematics is known.

Mathematicians have rather the opposite view — we’re just scratching the surface.  There is so much more underneath.

As I mentioned in my first post, mathematics is creative.  What makes this difficult for students to appreciate is that the artistic medium is that of abstraction, and without a real understanding of abstraction in mathematics, the creative aspect is hard to see.

But there is a way to help students experience the creative side of doing mathematics — and that is by having them write their own Original Problems.  I began thinking about this while I was teaching a course in problem solving at a magnet STEM high school — and being an avid problem writer myself, I imagined that having students write problems would help them solve problems.  Whether this is true or not is difficult to determine.  Regardless, an assignment was born….

What really got me interested in this assignment was the student comments at the end of the semester.  One student wrote,

Anyone can write tedious, difficult problems that review core math subjects, but to write problems in a novel, challenging, and refreshing manner, one must be imaginative. I feel that this creative side of math is an often overlooked aspect of the field as many believe math to be an extremely black-and- white, rigid, and boring subject.

I was intrigued by the fact that even though students were not prompted to address creativity in writing their course evaluations, some spontaneously did so.  As a teacher, I was delighted — an unanticipated side effect of an assignment designed for another purpose was somehow more significant to me than the intended outcome.

Fueled by this success, I introduced the assignment in an Honors Calculus section I taught, and students responded positively again.  Then I incorporated writing Original Problems into a traditional calculus classroom, then precalculus, then algebra — and students kept getting it.  Posing problems was no longer an assignment just for advanced students.

What does the assignment look like?  I break it down into four sections.  First, Motivation.  Where did the problem come from?  For some students, they might start looking in their textbook at interesting problems.  For others, they take inspiration from their daily life.  One calculus student said he came up with his problem because he dropped his backpack down the stairs and had to retrieve it — and he immediately thought of this as a displacement/velocity problem.  Another student was doodling figure eights, and created a problem about ice skating on a figure-eight shaped rink.  It is remarkable what students can create, given the opportunity!

Second, the Problem Statement.  This is actually quite difficult for some students.  And we teachers know the challenge of writing a test whose problems can be interpreted in only one way.  Now that I’ve moved on from the STEM high school to teaching university again — and work with a different set of students — I now assign the Motivation and Problem Statement as a separate assignment.  That way, I can give written and verbal feedback to students and help them craft a well-stated, manageable problem.  This has been very helpful for the students, and the quality of their final submissions has improved.

Third is the Problem Solution.  This is fairly self-explanatory, but a few comments are in order.  I like to give students wide latitude in selecting a problem of interest to them — sometimes they want to challenge themselves with a difficult problem.  In this case, a partial solution is fine.  The point is to get them writing mathematics — and a partial solution to a difficult problem often involves more mathematics than a complete solution to a more routine problem.

Finally, there is the Reflection.  I only ask for a few sentences or a paragraph — enough to give me a sense of how students are responding to the assignment.  These can be very revealing, and you sometimes get students who really appreciate the assignment and understand its purpose.  All four sections are to be included in the final submission.

You might be interested in a recent Original Problem prompt.  This assignment is highly adaptable.  I’ve had colleagues who wanted to narrow the focus because the assignment seemed to broad.  Suggesting a specific application — such as the Pythagorean theorem — will give students a starting place.  In my mind, the assignment is about creativity, writing, and self-determination.  Let students choose a topic to create a scenario and write about it, and they start to get a handle on what creativity in mathematics is all about.  There is no one way to accomplish this.

I should say a few words about grading these assignments.  At their broadest, these assignments read like short essays.  But they’re all different, so you can’t really develop a rhythm in the grading process.  So Original Problems take more time to grade — this semester I’m just giving two assignments, so it’s more manageable.  I do think it’s important to give at least two assignment, so students have a chance to improve.  Generally, I’m more lenient when I grade the first assignment, since often this is the first time students will have encountered such an assignment.

To encourage creativity, I tell students that if they just do the assignment  — and get their mathematics correct — they won’t earn lower than a B.  I don’t want them worrying about grades (and we’re stuck with them for a while!), although some inevitably do.  I rarely give a C, unless it’s evident a student waited until the last minute, or a student worked below their potential.  I do believe that for an assignment like this, you should evaluate students relative to themselves, not their peers.  More able students should be pushed — and frankly, most of them appreciate it when you do push them.

Many students really do begin to understand the creative aspect of mathematics after doing these assignments.  They really do enjoy getting to choose their own problem — and though it is sometimes challenging to come up with a way for them to develop a particular idea, I rarely tell them to just choose another topic.  I try to find some avenue they can pursue.

So I encourage you to give Original Problems a try!  Let me know how it goes.  For additional reading, you can find an article about writing Original Problems in Publication 10 on my website.  There is also a discussion of several student problems in Chapter 6 of Mathematical Problem Posing.  It really is time to have all students experience creativity in mathematics.  This is one of the main purposes of writing this blog, after all.

Evaporation II

Last week, we began exploring the piece Evaporation.  In particular, we looked at two aspects of the piece — randomness of both the colors and the sizes of the circles — and experimented with these features in Python.  Look at last week’s post for details!

Day011Evaporation2bWeb

Today, we’ll examine the third significant aspect of the piece — the color gradient.  The piece is a pure sky blue at the top, but becomes more random toward the bottom.  How do we accomplish this?

Essentially, we need to find a way to introduce “0” randomness to each color at the top, and more randomness as we move toward the bottom.  To understand the concept, though, we’ll be introducing 0 randomness at the bottom, and more as we move up.  You’ll see why in a moment.

Let’s first look at a linear gradient.  Imagine that we’re working with a 1\times1 square — we can always scale later.  Here’s what it looks like:

Day012linear

The “linear” part means we’re looking at randomness as a function of y^1=y.  So when y=0, we subtract y=0 randomness to each color.  But when y=1/2, we subtract a random number between 0 and y=1/2 from each of the RGB values.  Finally, at the very top, we’re subtracting a random number between 0 and 1 from each RGB value.  Recall that if an RGB value would ever fall below 0 as a result of subtraction, we’d simply treat the value as 0.

Why do we subtract as we go up?  Recall that black has RGB values (0,0,0), so subtracting the randomly generated number pushes the sky blue toward black.  If we added instead, this would push the sky blue toward white.  In fact, you can push the sky blue toward any color you want, but that’s a little too involved for today’s post.

The piece Evaporation was actually produced with a quadratic gradient.  Let’s look at a picture first:

Day012quadratic

That the gradient is quadratic means that the randomness introduced is proportional to y^2 for each value of y.  In other words, at a level of y=1/2 on our square, we subtract a random number between 0 and

(1/2)^2=1/4.

You can visually see this as follows.  Look at the gradient of color change from 0 to 1/2 for the quadratic gradient.  This is approximately the same color change you see in the linear gradient between 0 and 1/4.  Why does this happen?  Because when you square numbers less than 1, they get smaller.  So smaller numbers will introduce less randomness in a quadratic gradient than they will in a linear gradient.

We can go the other way, we well.  If we use a quadratic gradient (exponent of 2>1), the color changes more gradually at the bottom.  But if we use an exponent less than 1 (such as in taking a root, like a square root or cube root), we get the opposite effect:  color changes more rapidly at the bottom.  This is because taking a root of a number less than 1 increases the number.  It’s easiest to see this with an example:

Day012root

In this case, the exponent used is 0.4, so that for a particular y value, a random number between 0 and y^{0.4} is subtracted from each RGB value.  Note how quickly the color changes from the sky blue at the bottom toward very dark colors at the top.

Of course this is just one way to vary colors.  But I find it a very interesting application of power and root functions usually learned in precalculus — using computer graphics, we can directly translate an algebraic, functional relationship geometrically into a visual gradient of color.  Another example of why it is a good idea to enlarge your mathematical toolbox — you just never know when something will come in handy!  If I didn’t really understand how power and root functions worked, I wouldn’t have been able to create this visual effect so easily.

Now it’s your turn!  You can visit the Evaporation worksheet to try creating images on your own.  If you’ve been trying out the Python worksheets all along, the code should start to look familiar.  But a few comments are in order.

First, we just looked at a 1\times 1 square.  It’s actually easier to think in terms of integer variables “width” and “height” (after all, there is no reason our image needs to be square).  In this case, we use “j” as the height parameter, since it is more usual to use variables like “i” and “j” for integers.  So “j/height” would correspond to y.  This would produce a color gradient of light to dark form bottom to top.

To make the gradient go from top to bottom, we use “(height-j)/height” instead (see the Python code).  This makes values near the top of the image correspond to 0, and values near the bottom of the image correspond to 1.  I’ll leave it to you to explore all the other details of the Python code.

Please feel free to comment with images you create using the Sage worksheet!

As mentioned in the previous post as well, each parameter you change — each number which appears anywhere in your code — affects the final image.  Some choices seem to give more appealing results than others.  This is where are meets technology.

As a final word — the work on creating fractals is still ongoing.  I’ve learned to make movies now using Processing:

You’ll notice how three copies of one fractal image morph into one of another.  You can find more examples on Twitter: @cre8math.  Once I feel I’ve had enough experience using Processing, I’ll post about how you can use it yourself.  The great thing about Processing is that you can use Python, so all your hard work learning Python will yield even further dividends!

Evaporation I

This and the next post will walk you through how to create digital art similar to Evaporation.  I’ll also show you some Python code you can use yourself to experiment.

Day011Evaporation2bWeb

There are three significant features of Evaporation. First is the randomness of the colors. Second — if you look closely — the sizes of the circles are also different; these are randomly generated as well. The third feature is the gradient of the color — from a pure sky blue at the top, to a fairly randomly colored row of circles at the bottom. We’ll look at the first two features today.

Day011Evap1

Let’s look at color. In the figure above, the small teal square at the left has RGB values of 0, 0.5, and 0.7, respectively. The larger square at the left consists of 100 smaller squares. The color of each of these squares is generated by adding a random number between 0 and 0.1 to each of the RGB values 0, 0.5, and 0.7 — with a different random number added to each value. In the middle square, a random number between 0 and 0.2 is added, so this creates a wider range of color values. For the right square, the random numbers added are between 0 and 0.3.

But there is no reason that the ranges need to the same for each color. In the images below, the red values have a wider range of randomness then the green, which is “more random” than the blue.

Dao011Evap2

You can see that different ranges of random numbers create different color “textures.” This is where I think computer meets art — as a programmer, when it comes to creating random numbers, you have to specify a range for the randomness of each variable. The choices you make determine how your image looks. How do you make “artistic” choices? There is no easy answer, of course.

Another way to use randomness is by varying the size of the graphic objects. In the left square below, texture is created by randomly changing the radii of the circles.

Day011Texture2

In the middle square, the circles are all the same size, but random shades of gray. The right square varies both the size of the circles and their color. The final result depends on “how much” randomness is used. You can try it for yourself by altering the Python code linked to below — change the randomness and see what happens!

I think of my laptop as an art laboratory. It is a place to experiment with different ideas — change this parameter, increase randomness, try out different color combinations. Can you imagine creating any of the images in this post by hand? The computer allows us to perform experiments unthinkable to Rembrandt and Van Gogh. We may lose the texture of brush strokes or the dimensionality of paint on canvas, but what we gain by having a programming language at our disposal makes up for this loss.  At least in my opinion….

Now let’s look at how we can use Python to create these images.  You can experiment with this color and texture worksheet.

There is not much more to say here since a lot is explained in the worksheet. But as you are creating, keep a few things in mind.

1. Use descriptive variable names. This helps a lot when you’re looking a lines of code. Using variables a, b, c, etc., doesn’t help much when you’re looking at a program you wrote a few months ago.

2. Comment liberally! Notes to yourself are easy to use in Python — just start a line (or part of a line) with the “\#” character. You’ll thank yourself later.

3.  Save versions often! I won’t bore you with stories of using Mathematica to do some intense computations for creating digital art — and then read the “Mathematica quit unexpectedly” message on my screen — before I saved my work. I’ve encountered this in Python, too — if you use the online version, you’re connecting to an external server, which hopefully will not encounter problems while you’re working….

Also, as you change parameters, you may want to keep track of results you like. If there are a lot of these, sometimes I write the parameters as comments — so I can reproduce them later. Very important: don’t forget to keep track of the random number seed you use! The feel and texture of an image can vary dramatically with the random number seed, so don’t ignore this vital parameter.

One final thought.  In creating this type of art, I keep in mind the tension between structure and randomness.  You can use the computer to create randomness — but if there’s too much randomness, the image doesn’t seem to hang together.  But if there’s too much structure, the image can lose its interesting texture, and appear flat and purely two-dimensional.  So the choice of parameters in creating randomness is fairly crucial in determining how the final image will look.  And as I’ve said before — this is where technology meets art.  It is fairly easy to create a computer-generated image — but not as easy to create computer-generated art.  The difference is not exactly easy to describe — and certainly opinions will differ.  It is the questions which arise in describing the difference which are intriguing and exciting.

Enough philosophizing. Time to begin the artistic process!  Feel free to comment by posting any images you create using the Python code.

ColorSlide Puzzles

Part of the fun of writing a math blog is designing new puzzles.  I wanted to come up with a puzzle which incorporated color and logic, so here’s the result!

In the grid below, slide the tiles either horizontally or vertically onto the grid so that each row and column contains exactly one each of green, cyan, magenta, and yellow dots. When two dots share the same square, they are combined, so that if a green and a red dot occupy the same square, the dot is yellow, while if a blue and a green dot occupy the same square, a cyan dot is produced. In other words, overlapping the tiles is like adding their RGB values.  (If you aren’t familiar with RGB values, you can experiment in the “Continue reading” section by searching for Day002 in my blog.)  Horizontal tiles may only overlap vertical tiles (and not other horizontal tiles), and vertical tiles may only overlap horizontal tiles.

Dots of the same color may never overlap — although this condition follows from the puzzle setup. Note that green, cyan, and yellow all require a green dot, so with four rows/columns, at least 12 green dots are necessary. Since there are exactly 12 green dots, no two green dots may overlap. Similar arguments show that no two red dots or two blue dots may overlap, either.

Day010CS1

In the first part of the post, we’ll solve this puzzle so you see what’s involved.  We’ll look at the design later.

Let’s start by looking at Column 1. Each row column needs three green dots, two red dots, and two blue dots — this follows from the fact the the RGB values of the four colors in the completed puzzle are (0,1,0), (0,1,1), (1,0,1), and (1,1,0). Since the vertical tiles in Column 1 already include three green dots, we know how to place the tiles in Row 2, since we need to avoid a fourth green dot in the first column. This results in

Day010CS2

Now see that however the tiles are placed in Column 1, the dot at (2,1) — Row 2 and Column 1 — must be yellow. So (2,4) can’t be yellow, and therefore we know how to place the tiles in Column 4.

Day010CS3

Note how the red and blue dots overlap to create magenta.  Since there are no blue dots in the completed puzzle, we must place the tile in Row 3 so that the blue dot is covered by a green one (making a cyan dot).

Day010CS4

Since green dots cannot overlap, we know how to place the tiles in Rows 1 and 4.  Note the red and green dots overlapping in (4,4) to create yellow.

Day010CS5

Since green dots cannot overlap, we know how to place the tile in Column 2.  See how the overlapping dots create yellow, cyan, and magenta dots.

Day010CS6

Now in Column 1, there can only one be yellow dot. So we know how to place the tiles in Column 1, and it is easy to slide the remaining tiles from Column 3.

Day010CS7

That wasn’t so bad! Just a little knowledge of color theory and a bit of logic is all you need.

These puzzles are fun to create.  However, there are a few issues to be aware of.  The first arises since you want to avoid too many single dots — I used just one in the first puzzle, and I think that’s enough.  It’s actually rather easy to create a grid with one of each color in each row and column — there are called Latin squares.  The hard part is then creating an appropriate set of tiles.  The difficulty lies with the fact that some squares are covered by just one tile, others by two.

In the following small grid, the numbers represent how many dots are needed to create a color in a certain location.

Day010CS8

Suppose we wanted a vertical tile to cover a 1 and a 2 in column 3.  Since (2,3) is covered by two tiles and vertical tiles cannot overlap, this means we must use a horizontal tile here.  But then the only way to cover location (1,2) is with a horizontal tile and a vertical tile of height 1 (since the 1’s are already covered).  But this is exactly what we want to avoid!  Once I realized was happening, I first designed a grid with just 1’s and 2’s and a corresponding tile set, then added the colors later.  In other words, I broke a harder design problem into two easier ones.

The other issue which arose was the question of uniqueness.  It’s desirable to have a unique solution to puzzles like this — when you design a puzzle, you clearly have one solution, but can you be sure that there aren’t any others?  This is not an insurmountable task, but for the larger puzzle below, it was more involved than I thought it would be.

So I leave you with a 6 x 6 puzzle to solve.  Slide the tiles so that there is a red, green, blue, yellow, magenta, and cyan dot in each row and column.  As mentioned above, the solution is unique.  Feel free to post your own puzzles if you create them!

Day010CS9

Creating Fractals III: Making Your Own

Last week, we laid down some of the mathematical foundation needed to generate fractal images.  In this third and final post about creating fractals, we’ll discuss in some detail Python code you can adapt to making your own designs.  Follow along in this Sage notebook.

In order to produce fractal images iteratively, we need a function which returns the highest power of 2 within a positive integer (as discussed last week).  It is not difficult to write a recursive routine to do this, as is seen in the notebook.  This is really all we need to get started.  The rest involves creating the graphics.  I usually use PostScript for my images, like the one below discovered by Matthieu Pluntz.  There isn’t time to go into that level of detail here, though.

Day009Koch090-150

As far as the graphics are concerned, it would be nice to have an easily described color palette.  You might look here to find a wide range of predefined colors, which are available once we execute the “import mathplotlib” command (see Line 20).  These names are used in the “colors” variable.  Since each motif has four segments, I’ll color each one differently (though you may choose a different color scheme if you want to).

The loop is fairly straightforward.  On each iteration, first find the correct angle to turn using the highestpowerof2 function.  Then the segment to add on to the end of the path is

({\rm len}\cdot\cos(\theta), {\rm len}\cdot\sin(\theta)),

which represents converting from polar to rectangular coordinates.  This is standard fare in a typical high school precalculus course.  Note the color of the segment is determined by i % 4, since 0 is the index of the first element of any list in Python.

All there is left to do is output to the screen.  We’re done!  You can try it yourself.  But note that the way I defined the function, you have to make the second argument negative (compare the image in the notebook with last week’s post).  Be patient:  some of these images may take a few moments to generate.  It would definitely help the speed issue if you downloaded Sage on your own computer.

To create the image shown above, you need to use angles of 90 and -210 (I took the liberty of rotating mine 15 degrees to make it look more symmetrical).  To create the image below, angles of 90 and -250 are used.  However, 26,624 steps are needed to create the entire image!  It is not practical to create an image this complex in the online Sage environment.

Day009koch090-110

How do you know what angles to use?  This is still an open question — there is no complete answer that I am aware of.  After my first post on October 4, Matthieu Pluntz commented that he found a way to create an infinite variety of fractal images which “close up.”  I asked him how he discovered these, and he responded that he used a recursive algorithm.  It would take an entire post just to discuss the mathematics of this in detail — so for now, we’ll limit our discussion to how to use this algorithm.  I’ve encoded it in the function “checkangles.”

To use this function, see the examples in the Sage notebook.  Be careful to enter angles as negative when appropriate!  Also, you need to enter a maximum depth to search, since perhaps the angles do not result in an image which “closes up,” such as with 11 and -169.  But here’s the difficult part mathematically — just because our algorithm doesn’t find where 11 and -169 closes up does not mean that the fractal doesn’t close.  And further, just because our algorithm produced a positive result does not mean the algorithm must close.  Sure, we’ve found something that produces many results with interesting images — which suggests we’re on the right track.  But corroboration by a computer program is not a proof.

At the end of the notebook, I wrote a simple loop illustrating how you can look for many possibilities to try at once.  The general rule of thumb is that the more levels required in the algorithm to produce a pair of angles (which is output to the screen), the more segments needed to draw it.  I just looked for an example which only required 5 levels, and it was fairly easy to produce.

So where do we go from here?  Personally, I’ve found this investigation fascinating — and all beginning from a question by a student who is interested in learning more about fractals.  I’ve tried to give you an idea of how mathematics is done in the “real world” — there is a lot of exploration involved.  Proofs will come later, but it is helpful to look at lots of examples first to figure out what to prove.  When I find out something significant, I’ll post about it.

And I will admit a recent encounter with the bane of a programmer’s existence — the dreaded sign error.  Yes, I had a minus sign where I should have had a plus sign.  This resulted in my looking at lots of images which did not close up (instead of closing up, as originally intended).  Some wonderful images resulted, though, like the one below with angles of 11 and -169.  Note that since the figure does not close up (as far as I know), I needed to stop the iteration when I found a sufficiently pleasing result.

Day009koch011-191

If I hadn’t made this mistake, I might have never looked at this pair of angles, and never created this image.  So in my mind, this wasn’t really a “mistake,” but rather a temporary diversion along an equally interesting path.

I’ve been posting images regularly to my Twitter feed, @cre8math.  I haven’t even touched on the aesthetic qualities of these images — but suffice it to say that it has been a wonderful challenge to create interesting textures and color effects for a particular pair of angles.  Frankly, I am still amazed that such a simple algorithm — changing the two angle parameters used to create the Koch snowflake — produces such a wide range of intriguing mathematical and artistic objects.  You can be sure that I’m not finished exploring this amazing fractal world quite yet….

Creating Fractals II: Recursion vs. Iteration

There was such a positive response to last week’s post, I thought I’d write more about creating fractal images.  In the spirit of this blog, what follows is a mathematical “stream of consciousness” — that is, my thoughts as they occurred to me and I pursued them.  Or at least a close approximation — thoughts tend to jump very nonlinearly, and I do want the reader to be able to follow along….

Let’s begin at the beginning, with one of my first experiments.  Here, the counterclockwise turns are 80 degrees, and the clockwise turns are 140 degrees.

Day008koch+80-140One observation I had made in watching PostScript generate such images was that there was “overlap”:  the recursive algorithm kept going even if the image was completely generated.  Now the number of segments drawn by the recursive algorithm is a power of 4, since each segment is replaced by 4 others in the recursive process.  So if the number of segments needed to complete a figure is not a power of 4, the image generation has to be stopped in the middle of a recursive call.

This reminded me of something I had investigated years ago — the Tower of Hanoi problem.  This is a well-known example of a problem which can be solved recursively, but there is also an iterative solution.  So I was confident there had to be an iterative way to generate these fractal images as well.

I needed to know — at any step along the iteration — whether to turn counterclockwise or clockwise.  If I could figure this out, the rest would be easy.  So I wrote a snippet of code which implemented the recursive routine, and output a 0 if there was a counterclockwise turn, and a 1 if there was a clockwise turn.  For 2 levels of recursion, this sequence is

0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0.

The ones occur in positions 2, 6, 8, 10, and 14.

I actually looked at 1024 steps in the iteration, and noticed that the ones occur in exactly those positions whose largest power of 2 is odd.  Each of 2, 6, 10, and 14 has one power of 2, and 8 has three.

You might be wondering, “How did you notice that?”  Well, the iterative solution of the Tower of Hanoi does involve looking at the powers of 2 within numbers, so past experience suggested looking along those lines.  This is a nice example of how learning neat math can enlarge your mathematical “toolbox.”  You never know when something might come in handy….

There was other interesting behavior as well — but it’s simpler if you just watch the video to see what’s happening.

First, you probably noticed that each of the 18 star arms takes 32 steps to create.  And that some of the star arms — eight of them — were traversed twice.  This means that 18 + 8 = 26 arms were drawn before the figure was complete, for a total of 832 steps.  Note that the recursive algorithm would need 1024 steps to make sure that all 832 steps were traversed — but that means an overlap of 192 steps.

Now let’s see why some of the arms were traversed twice.  The 32nd step of the first arm is produced after 31 turns, and so the 32nd turn dictates what happens here.  Now the highest power of 2 in 32 is 5, which is odd – so a clockwise turn of 140 degrees is made.  You can see by looking at the first 33 steps that this is exactly what happens.  The 32nd step takes you back to the center, and then a 140 degree clockwise turn is made.

Day008Fractal33Now after the next arm is drawn, the turn is determined by the 64th angle.  But 6 is the highest power of two here, and so an 80 degree counterclockwise turn is made — but this takes you over the same arm again!

Day008Fractal65Note that we can’t keep traversing the same arm over and over.  If we add 32 to a number whose highest power of 2 is 6:

2^6m+2^5=2^5(2m+1),

we get a number whose highest power of 2 is 5 again (since 2m + 1 must be odd).  Since this power is odd, a clockwise turn will be made.

So when do we repeat an arm?  This will happen when we have a counterclockwise turn of 80 degrees, which will happen when the highest power of 2 is even (since an odd power takes you clockwise) — when looking at every 32nd turn, that is.  So, we need to look at turns

32, 64, 96, 128, 160, 192, 224, etc.

But observe that this is just

32 x (1, 2, 3, 4, 5, 6, 7, etc.).

Since 32 is an odd power of two, the even powers of two must occur when there is an odd power of 2 in 1, 2, 3, 4, 5, 6, 7, etc.  In other words, in positions 2, 6, 8, 10, 14, etc.

To summarize this behavior, we can state the following simple rule:  arms move seven points counterclockwise around the circle, except in the case of the 2nd, 6th, 8th, 10th, 14th, etc., arms, which repeat before moving seven points around.  Might be worth taking a minute to watch the video again….

We can use this rule to recreate the order in which the star arms are traversed.  Start with 1.  The next arm is 1 + 7 = 8.  But 8 is the 2nd arm, so it is repeated — and so 8 is also the third arm.  The fourth arm is 8 + 7 = 15, and the fifth is seven positions past 15, which is 4.  Mathematically, we say 15 + 7 = 4 modulo 18, meaning we add 15 and 7, and then take the remainder upon dividing by 18.  This is know as modular arithmetic, and is one of the first things you learn when studying a branch of mathematics called number theory.

The sixth arm is 4 + 7 = 11, which is repeated as the seventh arm.  You can go on from here….

There are still some questions which remain.  Why 32 steps to complete an arm?  Why skip every seventh arm?  Why are the arms 20 degrees apart?  These questions remain to be investigated more thoroughly.  But I can’t stress what we’re doing strongly enough — using the computer to make observations which can be stated mathematically very precisely, and then looking at a well-defined algorithm to (hopefully!) prove that our observations are accurate.  More and more — with the advent of technology — mathematics is becoming an experimental science.

I’ll leave you with one more video, which shows PostScript creating a fractal image.  But laying a mathematical foundation was important — so next week, we can look at how you can make your own fractals in Python using an iterative procedure.  This way, you can explore this fascinating world all on your own….

There are 10 levels of recursion here, and so 1,048,576 segments to draw.  To see the final image, visit my Twitter feed for October 9.  Enjoy!