Fizz Buzz as a problem in group theory
There is a famous programming interview problem that goes like this: Print out numbers 1 to 100. However, if for multiples of 3, replace it with “Fizz”, for multiples of 5, with “Buzz” and for numbers which are simultaneously multiples of 3 and 5, print “FizzBuzz”.
There standard solution to this problem (implemented in Python) is as follows:
The above works, but the style is implicit. Some thought needs to put in to the order of the conditionals. all(...) must come first, or else we will be printing “Fizz” (or “Buzz”) instead of “FizzBuzz” when i=15. Code like this while correct, makes it difficult to maintain because of the implicit dependency between the conditionals. If someone didn’t know about the FizzBuzz problem, he wouldn’t realize that you can’t shift the conditionals about because the code wouldn’t break if he did that. Dependencies which arise in the context of the requirements, and not explicitly in code are what makes code bug prone.
I think there is a better, more explicit way of solving this problem which highlights the inherent mathematical nature of this problem. And by appreciating the mathematical context, we get a more elegant way of implementing the FizzBuzz printer and remove implicit dependencies from the code.
The expected output from this program would look something like this:
1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16, 17, Fizz, 19, Buzz, Fizz, 22, 23, Fizz, Buzz, 26 ...But suppose we were to arrange the numbers in a tabular manner, wrapping to a new row after fifteen numbers. And, instead of starting from 1, we start from 0 and don’t print in the “Fizz”, “Buzz” and “FizzBuzz” replacements.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
45 ...Notice something interesting? Look at the first column. These are all the numbers which will be replaced by “FizzBuzz”.
FizzBuzz 1 2 3 4 5 6 7 8 9 10 11 12 13 14
FizzBuzz 16 17 18 19 20 21 22 23 24 25 26 27 28 29
FizzBuzz 31 32 33 34 35 36 37 38 39 40 41 42 43 44
FizzBuzz ...Basically, only the multiples of 15 are converted to “FizzBuzz”. Now, let’s see, which numbers will be converted to “Fizz” (excluding the first column).
0 1 2 Fizz 4 5 Fizz 7 8 Fizz 10 11 Fizz 13 14
15 16 17 Fizz 19 20 Fizz 22 23 Fizz 25 26 Fizz 28 29
30 31 32 Fizz 34 35 Fizz 37 38 Fizz 40 41 Fizz 43 44
45 ...Notice how they line up nicely, repeating every 3 columns? This is where “Buzz” would go
0 1 2 3 4 Buzz 6 7 8 9 Buzz 11 12 13 14
15 16 17 18 19 Buzz 21 22 23 24 Buzz 26 27 28 29
30 31 32 33 34 Buzz 36 37 38 39 Buzz 41 42 43 44
45 ...Observe how the “Buzz” columns repeats every 5 columns?
This can’t be a coincidence! And it should prompt us to ask, what is common about the numbers which were replaced by the fizzy adjectives. Does the fact that 15 = 3 x 5 have anything to do with this nice arrangement?
Actually it does! Let’s look at the Fizz columns. Let’s take the first Fizz column. The one replacing the numbers 3, 18, 33 and so on. Now I want you to add them to themselves. What do you get? 6, 36, 66 which is you check is in the second Fizz column! What if the first column was added 2 times instead. What do you get? 9, 54, 99 which is the third Fizz column. If you add the first column to itself 3 times, you get the fourth column.
Hmmm… Interesting. It’s like there’s a chain 1 -> 2 -> 3 -> 4 of Fizz columns. What happens if we add the first Fizz column to itself 4 times instead. 15, 60, 165 which turns out to be numbers the 1st FizzBuzz column! So, starting from the first Fizz column, we need multiply by 5 before we return to the FizzBuzz column. The complete chain looks like this 1 -> 2 -> 3 -> 4 -> FizzBuzz!
Ok, what if we start from the second Fizz column and repeat the self addition 1, 2, 3 and so on many times? The chain we obtain is (you can check) 2 -> 4 -> 1 -> 3 -> FizzBuzz! Once again, minimum multiplier is 5 before returning to the FizzBuzz.
Starting from the 3rd Fizz column, the chain is 3 -> 1 -> 4 -> 2 -> FizzBuzz! and for the 4th Fizz, the chain is 4 -> 3 -> 2 -> 1 -> FizzBuzz! In any case, Fizz columns need to be multiplied by at least 5 before returning to FizzBuzz.
This suggests to us that the FizzBuzz column is very special and that the Fizz columns have some common invariant, the minimum factor needed to multiply the column so that it becomes FizzBuzz.
That invariant is knowns as the order of the column. Fizz columns are order 5. What about the FizzBuzz column. Well, since it is already its own self, we can think of it returning to itself by multiplying 1. So FizzBuzz is order 1.
So what is the order of the Buzz column? You probably suspect that it is 3. And that would be absolutely correct. The chain is 1 -> 2 -> FizzBuzz! and 2 -> 1 -> FizzBuzz! .
What about numbers which are not going to be replaced? It is tedious to check, but their order is 15. It fact, the following formula helps us calculate the order of a number relative to 15.
order15(n) = 15 / GreatestCommonDivisor(15, n) Can you prove this?
What the exercise above shows is that numbers when wrapped around every 15 columns have a interesting internal structure. That structure is called a group. Each column represents an element in the group, and above, we have discussed an invariant, a unique property of elements in the group called the order of an element.
The implication for programming is that because the group elements have a unique order, we can use the order to distinguish which numbers are to be printed as “Fizz” , “Buzz”, “FizzBuzz” or just reprinted. And because these conditionals simply indicate which column the number belong to, it doesn’t matter how the conditionals are arranged in a if else construct. Our code would then be something like, if (column_order == e): print("something") .
The final solution looks something like this:
Structurally it looks the same as the first solution, but the main difference is…we don’t need to worry about causing bugs if the order of the conditionals are changed!
Group theory is one of the more abstract part of mathematics. But as you can see here, understanding the hidden properties of numbers does have practical implications to real life. What other facts about numbers can you think of that impacts your life today?
