Euler’s Fizzbuzz

FizzBuzz is a common coding problem of the sort asked in technical screenings or interviews. It goes something like this:

Write a function to list the integers from 1 to 100, but for every multiple of 3, write “Fizz”, and for every multiple of 5, write “Buzz”. For numbers which are multiples of both 3 and 5, it should write “FizzBuzz”; for every other number, it should print the number unchanged.

It is possible to write a function which uses no conditional logic at all, but which uses math to separate integers into 4 possible categories: The usual solution is left as an exercise for the interested reader.

  1. Those which have 3 as a factor, but not 5
  2. Those which have 5 as a factor, but not 3
  3. Those which have both 3 and 5 as a factor
  4. Those which have neither 3 nor 5 as factors

We want a function that will return

Consider an implementation of such a function in python:

[(lambda n: { 1: n, 6: "Fizz", 10: "Buzz", 0: "FizzBuzz" }[n**4%15])(n+1) for n in range(100)]

The same function in ruby:

(1..100).map{|n| {1 => n, 6 => "Fizz", 10 => "Buzz", 0 => "FizzBuzz"}[n**4%15] }

As expected, each of these returns a list of the integers from 1 to 100 with “Fizz”, “Buzz”, or “FizzBuzz” substituted in the correct spots.

But why? Where do the constant values 0, 6, 10, and 1 come from? Why does $n^4 \mod 15$ return 6 for multiples of 3 but not 5, 10 for multiples of 5 but not 3, 0 for multiples of 5 and 3, and 1 otherwise? Most important, does this hold true for every $n$ we might choose?

I. $n^4 \mod 15$ solves FizzBuzz

The proposition is:

$$n^4 \mod {15} = \begin{cases} 0, & \text{if $n$ is divisible by 3 and 5} \newline 6, & \text{if $n$ is divisible by 3 and coprime to 5} \newline 10, & \text{if $n$ is divisible by 5 and coprime to 3} \newline 1, & \text{if $n$ is coprime to 3 and 5} \end{cases}$$

The first case is trivial; if n has both 3 and 5 as factors, then raising n to any power and returning the result $\mod 15$ will always be 0, as any integer with both 3 and 5 as factors is also a multiple of 15 $(3 * 5)$.

For the second case, we have 3 as a factor of some constant c:

$$3c^4 \equiv 6 \pmod{15}$$

or

$$3c^4 \mod 15 = 6$$

for every constant c > 0 as long as c is coprime to 5. (If c is not coprime to 5, we have the first case, which will return 0.)

To begin, suppose $c = 1$. This gives $3^4 \mod 15$, or $81 \mod 15$, which will return 6: $15 * 5 = 75$, leaving a remainder of 6 from 81.

Suppose c is an integer > 1. Applying the exponent to each factor and making use of the identity $(ab) = (a + a(b - 1))$:

\begin{aligned} 3^4c^4 & \mod 15 \newline 81c^4 & \mod 15 \newline (81 + 81(c^4 - 1)) & \mod 15 \end{aligned}

Consider the expression $c^4$ by itself for a moment. We know from Euler’s totient theorem Euler’s totient theorem is that $a^{ϕ(n)} \equiv 1 (\mod n)$ where $a$ is coprime to $n$ and $ϕ$ is Euler’s totient function; the totient function of $n$ returns the number of integers less than $n$ that are coprime to $n$. For every prime number $p$, $ϕ(p)$ is equal to $p - 1$. A photo of Leonhard Euler
Figure Leonhard Euler that since c is coprime to 5, $c^4 \mod 5$ is equal to 1; if $c^4 / 5$ has a remainder of 1, then it must be the case that $c^4 - 1$ divides evenly by 5; that is, no matter what c is, if it is coprime to 5 then $(c^4 - 1)$ has 5 as a factor. The other factor is not significant, so let’s rewrite $(c^4 - 1)$ as $5x$.

\begin{align} (81 + 81(5x)) &\mod 15 \newline (81 \mod 15 + 81(5x) \mod 15) &\mod 15 \newline (6 + 81(5x) \mod 15) &\mod 15 \newline 6 \mod 15 \end{align}

We can rewrite this in (2) because a property of modular expressions is $(a + b) \mod n = (a \mod n + b \mod n) \mod n$.

In line (3), the expression $81(5x)$ has both 3 and 5 as factors, so $81(5x) \mod 15 = 0$, which gives us $6 \mod 15$, which is 6.

So for any c coprime to 5 and > 1, $3c^4 \mod 15$ will return 6.

The same process finds that $5c^4 \mod 15$ will always return 10; for c = 1, we have $625 \mod 15$, which is 10. Again, for $c > 1$ (coprime to 3), we can write

$$(625 + 625(c^4 - 1)) \mod 15$$

Euler’s totient theorem tells us that if c is coprime to 3, then $c^2 \equiv 1 \mod 3$; but we have $c^4$. However, $c^4$ is $c^2c^2$, and since $ab \mod n = ((a \mod n)( b \mod n)) \mod n$, $c^4 \mod 3$ is also 1.

Again, if $c^4 \equiv 1 (\mod 3)$ then $(c^4 - 1)$ divides evenly by 3 and had 3 as a factor. This again reduces the 2nd term to 0, leaving $625 \mod 15$, which again is 10.

This leaves the case where we have some number c which is coprime to both 3 and 5. If c is 1, we have $1 \mod 15$, which is 1.

If c > 1, we can again write this as $(1 + (c^4 - 1)) \mod 15$. Since we know that if c is coprime to both 3 and 5, and $c^4 \equiv 1 (\mod 3)$ and $c^4 \equiv 1 (\mod 5)$, then $(c^4 - 1)$ has both 3 and 5 as factors. So again,

\begin{aligned} (1 + (c^4 - 1)) &\mod 15 \newline (1 \mod 15 + (c^4 - 1) \mod 15) &\mod 15 \newline (1 + 0) &\mod 15 \newline 1 &\mod 15 \newline 1 \end{aligned}

So $n^4 \mod 15$ will always return 0 if both 3 and 5 are factors of n, 6 if 3 is a factor but not 5, 10 if 5 is a factor but not 3, and 1 if n is coprime to both 3 and 5, and a function like ->(n){ {1 => n, 6 => "Fizz", 10 => "Buzz", 0 => "FizzBuzz"}[n**4%15] } will always return a correct FizzBuzz result for every $n$ Up until $n^4$ overflows the integer type used by a given computer. .

II. Solving any FizzBuzz-category problem

A similar function can be created for any similar problem, which I’ll call FizzBuzz-category problems FizzBuzz-category problems: e.g., print “Foo” for multiples of 2, “Bar” for multiples of 3, “Baz” for multiples of 5, and a concatenate each word for numbers which have more than one of 2,3, or 5 as factors . 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. For example, if we chose to modify FizzBuzz such that multiples of 2 return “Fizz”, and multiples of 4 return “Buzz” (instead of the traditional 3 and 5), we will see “Fizz” for any multiple of 2, “FizzBuzz” for any multiple of both 2 and 4, but we will never see “Buzz” alone, as there is no multiple of 4 which is coprime to 2. The general solution presented below is not quite as general as I implied here: there are many number pairs for which is will not work well; so the factors must actually be chosen much more specifically. It will work for distinct primes, but not so well for composite numbers. I’d like to thank the author of this very well explained post, which goes into some detail about why the general formula will not work for composite numbers.

The equation used to solve FizzBuzz above can also be written

$$n^{LCM(ϕ(3),ϕ(5))} \mod (3 \cdot 5)$$

where $ϕ$ is Euler’s totient function, and $LCM$ is the least common multiple.

Generalized, for any set of $k$ factors $n_1,n_2,..n_k$ for which we want a FizzBuzz-like function, we can use the formula:

$$n^{LCM(ϕ(n_1),ϕ(n_2),..ϕ(n_k))} \mod \prod_{i=1}^k n_i$$

For a FizzBuzz-like function which returns “Foo” for multiples of 7 and “Bar” for multiples of 11, find:

$$n^{LCM(ϕ(7),ϕ(11))} \mod (7 \cdot 11)$$

$ϕ(7)$ is 6 and $ϕ(11)$ is 10, and the $LCM$ of 6 and 10 will be 30. So the equation will be:

$$n^{30} \mod 77$$

An implementation in python:

[(lambda n: { 1: n, 7**30%77: "Foo", 11**30%77: "Bar", 0: "FooBar" }[n**30%77])(n+1) for n in range(100)]

This gives the expected result:

[1, 2, 3, 4, 5, 6, 'Foo', 8, 9, 10, 'Bar', 12, 13, 'Foo', 15, 16, 17, 18, 19, 20, 'Foo', 'Bar', 23, 24, 25, 26, 27, 'Foo', 29, 30, 31, 32, 'Bar', 34, 'Foo', 36, 37, 38, 39, 40, 41, 'Foo', 43, 'Bar', 45, 46, 47, 48, 'Foo', 50, 51, 52, 53, 54, 'Bar', 'Foo', 57, 58, 59, 60, 61, 62, 'Foo', 64, 65, 'Bar', 67, 68, 69, 'Foo', 71, 72, 73, 74, 75, 76, 'FooBar', 78, 79, 80, 81, 82, 83, 'Foo', 85, 86, 87, 'Bar', 89, 90, 'Foo', 92, 93, 94, 95, 96, 97, 'Foo', 'Bar', 100]

Conclusion

So

$$a^{LCM(ϕ(n_1),ϕ(n_2),..ϕ(n_k))} \equiv \begin{cases} 0\pmod {\prod_{i=1}^k n_i}, & \text{if $n$ is divisible by every $n_1,n_2,..n_k$} \newline r_1,r_2,..r_k\pmod {\prod_{i=1}^k n_i}, & \text{a distinct result for every other combination of factors in $n_1,n_2,..n_k$} \newline 1\pmod {\prod_{i=1}^k n_i}, & \text{if $n$ is coprime to every $n_1,n_2,..n_k$} \end{cases}$$

… if the numbers $n_1, n_2,.. n_k$ are distinct primes. Again, thanks to the author of this post for illustrating this so clearly.

The author makes no assertion that there is any practical application for this formula other than as a solution to FizzBuzz-category problems with arbitrary integers chosen as candidates.