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 78 days ago [-]
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.
susam 78 days ago [-]
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.
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.
Does aphyr even have comments, or is it a pure political protest?
That's the first thing that's tempted to break out an ssh tunnel - I can live without the occasional NSFW reddit group.
toast0 77 days ago [-]
They do show comments at the bottom of the posts.
AstroJetson 77 days ago [-]
Thanks for the memory reminder, I read them when they first came out. They are still highly amusing today!
arealaccount 78 days ago [-]
This would be an offer on the spot from me
n4r9 78 days ago [-]
A massively over-engineered, incorrect solution?
jiveturkey 78 days ago [-]
A candidate that appreciates the value of the question, yet won't subject themselves to the absurdity of demonstrating compliance.
Yes, very much yes.
n4r9 76 days ago [-]
I'd worry about them over-complicating solutions at work as well.
jiveturkey 70 days ago [-]
I definitely wouldn't want to work on your team, if that's how you interpret such an answer. Perfect interview then -- we've both eliminated the other as a viable employee/employer, so that's a win and we got there from just 1 trivial coding question. There's so much more to say here, but this is no longer timely, plus this isn't great forum for such discussion.
FWIW I have never been asked this question or similar, but since it's so famous I do have my own answer at the ready, which is just slightly more complex than the naive solution, but still well within the realm of production-worthy (maintainable, testable, readable) code. We don't really ever see any discussion of such because of course it isn't "interesting".
stronglikedan 78 days ago [-]
> 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.
darth_aardvark 78 days ago [-]
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.
toast0 77 days ago [-]
If the candidate didn't even show up to an interview, they're definitely not worth hiring. :p
NitpickLawyer 78 days ago [-]
> 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.
cyphar 77 days ago [-]
> For those that don't know, Fizz Buzz is less an aptitude test and more of an attitude test.
The articles which popularised FizzBuzz as an interview question stated as a categorical fact that most computer science graduates or programmer candidates (one article even said 199/200!![2]) cannot do FizzBuzz[1,2,3] and were absolutely recommending it as an aptitude test.
I personally think this whole thing was simply untrue back in 2007 (or at the very least incredibly overstated) and we are paying the price for it with ridiculous 15-stage interviews as a paranoid response to some urban legend from ~20 years ago.
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.
theendisney 77 days ago [-]
It would find a therapist contact your employer, your wife and your dad.
flir 77 days ago [-]
> LMAOOOOO OKAY SO THE POLYNOMIAL IS LITERALLY SHITTING ITSELF
That was a fun read, but I can see that persona quickly becoming wearing. I had a "talk like a wiki article" persona for a while that worked better (for me) than any attempt to inject personality. The greyer the better, when it comes to tools.
(Being a child of the internet rather than the classroom my abusive solution would be to look up the sequence in OEIS, but I think fizzbuzz could be encoded into an L-system quite neatly).
isoprophlex 77 days ago [-]
Yes, it's indeed very over the top and one-dimensional. However, I've been iterating on this system prompt since the early early days of chatgpt.com, and I find that I can't really chat with AI systems in their "grey", dry mode anymore.
On their default behavior they try too hard to make me like them, which I find intolerable. "You're absolutely right!" for some reason drives me insane; getting "lmaaoooo my bad fam i dun goofed" twenty times a day is equally annoying in terms of models being confidently wrong, but somehow the lazy shitbag attitude pisses me off less than the goody two shoes energy.
And if they're low on crazyness and you force them to be crisp and emotionless like a wikipedia article, I notice that I tend to trust them more... even though again the tendency to bullshit is unchanged, still there.
Somehow this really works for me.
Also when coding it makes it very clear which bits I haven't inspected yet because the comments and variable names will be super nsfw, thus keeping me on my toes as to not accidentally submit PRs filled with "unfuck_json()" functions.
flir 77 days ago [-]
> On their default behavior they try too hard to make me like them, which I find intolerable. "You're absolutely right!"
Yeah, that's what I was trying to avoid, too. Why do we have such strong negative reactions to sycophancy? I went for something like: "You are a maximally terse assistant with minimal affect. Be detailed and complete, but brief."
drob518 77 days ago [-]
I laughed so hard. Really curious what the pre-prompt was.
"there ya go homie, copy paste ready for whoever needs their ai to have some goddamn personality"
chaboud 76 days ago [-]
Oh man. This system prompt is everything I'm looking for in my coding agents. This shit should be fun. Let it be fun!
bmacho 76 days ago [-]
It could've solved the task instead of being wrong and spitting nonsense tho.
This is orthogonal to the style, still, if it realizes that it can use Python's arbitrary precision integers instead of floats then the problem becomes absolutely trivial. Fast, and numerically stable.
mikestaas 77 days ago [-]
absolute madlad
user070223 77 days ago [-]
Inspired by this post & TF comment I tried symbollic regression [0]
Basically it uses genetic algorithm to find a formula that matches known input and output vectors with minimal loss
I tried to force it to use pi constant but was unable
I don't have much expreience with this library but I'm sure with more tweaks you'll get the right result
from pysr import PySRRegressor
def f(n):
if n % 15 == 0:
return 3
elif n%5 == 0:
return 2
elif n%3 == 0:
return 1
return 0
n = 500
X = np.array(range(1,n)).reshape(-1,1)
Y = np.array([f(n) for n in range(1,n)]).reshape(-1,1)
model = PySRRegressor(
maxsize=25,
niterations=200, # < Increase me for better results
binary_operators=["+", "*"],
unary_operators=["cos", "sin", "exp"],
elementwise_loss="loss(prediction, target) = (prediction - target)^2",
with compleixty 22 loss: 0.000015800686
The first term is close to 2/3 * cos(2pi*n/3) which is featured in the actual formula in the article. the constant doesn't compare to 11/15 though
Great work, I really liked Susam's setup in the article:
> Can we make the program more complicated? The words 'Fizz', 'Buzz' and
> 'FizzBuzz' repeat in a periodic manner throughout the sequence. What else is
> periodic?
and then I'm thinking ..
> Trigonometric functions!
is a good start, but there are so many places to go!
pillars001 77 days ago [-]
HN is a great place to learn non-trivial things about trivial things, and that’s why I like it. My comment won’t add much to the discussion, but I just wanted to say that I learned something new today about a trivial topic I thought I already understood. Thank you, HN, for the great discussion thread.
ok123456 78 days ago [-]
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.
vincenthwt 75 days ago [-]
Background Context:
I am a machine vision engineer working with the Halcon vision library and HDevelop to write Halcon code. Below is an example of a program I wrote using Halcon:
* Generate a tuple from 1 to 1000 and name it 'Sequence'
tuple_gen_sequence (1, 1000, 1, Sequence)
* Replace elements in 'Sequence' divisible by 3 with 'Fizz', storing the result in 'SequenceModThree'
In this program, I applied a vectorization approach, which is an efficient technique for processing large datasets. Instead of iterating through each element individually in a loop (a comparatively slower process), I applied operations directly to the entire data sequence in one step. This method takes advantage of Halcon's optimized, low-level implementations to significantly improve performance and streamline computations.
layer8 78 days ago [-]
I think that implementation will break down around 2^50 or so.
siegelzero 78 days ago [-]
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
makerofthings 77 days ago [-]
There are a surprising number of ways to generate the fizzbuzz sequence. I always liked this one:
fizzbuzz n = case (n^4 `mod` 15) of
1 -> show n
6 -> "fizz"
10 -> "buzz"
0 -> "fizzbuzz"
fb :: IO ()
fb = print $ map fizzbuzz [1..30]
Someone 77 days ago [-]
So, there’s a similar way to do it with a function that produces one of the characters in “FizBu\nx” and a while true loop that
- increases i on every \n,
- prints i when that produces x, otherwise prints the character
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.
acheron 77 days ago [-]
You saw a Usenet post on Nov 12? 2025?
anthk 77 days ago [-]
IT and some music/literature niche newsgroups and some Paleonthology ones plus a few more are still alive.
jmclnx 77 days ago [-]
Forgot to mention, the subject was "Simple Programming Challenge"
jmclnx 77 days ago [-]
Yes, it was about fizzbuz
ivansavz 78 days ago [-]
This is very nice.
burnt-resistor 78 days ago [-]
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.)
pbsd 77 days ago [-]
This can be translated to the discrete domain pretty easily, just like the NTT. Pick a sufficiently large prime with order 15k, say, p = 2^61-1. 37 generates the whole multiplicative group, and 37^((2^61-2)/3) and 37^((2^61-2)/5) are appropriate roots of unity. Putting it all together yields
This involves 6 exponentiations by n with constant bases. Because in fizzbuzz the inputs are sequential, one can further precompute c^(2^i) and c^(-2^i) and, having c^n, one can go to c^(n+1) in average 2 modular multiplications by multiplying the appropriate powers c^(+-2^i) corresponding to the flipped bits.
burnt-resistor 77 days ago [-]
Integer exponentiation is still really, really expensive. 3-4 modulus operations and a few branches is a lot cheaper.
tantalor 78 days ago [-]
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.
susam 78 days ago [-]
> 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.'
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.
michaelcampbell 77 days ago [-]
> Sort of fun to muse whether almost all FizzBuzz implementations are a bit wrong.
They're only wrong if they provide output that isn't in the spec. Adding "bazz" isn't in the spec, and assuming that something indeterminate MIGHT come later is also not part.
Terretta 77 days ago [-]
Yep, that's how people answer.
Folks really really don't like thinking that "FizzBuzz" case maybe shouldn't be there, future extension or factor edit or no.
// And as long as we're just manually computing factor times factor and typing out the results for it like "FizzBuzz" we might as well just hardcode the whole series...
theendisney 77 days ago [-]
I think the reqirement should be to n digits. Then at least we can benchmark it.
78 days ago [-]
theendisney 77 days ago [-]
If we are going to be like that we should just increment a var by 3,5 or 7 and compare it rather than %3 as the later seems expensive.
Rendered at 13:04:10 GMT+0000 (Coordinated Universal Time) with Vercel.
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.
Here is the direct link to the new section on DFT: https://susam.net/fizz-buzz-with-cosines.html#dft
[0]: https://www.desmos.com/calculator/wgr3zvhazp
Also probably easy enough to encode as quantum superpositions.
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.
Does aphyr even have comments, or is it a pure political protest?
That's the first thing that's tempted to break out an ssh tunnel - I can live without the occasional NSFW reddit group.
Yes, very much yes.
FWIW I have never been asked this question or similar, but since it's so famous I do have my own answer at the ready, which is just slightly more complex than the naive solution, but still well within the realm of production-worthy (maintainable, testable, readable) code. We don't really ever see any discussion of such because of course it isn't "interesting".
> 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.
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.
The articles which popularised FizzBuzz as an interview question stated as a categorical fact that most computer science graduates or programmer candidates (one article even said 199/200!![2]) cannot do FizzBuzz[1,2,3] and were absolutely recommending it as an aptitude test.
I personally think this whole thing was simply untrue back in 2007 (or at the very least incredibly overstated) and we are paying the price for it with ridiculous 15-stage interviews as a paranoid response to some urban legend from ~20 years ago.
[1]: https://imranontech.com/2007/01/24/using-fizzbuzz-to-find-de... [2]: http://weblog.raganwald.com/2007/01/dont-overthink-fizzbuzz.... [3]: https://blog.codinghorror.com/why-cant-programmers-program/
https://github.com/taolson/Admiran/blob/main/examples/fizzBu...
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 was a fun read, but I can see that persona quickly becoming wearing. I had a "talk like a wiki article" persona for a while that worked better (for me) than any attempt to inject personality. The greyer the better, when it comes to tools.
(Being a child of the internet rather than the classroom my abusive solution would be to look up the sequence in OEIS, but I think fizzbuzz could be encoded into an L-system quite neatly).
On their default behavior they try too hard to make me like them, which I find intolerable. "You're absolutely right!" for some reason drives me insane; getting "lmaaoooo my bad fam i dun goofed" twenty times a day is equally annoying in terms of models being confidently wrong, but somehow the lazy shitbag attitude pisses me off less than the goody two shoes energy.
And if they're low on crazyness and you force them to be crisp and emotionless like a wikipedia article, I notice that I tend to trust them more... even though again the tendency to bullshit is unchanged, still there.
Somehow this really works for me.
Also when coding it makes it very clear which bits I haven't inspected yet because the comments and variable names will be super nsfw, thus keeping me on my toes as to not accidentally submit PRs filled with "unfuck_json()" functions.
Yeah, that's what I was trying to avoid, too. Why do we have such strong negative reactions to sycophancy? I went for something like: "You are a maximally terse assistant with minimal affect. Be detailed and complete, but brief."
"there ya go homie, copy paste ready for whoever needs their ai to have some goddamn personality"
This is orthogonal to the style, still, if it realizes that it can use Python's arbitrary precision integers instead of floats then the problem becomes absolutely trivial. Fast, and numerically stable.
((cos((x0 + x0) * 1.0471969) * 0.66784626) + ((cos(sin(x0 * 0.628323) * -4.0887628) + 0.06374673) * 1.1508249)) + 1.1086457
with compleixty 22 loss: 0.000015800686 The first term is close to 2/3 * cos(2pi*n/3) which is featured in the actual formula in the article. the constant doesn't compare to 11/15 though
[0] https://github.com/MilesCranmer/PySR
> Can we make the program more complicated? The words 'Fizz', 'Buzz' and
> 'FizzBuzz' repeat in a periodic manner throughout the sequence. What else is
> periodic?
and then I'm thinking ..
> Trigonometric functions!
is a good start, but there are so many places to go!
* Generate a tuple from 1 to 1000 and name it 'Sequence'
tuple_gen_sequence (1, 1000, 1, Sequence)
* Replace elements in 'Sequence' divisible by 3 with 'Fizz', storing the result in 'SequenceModThree'
tuple_mod (Sequence, 3, Mod)
tuple_find (Mod, 0, Indices)
tuple_replace (Sequence, Indices, 'Fizz', SequenceModThree)
* Replace elements in 'Sequence' divisible by 5 with 'Buzz', storing the result in 'SequenceModFive'
tuple_mod (Sequence, 5, Mod)
tuple_find (Mod, 0, Indices)
tuple_replace (SequenceModThree, Indices, 'Buzz', SequenceModFive)
* Replace elements in 'Sequence' divisible by 15 with 'FizzBuzz', storing the final result in 'SequenceFinal'
tuple_mod (Sequence, 15, Mod)
tuple_find (Mod, 0, Indices)
tuple_replace (SequenceModFive, Indices, 'FizzBuzz', SequenceFinal)
Alternatively, this process can be written more compactly using inline operators:
tuple_gen_sequence (1, 1000, 1, Sequence)
tempThree:= replace(Sequence, find(Sequence % 3, 0), Fizz')
tempFive:= replace(tempThree, find(Sequence % 5, 0), 'Buzz')
FinalSequence := replace(tempFive, find(Sequence % 15, 0), 'FizzBuzz')
In this program, I applied a vectorization approach, which is an efficient technique for processing large datasets. Instead of iterating through each element individually in a loop (a comparatively slower process), I applied operations directly to the entire data sequence in one step. This method takes advantage of Halcon's optimized, low-level implementations to significantly improve performance and streamline computations.
- increases i on every \n,
- prints i when that produces x, otherwise prints the character
(Disregarding rounding errors)
That would be fairly obfuscated, I think.
arr = [];
y = 0;
setInterval(()=>{arr[y]=x},10)
setInterval(()=>{x=y++},1000)
setInterval(()=>{x="fizz"},3000)
setInterval(()=>{x="buzz"},5000)
setInterval(()=>{x="fizzbuzz"},15000)
Anyway an interesting read.
(The divisions will get optimized away.)
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 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.'
I see a case for 3 * 5 in here:
Why?If we add 'Bazz' for mod 7, are we going to hardcode:
Or should we have done something like: 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.
They're only wrong if they provide output that isn't in the spec. Adding "bazz" isn't in the spec, and assuming that something indeterminate MIGHT come later is also not part.
Folks really really don't like thinking that "FizzBuzz" case maybe shouldn't be there, future extension or factor edit or no.
// And as long as we're just manually computing factor times factor and typing out the results for it like "FizzBuzz" we might as well just hardcode the whole series...