Euler's Fizzbuzz (2020)
philcrissman.net
Euler's Fizzbuzz (2020)
1–10 of 92 posts
Re: Euler's Fizzbuzz (2020)
#2This is a cute solution but I feel like the exposition makes it more mysterious seeming then necessary. If you have n%15, that's enough to do FizzBuzz on it's own, without having to take a fourth power. It's just then you need to map n%15=3,6,9,12 to "Fizz" instead of just 6. Taking the fourth power simplifies things because 3^4, 6^4, 9^4 and 12^4 all equal 6 (mod 15). And similarly for the multiples of 5. Though this explanation doesn't generalize as well.
Re: Euler's Fizzbuzz (2020)
#3This is of course a really neat solution, but the proof doesn't really give me much value as a reader.
I am much more interested in an explanation of how to find this solution, than a theoretical solution of why it is correct. Specifically I don't understand from the article why the trick of raising n to the power of LCM(phi(3), phi(5)) works.
Re: Euler's Fizzbuzz (2020)
#4The fundamental mathematical concepts revealed in this answer, especially the use of Euler's totient theorem, are worth pondering because it is this branch of modular arithmetic that Diffie and Hellman first proposed, and then Rivest, Shamir, and Adleman concretely used to produce, well, RSA:
https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Operation
Sadly, quantum supremacy may mean this form of cryptography will soon be dead, but this curious application is why modular arithmetic is a favorite of mine. It was a branch of math that historically had a few niche applications, and then in the 21st century became an underpinning to global capitalism.
Re: Euler's Fizzbuzz (2020)
#5Was this the expected answer to the coding interview question at places like Renaissance Technologies, Jane Street Capital, and Galois?
This is really funny. I had an intuition there must be a lambda function solution for fizzbuzz, but I don't do coding interviews and never pursued it. I can see why now, because it's waaay out of my skillset, but so neat to read.
Re: Euler's Fizzbuzz (2020)
#6This is of course a really neat solution, but the proof doesn't really give me much value as a reader. I am much more interested in an explanation of how to find this solution, than a theoretical solution of why it is correct. Specifically I don't understand from the article why the trick of raising n to the power of LCM(phi(3), phi(5)) works.
Because it doesn't :)
The author is trying to use Euler's theorem (if a, n are coprimes, then a^{\phi(n)} \equiv 1 \mod n), but the map defined by the exponentiation doesn't say anything about what happens when (a, n) are not coprime.
I'd encourage you to read this post, which is linked by the article: https://blog.antfeedr.com/posts/fizzbuzz.html.
Re: Euler's Fizzbuzz (2020)
#7The fundamental mathematical concepts revealed in this answer, especially the use of Euler's totient theorem, are worth pondering because it is this branch of modular arithmetic that Diffie and Hellman first proposed, and then Rivest, Shamir, and Adleman concretely used to produce, well, RSA: https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Operation Sadly, quantum supremacy may mean this form of cryptography will so…
> Sadly, quantum supremacy may mean this form of cryptography will soon be dead
I don't think it will be soon, but when it happens it won't necessarily be sad.
Re: Euler's Fizzbuzz (2020)
#8Was this the expected answer to the coding interview question at places like Renaissance Technologies, Jane Street Capital, and Galois? This is really funny. I had an intuition there must be a lambda function solution for fizzbuzz, but I don't do coding interviews and never pursued it. I can see why now, because it's waaay out of my skillset, but so neat to read.
The lambda's purpose here is only to turn it into a one-liner. It can be rewritten as
def fizzbuzz(n):
num_map = { 1: n, 6: "Fizz", 10: "Buzz", 0: "FizzBuzz" }
return num_map[n**4%15]
for i in range(100):
print(fizzbuzz(i + 1))
Re: Euler's Fizzbuzz (2020)
#9Was this the expected answer to the coding interview question at places like Renaissance Technologies, Jane Street Capital, and Galois? This is really funny. I had an intuition there must be a lambda function solution for fizzbuzz, but I don't do coding interviews and never pursued it. I can see why now, because it's waaay out of my skillset, but so neat to read.
The lambda's purpose here is only to turn it into a one-liner. It can be rewritten as def fizzbuzz(n): num_map = { 1: n, 6: "Fizz", 10: "Buzz", 0: "FizzBuzz" } return num_map[n**4%15] for i in range(100): print(fizzbuzz(i + 1)) The real skill would be to demonstrate that you know/remember/can apply Euler's totient theorem off-the-cuff in an interview!
I don't know about Jane Street or Galois, but Renaissance is full of mathematicians so I doubt they'd be impressed by Euler's theorem. Math students learn it in undergrad, it is considered basic.
Re: Euler's Fizzbuzz (2020)
#10Was this the expected answer to the coding interview question at places like Renaissance Technologies, Jane Street Capital, and Galois? This is really funny. I had an intuition there must be a lambda function solution for fizzbuzz, but I don't do coding interviews and never pursued it. I can see why now, because it's waaay out of my skillset, but so neat to read.
Yeah if I get asked fizzbuzz at an interview I'll really think less of the interviewer and will try to propose a solution like that ;)