Solving Fizz Buzz with Cosines

This is very nice.

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.

This would be an offer on the spot from me

> 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.'

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

> 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.

I think that implementation will break down around 2^50 or so.

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.

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.

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

Also probably easy enough to encode as quantum superpositions.

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 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.

A massively over-engineered, incorrect solution?

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.

How would someone do FizzBuzz on a quantum computer? It seems like a nice toy example problem.

Where the madness leads: https://cspages.ucalgary.ca/~robin/class/449/Evolution.htm

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

A candidate that appreciates the value of the question, yet won't subject themselves to the absurdity of demonstrating compliance.

Yes, very much yes.

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...

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 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.

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.)

The article conceit is fantastic. That said, is the going-in algo wrong?

I see a case for 3 * 5 in here:

  for n in range(1, 101):
      if n % 15 == 0:
          print('FizzBuzz')
      elif n % 3 == 0:
          print('Fizz')
      elif n % 5 == 0:
          print('Buzz')
      else:
          print(n)

Why?

If we add 'Bazz' for mod 7, are we going to hardcode:

  for n in range(1, 105):
      if n % 105 == 0:          # 3 * 5 * 7
          print('FizzBuzzBazz')
      elif n % 15 == 0:         # 3 * 5
          print('FizzBuzz')
      elif n % 21 == 0:         # 3 * 7
          print('FizzBazz')
      elif n % 35 == 0:         # 5 * 7
          print('BuzzBazz')
      elif n % 3 == 0:
          print('Fizz')
      elif n % 5 == 0:
          print('Buzz')
      elif n % 7 == 0:
          print('Bazz')
      else:
          print(n)

Or should we have done something like:

  for n in range(1, 105):
      out = ''
  
      if n % 3 == 0:
          out += 'Fizz'
      if n % 5 == 0:
          out += 'Buzz'
      if n % 7 == 0:
          out += 'Bazz'
  
      print(out or n)

I've been told sure, but that's a premature optimization, 3 factors wasn't in the spec. OK, but if we changed our minds on even one of the two factors, we're having to find and change 2 lines of code ... still seems off.

Sort of fun to muse whether almost all FizzBuzz implementations are a bit wrong.

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

By the way, the topic of extending the solution to include numbers divisible by 7 came up in the comments section of my post here: <https://susam.net/comments/fizz-buzz-with-cosines.html>. My response, in the context of the approach in this post, can be found in the second comment there.