There was recently an article submitted on Lobsters, which discussed a pretty clever approach to the FizzBuzz problem using some number theory.
The approach is sufficient granted that each chosen FizzBuzz number is a distinct prime, but when we start involving composite numbers things begin to get a little hairy.
Some of the language used in the article led me to believe that the subtler details of this latter situation were overlooked. I aim to discuss those here.
The question was asked: does this [approach] hold true for every n we might choose?
The author seemed to imply throughout the text that the answer to this question is yes, but the answer is actually no, as we will work out.
Furthermore, the following claim was made:
The numbers chosen as factors do not need to be prime, but if one of them has another as a factor, some groups will not exist
.
The example that was given in this context involved choosing FizzBuzz numbers \(2\) and \(4\), so that numbers that are divisible by \(2\) yield \(Fizz\), and numbers that are divisible by \(4\) yield \(FizzBuzz\).
To the passing reader, this might makes sense. Clearly numbers that are divisible by \(4\) are divisible by both \(2\) and \(4\), and so we shouldn't expect to ever just see \(Buzz\).
This intuition is actually misleading in the sense that even though it seems logical at first, there are other things going on under the surface that don't really have much to do with sharing factors.
In fact, it isn't just the case that things get weird when the chosen FizzBuzz numbers share factors. It even happens when they are non-prime coprimes!
It's worth mentioning that this is actually my first personal technical blog post, and I can't think of a more fitting thing to write about than mathematics. I hope that there is some meaningful discussion as a result, and that folks gain something from reading along.
I want to emphasize that what follows is not an attack on the author of the linked article or their work, but instead just a critique / commentary on some of the mathematics used and explanations given.
As you make your way through this post, you'll notice that I have linked to a lot of external resources, and at times perhaps the explanations that I give might seem a bit handwavy, especially to readers who aren't familiar with the underlying mathematics.
The following content is already quite long, and if I were to go off into the weeds to explain every little detail, it would be much longer. The hope is that you will become curious where you want to be, and explore some of the topics discussed as necessary / desired.
That being said, I know that there is a lot being covered, and so if anything is not clear, I am open and looking forward to any ensuing discussions, whether it be via e-mail or in the comments on Lobsters.
I'm not going to restate the entire article here, and I will assume that you have at least skimmed through it and have a general understanding about what the proposed generalized FizzBuzz solution looks like.
I encourage you to play around with different FizzBuzz numbers and see what you come up with.
For the purposes of our discussion, I restate the proposed solution, albeit somewhat differently (I've added a bit more detail for context):
Given:
The author claims that we can define a function (which we'll call the FizzBuzz assignment function): \begin{equation} g(a) = \begin{cases} a & \text{if \(h(a) = 1 \;(\bmod\; N)\)}\\ f(n_i)\cdot f(n_{i+1})\cdot ... f(n_j) & \text{if \(h(a)\) implies that \(a\) is divisible by \(n_i,...,n_j\); \(i \leq j\),}\\ & \text{(note that when \(i = j\) we get the singular case, i.e. \(Fizz\))} \end{cases} \end{equation} where: \begin{equation} h(a) = a^e\;(\bmod\; N)\equiv \begin{cases} 0\;(\bmod\; N) & \text{if \(N\;\vert\; a\) (and so all \(n_1...n_k\) divide \(a\))}\\ r_{n_h,...,n_j}\;(\bmod\; N) & \text{if \(a\) is divisible by all \(n_i\) } \textit{except }\text{for \(n_h,...,n_j\)}\\ 1\;(\bmod\; N) & \text{if \(a\) is relatively prime to N (and so all \(n_1...n_k\))}\\ \end{cases} \end{equation} That supposedly provides a general solution to the FizzBuzz problem. Let's try out a few examples.
Note: The function construction claims are just that — claims. As we'll see, the prescribed means of construction doesn't hold true for all cases. In other words, we will see conditions on the right hand side start to fail.
Let's try out some values:
For \(a = 3\), calculating \(a^e\;(\bmod\; 15)=3^4 \;(\bmod\; 15)\) yields \(6\), so that \(g(a) = Fizz\). So far so good! Similarly, \(a = 5\), calculating \(a^e\;(\bmod\; 15)=5^4 \;(\bmod\; 15)\) yields \(10\), so that \(g(a) = Buzz\) as expected.
I'll leave it to you to verify that \(a = 15\) would lead us to \(FizzBuzz\).
Let's try an \(a\) that isn't completely obvious:
Let \(a = 3796875\). We can tell it's divisible by \(5\) because there is a \(5\) in the ones place. We can also tell that it
is divisible by \(3\) because the sum of the digits is divisible by \(3\) (if you're not familiar with this trick google
divisible by 3 trick
).
Our expected output, then, should be \(FizzBuzz\). Let's verify that:
\(a^4 \;(\bmod\; 15)=3796875^4 \;(\bmod\; 15)\) yields \(0\), so that \(g(a) = FizzBuzz\). Cool!
Let's see if we can try to understand what's going on in this case. \(n_1\) and \(n_2\) are both prime in the example, so we'll try to find out what we can determine from that:
Let \(n_1,n_2\in\mathbb{Z}^+\) be distinct primes, so that \(\phi(n_1)=n_1-1\) and \(\phi(n_2)=n_2-1\).
Then \(e = LCM(n_1-1,n_2-1)=(n_1-1)\cdot(n_2-1)=\phi(n_1n_2)\).
In order to get \(FizzBuzz\), we need \(a^e\;(\bmod\; n_1n_2)\equiv 0\;(\bmod\; n_1n_2)\). Let's suppose that this is the case. But then:
\(a^e\;(\bmod\; n_1n_2)\equiv 0\;(\bmod\; n_1n_2) \iff n_1n_2\;\vert\;a^e\iff n_1\;\vert\;a^e\) and \(n_2\;\vert\;a^e\iff n_1\;\vert\;a\) and \(n_2\;\vert\;a\)
That is to say, we only get \(FizzBuzz\) when both \(n_1\) and \(n_2\) divide \(a\).
In order to get neither, we need \(a^e\;(\bmod\; n_1n_2)\equiv 1\;(\bmod\; n_1n_2)\). Let's suppose that this is the case.
Recall that due to our choice of \(n_1\) and \(n_2\), we have \(e=\phi(n_2n_2)\). In other words Euler's Theorem applies. i.e.
\(a^e\;(\bmod\; n_1n_2)\equiv 1\;(\bmod\; n_1n_2)\iff a\) is relatively prime to \(n_1n_2\iff a\) is relatively prime to both \(n_1\) and \(n_2\).
So we get neither \(Fizz\) nor \(Buzz\) precisely when \(a\) is relatively prime to both \(n_1\) and \(n_2\).
Our discussion above implicitly shows that we get exactly one of \(Fizz\) or \(Buzz\) in the case that \(a\) is divisible by exactly one of \(n_1\) or \(n_2\), since otherwise one of the previous cases would apply.
To state differently, this happens exactly when \(a\) is congruent to neither \(0\;(\bmod\; n_1n_2)\) nor \(1\;(\bmod\; n_1n_2)\).
Now we need to construct \(h(a)\). Let's first deal with \(n_1=4\):
We need to figure out what \(a^8 \;(\bmod\; 64)\) is congruent to modulo \(64\) for any arbitrary \(a\in\mathbb{Z}^+\) which is divisible by \(n_1=4\). To do that, we solve the relation: \begin{equation} \begin{aligned} a^e=(4l)^8\equiv x\;(\bmod\; 64) \; \text{for some \(l,x\in\mathbb{Z}^+\)} \\ \end{aligned} \end{equation} \begin{equation} \implies 4^8l^8\equiv x\;(\bmod\; 64) \;\; \end{equation} Note that \(4^8\) is divisible by \(64\) (you can verify this with a calculator), and so by the properties of modular arithmetic: \begin{equation} 4^8l^8\equiv 0l^8=0\;(\bmod\; 64) \;\; \end{equation} Which implies that \(x\) is congruent to \(0\) modulo \(64\). Weird. Take a moment to digest that and see if you realize anything.
What this says is that for any \(a\in\mathbb{Z}^+\) that is divisible by \(4\), \(a^8\;(\bmod\; 64)\equiv 0\;(\bmod\; 64)\).
Try the above calculation for \(n_2\). What do you get? (spoiler: it's also \(0\))
We've stumbled upon one of the issues with the described approach — namely that there appear to be positive integers \(a\) for which \(a^e\;(\bmod\; N))\equiv 0\;(\bmod\; N)\), even when \(N\not{\vert} \;a\).
But this is normal, right? The author did mention in the case of \(2\) and \(4\) that some groups will not exist
if there are shared factors, and we have that here.
It turns out that the explanation isn't quite as simple as that.
For the above example, there is actually a stronger assertion to be made. It's not just that the resulting \(h(x)\) will yield \(0\) for multiples of \(4\) and \(16\), it does so for all multiples of \(2\), which translates into every multiple of \(2\) being assigned \(FizzBuzz\) under the described approach!
To understand why this is, consider the case where \(a\) is a multiple of \(2\). Then \(a = 2l\) for some \(l\in\mathbb{Z}^+\). Then: \begin{equation} a^8=(2l)^8=2^8l^8=256l^8\equiv 0l^8=0\;(\bmod\; 64) \;\; \end{equation} But wait a minute, how come in the example where \(n_1=2\) and \(n_2=4\) it seemed to work just fine — assigning \(Fizz\) to every multiple of \(2\) and \(FizzBuzz\) to every multiple of \(4\), which makes sense — what gives? Stay tuned :)
In this case, \(\phi(4)=2\) and \(\phi(9)=6\), so that \(e=LCM(2,6)=6\).
I'm going to skip through the rest of the derivation and just point out the following:
Let \(a=6\), then we get: \begin{equation} 6^6\;(\bmod 36)\;\equiv 46656\;(\bmod 36)\;\equiv 0\;(\bmod 36)\; \end{equation}
Here we have an integer \(6\), which is divisible by neither \(n_1\) nor \(n_2\) (which are relatively prime), yet still gets taken to \(0\) modulo \(36\).
I want to emphasize that \(n_1\) and \(n_2\) are relatively prime, because part of the explanation of the original claim was that if any of the \(n_i\) shared factors, then there could be issues.
We have shown here that that sharing factors isn't the only way for us to start having problems.
To understand why weird things happen with some FizzBuzz numbers and not others, we need to talk a bit about some of the properties of the mathematical structures defined on the integers modulo \(n\in \mathbb{Z}\).
For \(n\in\mathbb{Z}^+\), the set of integers modulo \(n\), denoted \(\mathbb{Z}/n\mathbb{Z} = \{\bar{1},\bar{2},...,\overline{n-1}\}\) give rise to the following mathematical structures: groups, rings, and in some situations, fields.
This isn't a course in abstract algebra, so I'll trust you to quickly read through these definitions and some examples of each, and I'll try to fill in the blanks where necessary.
For the purposes of our discussion, I recommend that you make sure that you have a decent understanding of what groups and rings are (when I say understanding I don't mean several semesters of group and ring theory; just understand the definitions and the intuition).
One of the intuitions for \(\mathbb{Z}/n\mathbb{Z}\) that I'd like to highlight has to do with (traditional) clocks. Consider \(n=12\), and the following single-handed clock:
\(12\) coincides with \(0 \;(\bmod\; 12)\)
Operations on integers modulo \(12\) are akin to sending the hour hand of the clock to different places.
For example, starting from \(0 \;(\bmod\; 12)\), we obtain the following sequence of clock states by performing each subsequent operation on the previous state:
Start with the hour hand on \(12\), i.e. \(0 \;(\bmod\; 12)\)
add 13 hours, which is equivalent to \(1\;(\bmod\; 12)\)
add 3 hours, which is equivalent to \(4\;(\bmod\; 12)\)
multiple by 3 hours, which is equivalent to \(0\;(\bmod\; 12)\)
This intuition generalizes (i.e. \(n\)-hour clocks), and you should keep it in mind throughout our discussion when we're talking about arithmetic operations modulo arbitrary \(n\).
You can find a more complete description of the integers moduluo \(n\) here.
Note: Sometimes we will leave the bar, i.e. \(\bar{1}\), off of the elements of the set of integers modulo \(n\) for brevity. The meaning should be clear from the context.
Note: The set \(\mathbb{Z}/n\mathbb{Z}\) is also referred to as the ring of integers modulo n.
Rings can have elements that are referred to as nilpotent:
If \(R\) is a ring, and \(r\in R\), \(r\) is said to be nilpotent if there exists some \(n\in\mathbb{Z}^+\) such that \(r^n = 0\in R\)
Let \(R = \mathbb{Z}/8\mathbb{Z}=\{\bar{0}, \bar{1}, \bar{2}, \bar{3}, \bar{4}, \bar{5}, \bar{6}, \bar{7}\}\). We want to know which elements of \(R\) are nilpotent:
As it turns out, there is a useful fact that could help us make some sense of this:
Let \(p_1,p_2,...p_k\in\mathbb{Z}^+\) be prime, \(r_1,r_2,...,r_k\in\mathbb{Z}^+\), and \(n=p_1^{r_1}\cdot p_2^{r_2}...\cdot p_2^{r_k}\).
An element \(r\in R=\mathbb{Z}/n\mathbb{Z}\) is nilpotent \(\iff\) \(\forall p_i\in\{p_1,p_2,...,p_k\}\), \(\;p_i\;\vert\;r\).
Suppose \(r\in R\) is nilpotent. Then \(\exists\; x\in \mathbb{Z}^+\) such that \(r^x = 0 \in R\)
This implies, then, that \(r^x\equiv 0 \;(\bmod n)\;\), i.e. \(n\;\vert\; r^x\). Therefore, if \(p_i\) is prime and \(p_i\;\vert\; n\), then \(p_i \;\vert\; r^x \implies p_i \;\vert\; r\).
Conversely, suppose that for \(n=p_1^{r_1}\cdot p_2^{r_2}...\cdot p_k^{r_k}\) and for some \(r\in R\), \(\forall p_i\in\{p_1,p_2,...,p_k\}\), \(\;p_i\;\vert\;r\).
Then \(r=p_1^{i_1}\cdot p_2^{i_2}\cdot...\cdot p_k^{i_k}\cdot a\), for \(i_1,i_2,...i_k,a\in\mathbb{Z}^+\).
Let \(x=max(\{r_1,r_2,...,r_k\})\). Therefore:
\(r^x = (p_1^{i_1}\cdot p_2^{i_2}\cdot...\cdot p_k^{i_k}\cdot a)^x = p_1^{i_1x}\cdot p_2^{i_2x}\cdot...\cdot p_k^{i_kx}\cdot a^x\)
But because of our choice of \(x\), we have \(p_j^{r_j} \leq p_j^{i_jx}\) for each \(p_j^{r_j}\) in the factorization of \(n\), and each \(p_j^{i_jx}\) in the factorization of \(r^x\).
Therefore, we can conclude that \(n\;\vert\; r^x\implies r^x\equiv 0 \;(\bmod n)\;\implies r\) is nilpotent in \(R\).
When our chosen \(n\in\mathbb{Z}^+\) is prime, \(R = \mathbb{Z}/n\mathbb{Z}\;\) has no non-zero nilpotent elements. Using our result above, it's relatively easy to see why this is the case.
Consider the case where \(n=7\). In this case, \(n\) has a single prime factor, namely \(7\). What non-zero elements of \(R\) have \(7\) among their prime factors? None of them.
Right, back to reality. Let's revisit our friends \(3\) and \(5\), both prime. Why does the outlined approach work for them?
You'll recall that we offered an explanation for why the outlined approach works in this case as a part of Example 1, but let's look at it from a different perspective.
Consider what non-zero elements of the resulting ring of integers modulo \(n=3\cdot 5=15\) are nilpotent. There aren't any!
This means that if we take any element \(r\) of the ring, and raise it to any power, we will never get \(0\) unless the element itself is \(0\). As it turns out, this is quite a nice property for helping to solve our FizzBuzz problem.
Since we know that we'll only get \(0\) if we raise \(0\) (that is, \(\bar{0}\) in the ring — i.e. any number divisble by \(n\)) itself to a power, we can say for a fact that under the original outlined approach, if our FizzBuzz assignment function spits out \(FizzBuzz\), then the number \(a\) must have been divisible by both \(3\) and \(5\).
Exercise: Determine what happens when there are prime powers in the factorization of \(n\) — i.e. \(p_i^{r_i}, r_i > 1\). Are there nilpotent elements? What do they look like?
Right, so, the plot thickens. Why does \(2\) only get assigned \(Fizz\)?
As it turns out, \(2\) is nilpotent in the ring of integers modulo \(n=2\cdot 4=8\) (we've proven that it should be!). However, the special selection of our exponent \(e\) is sort of hiding this from us, and preventing \(2\) from being taken to \(\bar{0}\) under \(\bmod 8\).
Remember that an element \(r\) in a ring is nilpotent if there exists an integer \(x\) such that \(r^x=0\). This doesn't mean that it holds for any integer.
A side effect of choosing our exponent \(e\) to be the least common multiple of \(\phi(2)\) and \(\phi(4)\) gives us \(e=2\), which just happens to be small enough so that \(2^e\neq 0\), which would be assigned \(FizzBuzz\) by our assignment function.
In other words:
The fact that this works has nothing to do with the generality of the solution, and everything to do with the exponent.
For large \(e\), the nilpotent elements in the ring \(\mathbb{Z}/n\mathbb{Z}\) become more apparent.
As our exponent \(e\) becomes larger — \(\phi(n_i)\) grows as each \(n_i\) grows, and thus \(e\), the least common multiple of the totients, also grows —, we will see nilpotent elements of certain rings go to \(0\) "faster" than in other rings.
Exercise: Up until this point we've talked about the nilpotent elements of the overall ring \(\mathbb{Z}/n\mathbb{Z}\), where \(n=n_1n_2...n_k\). What happens when an integer \(a\) is nilpotent in any of the rings \(\mathbb{Z}/n_i\mathbb{Z}\)?
At this point I suspect you're wondering. While I don't know for a fact the original author's motivations (though I am hoping that they respond and let me know!), I suspect that it has to do with the nice properties of Euler's totient.
In particular, Euler's Theorem states that if \(a,n\in\mathbb{Z}^+\) are relatively prime, then: \begin{equation} a^{\phi(n)}\equiv 1\;(\bmod n\;) \end{equation}
This makes sense, and we can see the use in the outlined approach. When a number satisfied the above relation, our FizzBuzz assignment function returned the number itself.
Otherwise, we calculate the other necessary rules to correctly map numbers to FizzBuzz string variations.
Note, however, that this says nothing about not incorrectly mapping numbers that aren't relatively prime to \(n\) to \(0\).
As we discussed above, this can happen to non-zero elements in rings whose moduli's prime factors are not distinct primes, each with exponent \(1\) in the factorization, and when our exponent \(e\) is large enough.
In other words, in rings with nilpotent elements and a sufficiently large \(e\), we can unintentionally map numbers that are not divisible by \(n\) to \(\bar{0}\) in the ring, in turn assigning \(FizzBuzz\) where we shouldn't.
Yes, so, I think that the intended point of that was to calculate value of the Carmichael's Function, \(\lambda(n)=LCM(\lambda(n_1)...\lambda(n_k))\), where \(n=n_1n_2...n_k\).
The outlined approach misses the step, however, where we need to divide \(\phi(n_i)\) by \(2\) in the case where \(n_i = 2^r, r>2\).
To make this long story short, in the case where all of the chozen FizzBuzz numbers are prime, the outlined approach works due to the reasons given at the end of Example 1, and more generally due to the fact the the resulting ring has no nilpotent elements.
The reason why it doesn't work in the general case with arbitrary FizzBuzz numbers has to do with the fact that resulting ring has nilpotent elements.
In certain rings, the nilpotency of elements will become clear more immediately than in other other rings, depending on the size of the exponent \(e\) that we have calculated using the outlined approach.
So we know that the originally outlined approach works for two prime FizzBuzz numbers.
Does it work for any number of FizzBuzz numbers
The answer is yes, and the proof is left as an exercise to the reader.
When you're dealing with FizzBuzz numbers that are distinct primes, the approach that was originally outlined works great. It's only when we start playing with composite numbers that things start to get difficult, as demonstrated above.
We have also shown that it is not enough for the FizzBuzz numbers to be relatively prime.
This I do not know. I may explore the problem further in the coming days, but for now the only general solutions that I can think of are the ones that we're most accustomed to seeing during programming interviews.
I thank you for taking the time out of your day to read along, and I hope that you found the content interesting. I am looking forward to any and all discussions that occur as a result, either in the comments on Lobsters, or if you would like to email me at:
ant at antfeedr dot com.
Cheers!