11 ms·

Euler's Fizzbuzz (2020)

212 points by koevet 6y ago

tgb 6y ago
This 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.
- kingaillas 6y ago
  His point was writing a function without conditional logic, and then of course generalizing to any "fizzbuzz category" problem. I thought it was a fantastic post on a extremely well trodden subject, up there with solving fizzbuzz in Tensorflow post. (https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/ https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/)
  - LanceH 6y ago
    My entry to use random-isn't-random: https://github.com/LanceH/fizzbuzz/blob/master/fb.go https://github.com/LanceH/fizzbuzz/blob/master/fb.go I feel like I need to revisit after seeing tensorflow and Euler. I need to find some way of making the lucky number using things around a room, like a mentalist or something. Some other subversive ones I've seen of are the java enterprise version, and several that import a fizzbuzz library and just run.
    - isaacimagine 6y ago
      I find that random-not-random implementation pretty incredible.
      - LanceH 6y ago
        Thanks. It seems kind of obvious compared to the Euler method, though. Once you realize it's 4 bits across a cycle of 15, it's just just a matter of finding the right seed. It should be on the order of 1 in a billion, which is no big deal. In hindsight, if I had combined my number theory knowledge I might have been able to accomplish the Euler solution, but I didn't, so hats off to them. The presentation of the tensorflow provides more a much higher contempt for the question than I've achieved as well. The fact it isn't 100% accurate, but can be trained to be accurate to a certain level, just makes it better. I will redouble my research efforts on this or some other problem which doesn't need solving.
  - uuidgen 6y ago
    But there is conditional logic "hidden" in lambda mapping. You want it without ANY conditional logic try this (python3): [str(n)*(n%3!=0)*(n%5!=0) + 'Fizz'*(n%3==0) + 'Buzz'*(n%5==0) for n in range(1,101)]
    - chongli 6y ago
      There’s tons of hidden conditional logic in the Python string multiplication operator. It’s implemented via the C function unicode_repeat which handles all the conditional logic.
      - uuidgen 6y ago
        If you're talking about assembly then every single statement in python will involve hidden conditions. I was talking about the idea behind the code - that map is a pythonic shorthand for a bunch of if-then statements, it still expresses conditionals. While using string multiplication doesn't.
- chronolitus 6y ago
  Right, but your comment doesn't do justice to the beauty of the solution being so concise. Is it a coincidence that the same exponent 4 works for both multiples of 3 and 5? What if instead of 3 and 5, we did FizzBuzz with 7 and 11? Let's do n%77, now we need to map 7, 14, 21, 28, 35, 42, 49, 56, 63, 70 to Fizz, and 11, 22, 33, 44, 55, 66 to Buzz, unless we can find some way to have them all reduce to the same number. Is that really so straightforward? Now that we know the trick with the exponents, we could try a few to start. For multiples of 11 it seems the smallest one which works is 6! Great, let's try it on multiples of 7.. Nope. Ok, for multiples of 7, I see that ^10 works.. but that doesn't work for multiples of 11. * the article addresses this at the end, and tells us that the correct exponent is ^30, the lowest common denominator of 6 and 10. But if I'd been given this problem, I'd have remained stuck on the second paragraph of this comment, with no idea where to start when seeking to reduce the divisors to a single number.
  - namelessUser 6y ago
    If a^n = 0 (or 1) mod b, then a^(kn) = (a^n)^k = 0 (or 1) mod b for any positive integer k. Therefore you need to pick a common multiple of 6 and 10.
tlaundal 6y ago
This 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.
- qsort 6y ago
  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 https://blog.antfeedr.com/posts/fizzbuzz.html.
- prionassembly 6y ago
  > This is of course a really neat solution, but the proof doesn't really give me much value as a reader. This is because your number theory-fu is poor. Don't take this in a bad way, I'm probably even less capable. What I mean is that readability is predicated on a reader. Seasoned number theorists might not be as cool with goroutines or walrii operators or virtual DOMs.
- anthk 6y ago
  https://medium.com/hackernoon/algorithms-explained-diffie-hellman-1034210d5100 https://medium.com/hackernoon/algorithms-explained-diffie-he...
Qub3d 6y ago
The 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 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.
- enriquto 6y ago
  > 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.
  - Qub3d 6y ago
    Well, I suppose I mean sad in the way people are wistful when old technology fades into obsolescence, not because the tech was better (it clearly isn't) but because the times it represents fading with it. e.g. dumb phones, analog TV, CRT monitors, floppy disks...
- uuidgen 6y ago
  I don't believe "quantum computing" will get us any step closer to breaking RSA. Similar how complex number theory didn't allow us to draw a square with area of -1. To break RSA-N you need a superposition of all the numbers up to 2^N, AFAIK there is even not a hint how to approach it physically.
  - danbruc 6y ago
    A superposition of all n bit integers is no big deal, extracting useful information when performing a measurement is. If you start with a uniform distribution of all n bit integers, you also get each result with equal probability unless you manage to manipulate the system in such a way that the probability of the correct result gets amplified. This is the hard part, finding and implementing operations that selectively boost the probability of the correct result while reducing the probabilities of all other results.
motohagiography 6y ago
Was 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.
- leblancfg 6y ago
  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!
  - omaranto 6y ago
    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.
  - roelschroeven 6y ago
    We can even easily write it as a one-line without lambda: [{ 1: n, 6: "Fizz", 10: "Buzz", 0: "FizzBuzz" }[n**4%15] for n in range(1, 101)] The lambda in the original code is just used to convert the 0..99 that's generated by range(100) to 1..100. Using range(1, 101) instead generates the appropriate range of numbers from the beginning.
- raverbashing 6y ago
  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 ;)
- bidirectional 6y ago
  Jane Street maybe. I've not heard of Galois having a tricky interview process. From what I've heard of Renaissance, this would be insultingly trivial to ask.
philcrissman 6y ago
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. I'm definitely an amateur mathematician, though I tried my best to write the post like I think I'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. I have nothing else to promote, haven't even put anything on the site since this one and only post... Anyways, thanks, news-YC.
- philcrissman 6y ago
  I was actually asked Fizz Buzz in an interview once, but I did not have this solution at the time. My favorite FizzBuzz solution is actually: ``` ->(n){[[["Fizz"][n%3],["Buzz"][n%5]].join].find(->{n}){|w| w if !w.empty?}} ``` This is Ruby, of course, probably something very similar can be done in several other languages.
- svat 6y ago
  This is a nice post; thanks for writing it! (A minor thing: the margin notes completely disappear on mobile, i.e. at width of 760px or less.) You probably know this already, but I'd think of this the following way. There are two main mathematical ideas involved here: • The first, easy to underrate because it can seem "obvious", is the Chinese remainder theorem. This, for instance, here implies that any function of the quantities (x mod 3) and (x mod 5) can be rewritten as a function of just (x mod 15). So if you used just this one idea and not the next one, you could implement FizzBuzz as lambda n: ['FizzBuzz', n, n, 'Fizz', n, 'Buzz', 'Fizz', n, n, 'Fizz', 'Buzz', n, 'Fizz', n, n][n % 15] • The second is Fermat's little theorem. It says (x^(p-1) mod p) = [x is not a multiple of p], where the notation […] is Iverson bracket, i.e. 1 or 0 depending on whether the condition is true or not. So the question of whether x is a multiple of 5 or not is equivalent to whether x^4 mod 5 is 0 or 1. This just gives us a convenient way of restating the divisibility condition. To get from Fermat's little theorem to Euler's theorem (or to be pedantic, Carmichael's theorem, as you're not using φ(15) which is technically 2*4 = 8, but rather using lcm(2, 4)=4: https://en.wikipedia.org/w/index.php?title=Carmichael_function&oldid=1007232556#Computing_%CE%BB(n)_with_Carmichael's_theorem https://en.wikipedia.org/w/index.php?title=Carmichael_functi... ) is itself an application of the Chinese remainder theorem, which is why I think it's important and mentioned it first. And putting these two ideas together gives the function in your post. Namely: the FizzBuzz you want is a function of [x is a multiple of 3] and [x is a multiple of 5], so you can (using the second idea) rewrite it as a function of (x^2 mod 3) and (x^4 mod 5), and put them together (using the CRT) as a function of (x^4 mod 15). Coincidentally, both the ideas here are connected to Lagrange: the Chinese remainder theorem is the same kind of thing as the Lagrange interpolation formula (https://artofproblemsolving.com/community/c1157h990758_the_chinese_remainder_theorem_and_lagrange_interpolation https://artofproblemsolving.com/community/c1157h990758_the_c...), and Fermat's/Euler's/Carmichael's theorem is the same kind of thing as Lagrange's theorem in group theory.
draganm 6y ago
Neat trick, the only issue I see is mis-selling the idea that no conditionals are used ... map on it's own (independently how it'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.
- Sharlin 6y ago
  In this case though you could just use an 11-element array as a lookup table which would technically make this branchless.
  - draganm 6y ago
    true - but would require modifying the proposed solutions. Besides, it does not remove the branching issue of mod ... unless you use a lookup table for that too, but then you might as well have the lookup table for the whole FizzBuzz solution space.
    - smlckz 6y ago
      heh, the branching is now in the implementation of the lookup table
      - Jtsummers 6y ago
        It's a common pattern in embedded systems (for better or worse) when you have something like function pointers or computed go tos available. C, of course, has function pointers and I've seen dispatch tables like this before: message_handler = {type_0, type_1, ..., type_999}; // imagine it being generated message_handler[message.type](message); In the case of computed go to in Fortran, it's similar. I had the "pleasure" of maintaining this once. It's been a while so I had to look up the syntax, IIRC it used something like a dispatch tree and dispatched off each digit in the type but I could be wrong: go to (0, 100, 200, 300, ...), message_type / 100 -- integer division 0 go to ... 100 go to ... 200 go to ... ...
smlckz 6y ago
if you want to practice programming and like mathematics, you should try Project Euler * * heh! https://projecteuler.net https://projecteuler.net
MauranKilom 6y ago
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)).
- ersatz_username 6y ago
  You’ve got a factor of three sneaking into your 4^4. In general (ab) mod n == (a mod n)(b mod n) mod n In the case of (3*c)^4, 3^4 mod 15 -> 108 mod 15 -> 3.
johbjo 6y ago
I would do this: Let i = ((n % 3) == 0) | ((n % 5) == 0) << 1 Then map output as { n, 'Fizz', 'Buzz', 'FizzBuzz' }
- MauranKilom 6y ago
  Or, using only elementary math: Let i = ((n % 3) ** 2) + ((n % 5) ** 4) * 2 Or, given any number n of primes p_j, the "fizzbuzz index" i is just Let i = sum_over_j(((n % p_j) ** (p_j - 1)) * (n ** j)) (This doesn't generalize to non-primes via the totient function for the same reason the post's solution doesn't generalize - (a % k) * phi(k) for prime k is zero if and only if k divides a, but for non-prime k it can also become zero for other a.)
decker 6y ago
Maybe I'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.
- wagslane 6y ago
  I think it's about the math porn, not execution time.
- jhayward 6y ago
  Conditional logic is, in general, harder to analyze for correctness than declarative data and mathematical formulae.
  - hansvm 6y ago
    Adding to this, I think conditional logic is typically fine; the distinction is in using conditionals as data that gets passed around in a system vs branching on those conditions. E.g., considering `var rectified = x*(x>0);` or `var foo = predicate ? bar : baz;` both lend themselves to having their invariants easily verified, even if many such constructions are littered through a program. Contrast that with something like `if (predicate) {/*nightmares*/} else {/*slightly changed nightmares*/}` -- too many branches can quickly lead to an explosion of possible execution paths and all the problems that entails.
kirillcool 6y ago
Good luck running ^4 on larger numbers and overflowing integer / long bounds orders of magnitude faster than the plain "boring" solutions
- bidirectional 6y ago
  Modular exponentiation can be done very quickly, you don't need to compute n^4 at all. Not sure if this particular implementation makes use of that, though. In Haskell, I can compute (100000 ^ 1000000 `mod` 15) near instantly.
  - nonameiguess 6y ago
    Python's built in pow function does this, but the ** operator does not. Of course, like Haskell, it also uses arbitrary precision integers by default, so it might take forever to compute something, but it won't overflow unless you actually run out of memory.
- Jtsummers 6y ago
  The trick is to do the modulus before the exponentiation. It gives the same result. n^4 % x = m == (n % x)^4 % x = m By way of demonstration: n = 18, x = 15 18^4 = 104976 = 6 (mod 15) ---- 18 % 15 = 3 3^4 = 81 = 6 (mod 15) A very handy result to remember for cases where you don't want to use or don't have easy access to arbitrary precision integers.
  - anthk 6y ago
    Well, this doesn't need much of a demonstration. The rest of a division will be the same "visually" if you keep "stacking" the same number on top.
- anthk 6y ago
  https://medium.com/@c0D3M/introduction-to-rsa-e8cb39af508e https://medium.com/@c0D3M/introduction-to-rsa-e8cb39af508e EDIT: Pasting into Lynx screwed formatting from Groff.
nickcw 6y ago
That was fun! Not that anyone cares for FizzBuzz but I'll just note that n**4%15 is more efficiently written using the 3 argument pow function in python, eg pow(n, 4, 15). >>> timeit("(1<<100000000)**4%15", number=1) 1.5620321459136903 >>> timeit("pow(1<<100000000, 4, 15)", number=1) 0.05834826407954097 >>> 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. https://docs.python.org/3/library/functions.html#pow https://docs.python.org/3/library/functions.html#pow
- ChrisLomont 6y ago
  Modulus and power commute, so you can use ((n%15)**4)%15 to keep it small for any integer n
  - Jtsummers 6y ago
    That starts it small, but doesn't necessarily keep it small. For instance, if n is 1000 and the mod is 1001, we still end up with 1,000,000,000,000 as an intermediate value before the final mod 1001. That's not too bad (fits in a 64-bit integer), but it's easy to see how (with different exponents or bases) it can still blow up. The second python example in GP comment keeps it small by making use of the mod as it steps through the exponentiation, not just at the start and end. EDIT: What I wrote was more about the general case. In this specific case, the largest number we get after modulo would be 14, and 14^4 is only 38,416 so it does actually stay small for this specific instance of the problem.
    - ChrisLomont 6y ago
      You don't have to do the power all at once - use powermod - then you need at most a square to fit. And when that doesn't fit, there are still more math tricks to keep it small and fast.
  - sblom 6y ago
    Is "commute" the right word for that? I'm not a mathematician, but it doesn't match any usage in my poorly trained math-lang semantic net.
exdsq 6y ago
I hope I remember this for the next time I have to answer fizzbuzz in an interview
deleted 6y ago
[deleted]
chinchilla2020 6y ago
Fizzbuzz question has a nuance that is not acknowledged by many. Read the question carefully. It should solve: 3: fizz 5: buzz 15: fizzbuzzfizzbuzz Why is this? 15 is divisible by 3 15 is divisible by 5 15 is divisible by 3 and 5 All three statements in the description are true. You never said they were mutually exclusive.
deleted 6y ago
[deleted]
scythe 6y ago
You can be even more ridiculous: char ds[5]; char * words[4] = {ds, "Fizz\n", "Buzz\n", "FizzBuzz\n"}; for (i = 1; i < 101; ++i) { sprintf(ds, "%d\\n", i) printf(words[((i*i*i*i)%15)/4]); }

212 points by koevet 6y ago

tgb 6y ago

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

kingaillas 6y ago
His point was writing a function without conditional logic, and then of course generalizing to any "fizzbuzz category" problem. I thought it was a fantastic post on a extremely well trodden subject, up there with solving fizzbuzz in Tensorflow post. (https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/ https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/)
- LanceH 6y ago
  My entry to use random-isn't-random: https://github.com/LanceH/fizzbuzz/blob/master/fb.go https://github.com/LanceH/fizzbuzz/blob/master/fb.go I feel like I need to revisit after seeing tensorflow and Euler. I need to find some way of making the lucky number using things around a room, like a mentalist or something. Some other subversive ones I've seen of are the java enterprise version, and several that import a fizzbuzz library and just run.
  - isaacimagine 6y ago
    I find that random-not-random implementation pretty incredible.
    - LanceH 6y ago
      Thanks. It seems kind of obvious compared to the Euler method, though. Once you realize it's 4 bits across a cycle of 15, it's just just a matter of finding the right seed. It should be on the order of 1 in a billion, which is no big deal. In hindsight, if I had combined my number theory knowledge I might have been able to accomplish the Euler solution, but I didn't, so hats off to them. The presentation of the tensorflow provides more a much higher contempt for the question than I've achieved as well. The fact it isn't 100% accurate, but can be trained to be accurate to a certain level, just makes it better. I will redouble my research efforts on this or some other problem which doesn't need solving.
- uuidgen 6y ago
  But there is conditional logic "hidden" in lambda mapping. You want it without ANY conditional logic try this (python3): [str(n)*(n%3!=0)*(n%5!=0) + 'Fizz'*(n%3==0) + 'Buzz'*(n%5==0) for n in range(1,101)]
  - chongli 6y ago
    There’s tons of hidden conditional logic in the Python string multiplication operator. It’s implemented via the C function unicode_repeat which handles all the conditional logic.
    - uuidgen 6y ago
      If you're talking about assembly then every single statement in python will involve hidden conditions. I was talking about the idea behind the code - that map is a pythonic shorthand for a bunch of if-then statements, it still expresses conditionals. While using string multiplication doesn't.
chronolitus 6y ago
Right, but your comment doesn't do justice to the beauty of the solution being so concise. Is it a coincidence that the same exponent 4 works for both multiples of 3 and 5? What if instead of 3 and 5, we did FizzBuzz with 7 and 11? Let's do n%77, now we need to map 7, 14, 21, 28, 35, 42, 49, 56, 63, 70 to Fizz, and 11, 22, 33, 44, 55, 66 to Buzz, unless we can find some way to have them all reduce to the same number. Is that really so straightforward? Now that we know the trick with the exponents, we could try a few to start. For multiples of 11 it seems the smallest one which works is 6! Great, let's try it on multiples of 7.. Nope. Ok, for multiples of 7, I see that ^10 works.. but that doesn't work for multiples of 11. * the article addresses this at the end, and tells us that the correct exponent is ^30, the lowest common denominator of 6 and 10. But if I'd been given this problem, I'd have remained stuck on the second paragraph of this comment, with no idea where to start when seeking to reduce the divisors to a single number.
- namelessUser 6y ago
  If a^n = 0 (or 1) mod b, then a^(kn) = (a^n)^k = 0 (or 1) mod b for any positive integer k. Therefore you need to pick a common multiple of 6 and 10.

tlaundal 6y ago

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

qsort 6y ago
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 https://blog.antfeedr.com/posts/fizzbuzz.html.
prionassembly 6y ago
> This is of course a really neat solution, but the proof doesn't really give me much value as a reader. This is because your number theory-fu is poor. Don't take this in a bad way, I'm probably even less capable. What I mean is that readability is predicated on a reader. Seasoned number theorists might not be as cool with goroutines or walrii operators or virtual DOMs.
anthk 6y ago
https://medium.com/hackernoon/algorithms-explained-diffie-hellman-1034210d5100 https://medium.com/hackernoon/algorithms-explained-diffie-he...

Qub3d 6y ago

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

enriquto 6y ago
> 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.
- Qub3d 6y ago
  Well, I suppose I mean sad in the way people are wistful when old technology fades into obsolescence, not because the tech was better (it clearly isn't) but because the times it represents fading with it. e.g. dumb phones, analog TV, CRT monitors, floppy disks...
uuidgen 6y ago
I don't believe "quantum computing" will get us any step closer to breaking RSA. Similar how complex number theory didn't allow us to draw a square with area of -1. To break RSA-N you need a superposition of all the numbers up to 2^N, AFAIK there is even not a hint how to approach it physically.
- danbruc 6y ago
  A superposition of all n bit integers is no big deal, extracting useful information when performing a measurement is. If you start with a uniform distribution of all n bit integers, you also get each result with equal probability unless you manage to manipulate the system in such a way that the probability of the correct result gets amplified. This is the hard part, finding and implementing operations that selectively boost the probability of the correct result while reducing the probabilities of all other results.

motohagiography 6y ago

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

leblancfg 6y ago
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!
- omaranto 6y ago
  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.
- roelschroeven 6y ago
  We can even easily write it as a one-line without lambda: [{ 1: n, 6: "Fizz", 10: "Buzz", 0: "FizzBuzz" }[n**4%15] for n in range(1, 101)] The lambda in the original code is just used to convert the 0..99 that's generated by range(100) to 1..100. Using range(1, 101) instead generates the appropriate range of numbers from the beginning.
raverbashing 6y ago
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 ;)
bidirectional 6y ago
Jane Street maybe. I've not heard of Galois having a tricky interview process. From what I've heard of Renaissance, this would be insultingly trivial to ask.

philcrissman 6y ago

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. I'm definitely an amateur mathematician, though I tried my best to write the post like I think I'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. I have nothing else to promote, haven't even put anything on the site since this one and only post... Anyways, thanks, news-YC.

philcrissman 6y ago
I was actually asked Fizz Buzz in an interview once, but I did not have this solution at the time. My favorite FizzBuzz solution is actually: ``` ->(n){[[["Fizz"][n%3],["Buzz"][n%5]].join].find(->{n}){|w| w if !w.empty?}} ``` This is Ruby, of course, probably something very similar can be done in several other languages.
svat 6y ago
This is a nice post; thanks for writing it! (A minor thing: the margin notes completely disappear on mobile, i.e. at width of 760px or less.) You probably know this already, but I'd think of this the following way. There are two main mathematical ideas involved here: • The first, easy to underrate because it can seem "obvious", is the Chinese remainder theorem. This, for instance, here implies that any function of the quantities (x mod 3) and (x mod 5) can be rewritten as a function of just (x mod 15). So if you used just this one idea and not the next one, you could implement FizzBuzz as lambda n: ['FizzBuzz', n, n, 'Fizz', n, 'Buzz', 'Fizz', n, n, 'Fizz', 'Buzz', n, 'Fizz', n, n][n % 15] • The second is Fermat's little theorem. It says (x^(p-1) mod p) = [x is not a multiple of p], where the notation […] is Iverson bracket, i.e. 1 or 0 depending on whether the condition is true or not. So the question of whether x is a multiple of 5 or not is equivalent to whether x^4 mod 5 is 0 or 1. This just gives us a convenient way of restating the divisibility condition. To get from Fermat's little theorem to Euler's theorem (or to be pedantic, Carmichael's theorem, as you're not using φ(15) which is technically 2*4 = 8, but rather using lcm(2, 4)=4: https://en.wikipedia.org/w/index.php?title=Carmichael_function&oldid=1007232556#Computing_%CE%BB(n)_with_Carmichael's_theorem https://en.wikipedia.org/w/index.php?title=Carmichael_functi... ) is itself an application of the Chinese remainder theorem, which is why I think it's important and mentioned it first. And putting these two ideas together gives the function in your post. Namely: the FizzBuzz you want is a function of [x is a multiple of 3] and [x is a multiple of 5], so you can (using the second idea) rewrite it as a function of (x^2 mod 3) and (x^4 mod 5), and put them together (using the CRT) as a function of (x^4 mod 15). Coincidentally, both the ideas here are connected to Lagrange: the Chinese remainder theorem is the same kind of thing as the Lagrange interpolation formula (https://artofproblemsolving.com/community/c1157h990758_the_chinese_remainder_theorem_and_lagrange_interpolation https://artofproblemsolving.com/community/c1157h990758_the_c...), and Fermat's/Euler's/Carmichael's theorem is the same kind of thing as Lagrange's theorem in group theory.

draganm 6y ago

Neat trick, the only issue I see is mis-selling the idea that no conditionals are used ... map on it's own (independently how it'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.

Sharlin 6y ago
In this case though you could just use an 11-element array as a lookup table which would technically make this branchless.
- draganm 6y ago
  true - but would require modifying the proposed solutions. Besides, it does not remove the branching issue of mod ... unless you use a lookup table for that too, but then you might as well have the lookup table for the whole FizzBuzz solution space.
  - smlckz 6y ago
    heh, the branching is now in the implementation of the lookup table
    - Jtsummers 6y ago
      It's a common pattern in embedded systems (for better or worse) when you have something like function pointers or computed go tos available. C, of course, has function pointers and I've seen dispatch tables like this before: message_handler = {type_0, type_1, ..., type_999}; // imagine it being generated message_handler[message.type](message); In the case of computed go to in Fortran, it's similar. I had the "pleasure" of maintaining this once. It's been a while so I had to look up the syntax, IIRC it used something like a dispatch tree and dispatched off each digit in the type but I could be wrong: go to (0, 100, 200, 300, ...), message_type / 100 -- integer division 0 go to ... 100 go to ... 200 go to ... ...

smlckz 6y ago

if you want to practice programming and like mathematics, you should try Project Euler * * heh! https://projecteuler.net https://projecteuler.net

MauranKilom 6y ago

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

ersatz_username 6y ago
You’ve got a factor of three sneaking into your 4^4. In general (ab) mod n == (a mod n)(b mod n) mod n In the case of (3*c)^4, 3^4 mod 15 -> 108 mod 15 -> 3.

johbjo 6y ago

I would do this: Let i = ((n % 3) == 0) | ((n % 5) == 0) << 1 Then map output as { n, 'Fizz', 'Buzz', 'FizzBuzz' }

MauranKilom 6y ago
Or, using only elementary math: Let i = ((n % 3) ** 2) + ((n % 5) ** 4) * 2 Or, given any number n of primes p_j, the "fizzbuzz index" i is just Let i = sum_over_j(((n % p_j) ** (p_j - 1)) * (n ** j)) (This doesn't generalize to non-primes via the totient function for the same reason the post's solution doesn't generalize - (a % k) * phi(k) for prime k is zero if and only if k divides a, but for non-prime k it can also become zero for other a.)

decker 6y ago

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

wagslane 6y ago
I think it's about the math porn, not execution time.
jhayward 6y ago
Conditional logic is, in general, harder to analyze for correctness than declarative data and mathematical formulae.
- hansvm 6y ago
  Adding to this, I think conditional logic is typically fine; the distinction is in using conditionals as data that gets passed around in a system vs branching on those conditions. E.g., considering `var rectified = x*(x>0);` or `var foo = predicate ? bar : baz;` both lend themselves to having their invariants easily verified, even if many such constructions are littered through a program. Contrast that with something like `if (predicate) {/*nightmares*/} else {/*slightly changed nightmares*/}` -- too many branches can quickly lead to an explosion of possible execution paths and all the problems that entails.

kirillcool 6y ago

Good luck running ^4 on larger numbers and overflowing integer / long bounds orders of magnitude faster than the plain "boring" solutions

bidirectional 6y ago
Modular exponentiation can be done very quickly, you don't need to compute n^4 at all. Not sure if this particular implementation makes use of that, though. In Haskell, I can compute (100000 ^ 1000000 `mod` 15) near instantly.
- nonameiguess 6y ago
  Python's built in pow function does this, but the ** operator does not. Of course, like Haskell, it also uses arbitrary precision integers by default, so it might take forever to compute something, but it won't overflow unless you actually run out of memory.
Jtsummers 6y ago
The trick is to do the modulus before the exponentiation. It gives the same result. n^4 % x = m == (n % x)^4 % x = m By way of demonstration: n = 18, x = 15 18^4 = 104976 = 6 (mod 15) ---- 18 % 15 = 3 3^4 = 81 = 6 (mod 15) A very handy result to remember for cases where you don't want to use or don't have easy access to arbitrary precision integers.
- anthk 6y ago
  Well, this doesn't need much of a demonstration. The rest of a division will be the same "visually" if you keep "stacking" the same number on top.
anthk 6y ago
https://medium.com/@c0D3M/introduction-to-rsa-e8cb39af508e https://medium.com/@c0D3M/introduction-to-rsa-e8cb39af508e EDIT: Pasting into Lynx screwed formatting from Groff.

nickcw 6y ago

That was fun! Not that anyone cares for FizzBuzz but I'll just note that n**4%15 is more efficiently written using the 3 argument pow function in python, eg pow(n, 4, 15). >>> timeit("(1<<100000000)**4%15", number=1) 1.5620321459136903 >>> timeit("pow(1<<100000000, 4, 15)", number=1) 0.05834826407954097 >>> 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. https://docs.python.org/3/library/functions.html#pow https://docs.python.org/3/library/functions.html#pow

ChrisLomont 6y ago
Modulus and power commute, so you can use ((n%15)**4)%15 to keep it small for any integer n
- Jtsummers 6y ago
  That starts it small, but doesn't necessarily keep it small. For instance, if n is 1000 and the mod is 1001, we still end up with 1,000,000,000,000 as an intermediate value before the final mod 1001. That's not too bad (fits in a 64-bit integer), but it's easy to see how (with different exponents or bases) it can still blow up. The second python example in GP comment keeps it small by making use of the mod as it steps through the exponentiation, not just at the start and end. EDIT: What I wrote was more about the general case. In this specific case, the largest number we get after modulo would be 14, and 14^4 is only 38,416 so it does actually stay small for this specific instance of the problem.
  - ChrisLomont 6y ago
    You don't have to do the power all at once - use powermod - then you need at most a square to fit. And when that doesn't fit, there are still more math tricks to keep it small and fast.
- sblom 6y ago
  Is "commute" the right word for that? I'm not a mathematician, but it doesn't match any usage in my poorly trained math-lang semantic net.

exdsq 6y ago

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

deleted 6y ago

[deleted]

chinchilla2020 6y ago

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

deleted 6y ago

[deleted]

scythe 6y ago

You can be even more ridiculous: char ds[5]; char * words[4] = {ds, "Fizz\n", "Buzz\n", "FizzBuzz\n"}; for (i = 1; i < 101; ++i) { sprintf(ds, "%d\\n", i) printf(words[((i*i*i*i)%15)/4]); }