Algorithms, Recursion, and Fractals

Woke up to this facebook message expressing a late night math observation, and thought I would reply to everyone. (Names have been removed to protect the innocent).  


On Monday, July 9, 2012, Facebook wrote:

Random Student

Hey Mr. Roer, I have a sort of math question for you. I happened to look at my clock at 12:24 a.m. tonight, and in my brain automatically thought about how 1+2=3 and 2+4= 6 and how 3 is half of 6 just as 12 is half of 24. I then thought about how 48 is 4+8= 12 which is double of 6. So then I decided to be a math nerd for a minute and tried it going from 10-19. It worked with the other numbers to a degree, except for 15, 16, and 17. 15 just goes back and forth between 6 and 3 until you reach 480. 16 and 17 countdown (7 to 6, and 8 to 7) and then stop. So, my question is what is this? lol Or is it just coincidence?

Well, Random, I'm not exactly clear what your algorithm was (I think in your sleepiness your message ended up being a little less obvious than you might have thought it was) but I appreciate your curiosity and looking for fun patterns. I'll try to suggest a couple that came to mind while reading it.


The first is a simple "divisibility by nine" test -- if you add up all the digits in a number, and then repeat, and repeat until there is only one digit remaining, and that digit is 9, then the number is divisible by nine.  A related fact is the "divisibility by three" test -- if you add up all the digits and continue etc. and your final answer is either 3, 6, or 9, then the number is divisible by 3.  

Another algorithm that came to mind was the "hail stone numbers" which is a famous open question in math -- meaning the answer is still unknown. The algorithm is simple enough -- if a number is even, cut it in half, and if it is odd, multiply it by 3 and add 1. Starting with any number (that people have tried so far) these numbers all eventually cascade down to 1.  The open question is will EVERY number do that -- there's a lot of numbers (especially huge numbers of 50+ digits) that have not been tested, and I believe there is a million dollar prize available for anyone who can prove what would happen.  They're called the hailstone numbers because like hailstones, they go up and down and up and down and can grow really big, before eventually falling down to the ground.

A fun pattern I have written about before involves cubing the digits of a number, and adding them up, and continuing that process indefinitely. It can produce cycles of repeating numbers, or get sucked in and stuck on numbers like 153.  A similar concept is described in a video where this process is called "Happification".

In general, this type of operation, when you do something and then you use that result to do the same again and again and again, is called a recursive function. Recursion can produce all sorts of different things -- from endless loops that freeze up your computer, interesting "steady state" results like 1, and 153 described above, or even beautiful images such as these fractals:

If that last one looks familiar, its because it's very similiar to the shape a cauliflower has. Next time you eat one, zoom in on it and you'll see a similar pattern occurring at smaller and smaller sizes. In fact, using recursion is mankind's best (truest? most accurate?) way of "drawing" nature, and is used quite frequently to produce backgrounds for movies and computer games. If you have 17 minutes and are interested in this further, I highly suggest listening to the "master" and discoverer of fractals Benoit Mandlebrot give his last lecture -- one of TED talks I came across recently. (If you only have three minutes, then pick up at the 14:00 minute mark where he describes and shows pictures of his Mandlebrot set, the first image shown above.

Feel free to describe your particular algorithm in more detail if you want more input for me, or better yet, draw a map of the routes numbers take using your algorithm. For the best algorithms, I suggest listing just a few short rules or steps and seeing what happens -- there is often much chaos and craziness in even the simplest rules.