Well, there must be an obvious solution where the fizzbuzz sequence is seen as a spectrum of two frequencies (1/3 and 1/5), and a Fourier transform gives us a periodic signal with peaks of one amplitude at fizz spots, another amplitude at buzz spots, and their sum at fizzbuzz spots. I mean. that would be approximately the same solution as the article offers, just through a more straightforward mechanism.

▲

susam 6 hours ago | parent | next [-]

That is precisely how I began writing this post. I thought I'd demonstrate how to apply the discrete Fourier transform (DFT) but to do so for each of the 15 coefficients turned out to be a lot of tedious work. That's when I began noticing shortcuts for calculating each coefficient c_k based on the divisibility properties of k. One shortcut led to another and this post is the end result. It turns out it was far less tedious (and more interesting as well) to use the shortcuts than to perform a full-blown DFT calculation for each coefficient.

Of course, we could calculate the DFT using a tool, and from there work out the coefficients for the cosine terms. For example, we could get the coefficients for the exponential form like this:

https://www.wolframalpha.com/input?i=Fourier%5B%7B3%2C+0%2C+...

And then convert them to the coefficients for the cosine form like this:

https://www.wolframalpha.com/input?i=%7B11%2F15%2C+2*0%2C+2*...

That's certainly one way to avoid the tedious work but I decided to use the shortcuts as the basis for my post because I found this approach more interesting. The straightforward DFT method is perfectly valid as well and it would make an interesting post by itself.

▲

susam 2 hours ago | parent [-]

Update: I went ahead and added the method of obtaining the coefficients using DFT anyway. Like I mentioned above, this approach is quite tedious by hand, so I only work out the first few coefficients explicitly. In practice, these are almost always computed using numerical software. But for some people it may still be interesting to see a direct calculation rather than relying on shortcuts.

Here is the direct link to the new section on DFT: https://susam.net/fizz-buzz-with-cosines.html#dft

	▲	xbar 35 minutes ago \| parent [-]
		This is a joy.

▲

mr_wiglaf 5 hours ago | parent | prev | next [-]

Ah so taking the Fourier transform of this function[0]? The summation of the fizz and buzz frequencies don't lead to perfect peaks for the fizz and buzz locations. I need to revisit Fourier cause I would have thought the transform would have just recovered the two fizz and buzz peaks not the fizzbuzz spot.

[0]: https://www.desmos.com/calculator/wgr3zvhazp

▲

3 hours ago | parent | prev | next [-]

[deleted]

▲

atemerev 6 hours ago | parent | prev [-]

Yes. Exactly. This is how it _should_ have been done.

Also probably easy enough to encode as quantum superpositions.

	▲	HPsquared 5 hours ago \| parent [-]
		How would someone do FizzBuzz on a quantum computer? It seems like a nice toy example problem.