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.
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:
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.
Could you elaborate on why the Fourier transform of cos(x/3) + cos(x/5) (I assume that's what you mean by "spectrum of two frequencies") yields a periodic signal? It seems to me that one would get exactly 4 peaks, at +-1/3 and +-1/5 respectively.
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.
There was another great satirical take on FizzBuzz which had something to do with runes and incantation and magical spells...? I sort of remember that the same author maybe even wrote a follow up? to this extremely experienced developer solving FizzBuzz in the most arcane way possible.
> me: It's more of a "I can't believe you're asking me that."
> interviewer: Great, we find that candidates who can't get this right don't do well here.
> me: ...
Shit attitude from that candidate, considering the interviewer is completely correct. I wouldn't hire them since they are obviously a problem employee.
For those that don't know, Fizz Buzz is less an aptitude test and more of an attitude test. That's why this candidate failed and didn't get the job.
> Fizz Buzz is less an aptitude test and more of an attitude test
The amount of (highly credentialed) interviewees that can't 0-shot a correct and fully functional fizzbuzz is also way higher than a lot of people would think. That's where the attitude part also comes in.
I once had a coworker who used the FFT to determine whether coordinates formed a regular 2D grid. It didn't really work because of the interior points.
What a neat trick. I'm thinking you can abuse polynomials similarly. If the goal is to print the first, say, 100 elements, a 99-degree polynomial would do just fine :^)
EDIT: the llm gods do recreational mathematics as well. claude actually thinks it was able to come up with and verify a solution...
That's the most expletive-laden LLM output I've ever seen. ChatGPT would have aborted half way through to protect its pure and unsullied silicon mind from the filthy impure thoughts.
Very cool! There's definitely some similarity to Ramanujan Sums, though the approach here sort of packages the fizz-buzz divisibility properties into one function.
https://en.wikipedia.org/wiki/Ramanujan%27s_sum
While it's cute use of mathematics, it's extremely inefficient in the real world because it introduces floating point multiplications and cos() which are very expensive. The only thing it lacks is branching which reduces the chances of a pipeline stall due to branch prediction miss.
> There are several mentions of "closed-form expression" without precisely defining what that means, only "finite combinations of basic operations".
There is no universal definition of 'closed-form expression'. But there are some basic operations and functions that are broadly accepted, and they are spelled out directly after the 'finite combinations' phrase you quoted from the post. Quoting the remainder of that sentence here:
'[...] finite combinations of basic operations such as addition, subtraction, multiplication, division, integer exponents and roots with integer index as well as functions such as exponentials, logarithms and trigonometric functions.'
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.
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.
Could you elaborate on why the Fourier transform of cos(x/3) + cos(x/5) (I assume that's what you mean by "spectrum of two frequencies") yields a periodic signal? It seems to me that one would get exactly 4 peaks, at +-1/3 and +-1/5 respectively.
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
Yes. Exactly. This is how it _should_ have been done.
Also probably easy enough to encode as quantum superpositions.
How would someone do FizzBuzz on a quantum computer? It seems like a nice toy example problem.
https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/
There was another great satirical take on FizzBuzz which had something to do with runes and incantation and magical spells...? I sort of remember that the same author maybe even wrote a follow up? to this extremely experienced developer solving FizzBuzz in the most arcane way possible.
Does this ring a bell for anyone?
---
Found it!
https://aphyr.com/posts/340-reversing-the-technical-intervie...
https://aphyr.com/posts/341-hexing-the-technical-interview
https://aphyr.com/posts/342-typing-the-technical-interview
https://aphyr.com/posts/353-rewriting-the-technical-intervie... (the FizzBuzz one)
https://aphyr.com/posts/354-unifying-the-technical-interview
wow.
One of my favorite blog posts of all time: https://aphyr.com/posts/342-typing-the-technical-interview
Along that line, an over-engineered fizzBuzz using lazy list operations:
https://github.com/taolson/Admiran/blob/main/examples/fizzBu...
This would be an offer on the spot from me
A massively over-engineered, incorrect solution?
A candidate that appreciates the value of the question, yet won't subject themselves to the absurdity of demonstrating compliance.
Yes, very much yes.
> me: It's more of a "I can't believe you're asking me that."
> interviewer: Great, we find that candidates who can't get this right don't do well here.
> me: ...
Shit attitude from that candidate, considering the interviewer is completely correct. I wouldn't hire them since they are obviously a problem employee.
For those that don't know, Fizz Buzz is less an aptitude test and more of an attitude test. That's why this candidate failed and didn't get the job.
For those that don't know even more, this interview never happened and this interviewer doesn't exist. It's a funny joke on the internet.
> Fizz Buzz is less an aptitude test and more of an attitude test
The amount of (highly credentialed) interviewees that can't 0-shot a correct and fully functional fizzbuzz is also way higher than a lot of people would think. That's where the attitude part also comes in.
I once had a coworker who used the FFT to determine whether coordinates formed a regular 2D grid. It didn't really work because of the interior points.
What a neat trick. I'm thinking you can abuse polynomials similarly. If the goal is to print the first, say, 100 elements, a 99-degree polynomial would do just fine :^)
EDIT: the llm gods do recreational mathematics as well. claude actually thinks it was able to come up with and verify a solution...
https://claude.ai/share/5664fb69-78cf-4723-94c9-7a381f947633
That's the most expletive-laden LLM output I've ever seen. ChatGPT would have aborted half way through to protect its pure and unsullied silicon mind from the filthy impure thoughts.
I think that implementation will break down around 2^50 or so.
Very cool! There's definitely some similarity to Ramanujan Sums, though the approach here sort of packages the fizz-buzz divisibility properties into one function. https://en.wikipedia.org/wiki/Ramanujan%27s_sum
While it's cute use of mathematics, it's extremely inefficient in the real world because it introduces floating point multiplications and cos() which are very expensive. The only thing it lacks is branching which reduces the chances of a pipeline stall due to branch prediction miss.
(The divisions will get optimized away.)
I wonder where this is coming from. I saw on USENET in comp.os.linux.misc a conversation about fizzbuzz too. That was on Nov 12.
Anyway an interesting read.
Where the madness leads: https://cspages.ucalgary.ca/~robin/class/449/Evolution.htm
There are several mentions of "closed-form expression" without precisely defining what that means, only "finite combinations of basic operations".
TFA implies that branches (if statements and piecewise statements) are not allowed, but I don't see why not. Seems like a basic operation to me.
Nevermind that `s[i]` is essentially a piecewise statement.
> There are several mentions of "closed-form expression" without precisely defining what that means, only "finite combinations of basic operations".
There is no universal definition of 'closed-form expression'. But there are some basic operations and functions that are broadly accepted, and they are spelled out directly after the 'finite combinations' phrase you quoted from the post. Quoting the remainder of that sentence here:
'[...] finite combinations of basic operations such as addition, subtraction, multiplication, division, integer exponents and roots with integer index as well as functions such as exponentials, logarithms and trigonometric functions.'
This is very nice.