Euler's Fizzbuzz (2020)

That was fun!<p>Not that anyone cares for FizzBuzz but I&#x27;ll just note that n**4%15 is more efficiently written using the 3 argument pow function in python, eg pow(n, 4, 15).<p><pre><code> &gt;&gt;&gt; timeit(&quot;(1&lt;&lt;100000000)**4%15&quot;, number=1) 1.5620321459136903 &gt;&gt;&gt; timeit(&quot;pow(1&lt;&lt;100000000, 4, 15)&quot;, number=1) 0.05834826407954097 &gt;&gt;&gt; </code></pre> If n gets large then n**4 is very large so the % 15 has to deal with a big number. pow runs the modulo operation at the same time as the power operation so the intermediates never get bigger than 15.<p><a href="https:&#x2F;&#x2F;docs.python.org&#x2F;3&#x2F;library&#x2F;functions.html#pow" rel="nofollow">https:&#x2F;&#x2F;docs.python.org&#x2F;3&#x2F;library&#x2F;functions.html#pow</a>

This is a cute solution but I feel like the exposition makes it more mysterious seeming then necessary. If you have n%15, that&#x27;s enough to do FizzBuzz on it&#x27;s own, without having to take a fourth power. It&#x27;s just then you need to map n%15=3,6,9,12 to &quot;Fizz&quot; 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&#x27;t generalize as well.

Not sure how this came back around into the zeitgeist today, but this is my post from awhile back. Thanks to all who had nice things to say about it.<p>I&#x27;m definitely an amateur mathematician, though I tried my best to write the post like I think I&#x27;d try to write a proof. It came about because I stumbled across the equation, but I did not know _why_ it worked, so I was semi-obsessed with figuring out the _why_ for a long time.<p>I have nothing else to promote, haven&#x27;t even put anything on the site since this one and only post... Anyways, thanks, news-YC.

The fundamental mathematical concepts revealed in this answer, especially the use of Euler&#x27;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:<p><a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;RSA_(cryptosystem)#Operation" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;RSA_(cryptosystem)#Operation</a><p>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.

Neat trick, the only issue I see is mis-selling the idea that no conditionals are used ... map on it&#x27;s own (independently how it&#x27;s implemented) is a conditional. Also, if you break down how mod can be implemented, it definitely requires conditionals. In terms of the computational overhead this is way worse than just going for mod 15 and then mapping every of the possible 15 results to Fizz, Buzz or FizzBuzz.

This is of course a really neat solution, but the proof doesn&#x27;t really give me much value as a reader.<p>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&#x27;t understand from the article why the trick of raising n to the power of LCM(phi(3), phi(5)) works.

The 3c^4 ≡ 6 (mod 15) line is missing parentheses... As written, it means 3 * (c^4) ≡ 6 (mod 15), which is demonstrably false (e.g. 3 * (4^4) = 768 ≡ 3 (mod 15)).

I would do this:<p>Let i = ((n % 3) == 0) | ((n % 5) == 0) &lt;&lt; 1<p>Then map output as { n, &#x27;Fizz&#x27;, &#x27;Buzz&#x27;, &#x27;FizzBuzz&#x27; }

Maybe I&#x27;m being old and grumpy, but is there really a point to writing python without conditional logic? Each operation is going to have all sorts of stuff going in the interpreter, and the amount of code being executed that tiny snippet is way more than one would expect.

You can be even more ridiculous:<p><pre><code> char ds[5]; char * words[4] = {ds, &quot;Fizz\n&quot;, &quot;Buzz\n&quot;, &quot;FizzBuzz\n&quot;}; for (i = 1; i &lt; 101; ++i) { sprintf(ds, &quot;%d\\n&quot;, i) printf(words[((i*i*i*i)%15)&#x2F;4]); }</code></pre>

if you want to practice programming and like mathematics, you should try Project Euler *<p>* heh! <a href="https:&#x2F;&#x2F;projecteuler.net" rel="nofollow">https:&#x2F;&#x2F;projecteuler.net</a>

Fizzbuzz question has a nuance that is not acknowledged by many. Read the question carefully.<p>It should solve:<p>3: fizz<p>5: buzz<p>15: fizzbuzzfizzbuzz<p>Why is this?<p>15 is divisible by 3<p>15 is divisible by 5<p>15 is divisible by 3 and 5<p>All three statements in the description are true. You never said they were mutually exclusive.

Good luck running ^4 on larger numbers and overflowing integer &#x2F; long bounds orders of magnitude faster than the plain &quot;boring&quot; solutions

Was this the expected answer to the coding interview question at places like Renaissance Technologies, Jane Street Capital, and Galois?<p>This is really funny. I had an intuition there must be a lambda function solution for fizzbuzz, but I don&#x27;t do coding interviews and never pursued it. I can see why now, because it&#x27;s waaay out of my skillset, but so neat to read.

I hope I remember this for the next time I have to answer fizzbuzz in an interview