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).
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.
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.
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.
Of course at that point you may as well just calculate gcd(n, 15) entirely since the fast version of Euclids algorihtm only needs 2 divisions at most anyway.
According to the Wikipedia page on the commutative property, "commute" is the right word.
> If the commutative property holds for a pair of elements under a certain binary operation then the two elements are said to commute under that operation.
I'm a PhD in math. Modulo is a function in that it maps integer to integers. Power is a function mall mg integers to integers. Both are operators in the math sense, and one can talk about operators commuting.
So the terms are correct.
As far as programmers, modulus is an operator, complete with operator overloading in many languages and satisfying operator precedence. So operator is the correct word there also.
The injection mod15: Z -> Z/15 is an operation and the basic idea here is mod15(pow4(x)) = pow4(mod15(x)), so I think it's correct to call it commutativity.
pow4(mod15(x)) is already in Z/15, you can't apply mod15 to it. The point is pow4ing in Z and then reducing mod 15 is the same as reducing mod 15, then pow4ing in Z/15.
It's not actually the same pow4 on the LHS and RHS (the LHS is in Z, the RHS in Z/15), but I think "commutative" still fits.
Well, how about this, if we use pow4' to be modular exponentiation, i.e. mod15 o pow4? (of course then changing mod15 to take Z -> Z so the types line up)
Then the desired statement showing commutativity is
pow4'(mod15(x)) = pow4'(x) = mod15(pow4'(x))
where that last equality is trivial because
mod15 o mod15 = mod15
so
mod15 o pow4' = mod15 o mod15 o pow4 = mod15 o pow4 = pow4'
It's roughly the right word for it - mathematicians would say that operations f and g commute if f(g(x)) = g(f(x)) for all x. In this specific case it is not quite true that (^4) and (%15) commute, but if we treat (%15) as returning an element of the-integers-modulo-15 then it is true that the two operations precisely commute. (I think people would say "they commute" anyway, because colloquially it's close enough).
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.
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.
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.
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.
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.
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.
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.
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_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_c...), and Fermat's/Euler's/Carmichael's theorem is the same kind of thing as Lagrange's theorem in group theory.
Re the margin notes, the footnote numbers are clickable to toggle them inline when the width is too small... I should add a bit of color or underline to them in the css so that this is easier to intuit. :/
Ah, clicking the footnote numbers worked for footnotes 1 to 4, but not for 5 and 6.
BTW, for the question “Where do the constant values 0, 6, 10, and 1 come from?”, though it's implicit in the post, it is useful to note explicitly that as x^4 takes only the values 0 or 1 either mod 3 or mod 5, these four possibilities—namely (0,0), (0,1), (1,0), (1,1)—precisely account for those values:
(0 mod 3) and (0 mod 5) ⇔ (0 mod 15)
(0 mod 3) and (1 mod 5) ⇔ (6 mod 15)
(1 mod 3) and (0 mod 5) ⇔ (10 mod 15)
(1 mod 3) and (1 mod 5) ⇔ (1 mod 15)
This would also simplify the post considerably maybe, as much of the algebra wouldn't be needed.
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:
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.
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...
IMHO Quantum supremacy is pie in the sky, which will stay in the sky. So, you can probably pursue modular arithmetic safely for the foreseeable future.
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.
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.
> A superposition of all n bit integers is no big deal
Is it? How do you do it? The papers I've seen so far shown that given enough measurements we can conclude that the qbits ware in superposition in many cases. I still haven't seen any way to have superposition of all numbers from 0 to 2^n.
What you're describing in the rest of your comment is solved by Shor's algorithm. It is quite straight-forward. If we can get the superposition as an input and have working quantum gates it would work.
Similar how all we need to draw a square with -1 area is to take a line segment with a length of i, the rest is simple.
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.
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.
Yeah, but given that `mod` (if we’re talking native integers rather than some bigint type) is implemented as a single machine instruction, i’d count that as branchless for all reasonable intents and purposes even though the hardware has to internally do something equivalent to a loop to do division.
on the CPU level (I'm talking Intel here, but it applies to most other chips) DIV/IDIV instructions (returning division result and remainder a.k.a. modulo) are the ones using up the most CPU cycles. The reason for this is that they can't be completely parallelised because of having to check conditions.
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 ...
...
If your compiler is optimizing for speed, you can you write the program in a way so that the compiler can unroll the loop and hopefully make it branchless as well
The map data structure, not the map higher order function. As implemented, most map data structures will have a conditional in their lookup functions to handle the case of collisions or a key being absent from the map.
Well, the loop in your `map()` does obviously have a halting condition. But I believe by map, the GP meant the associative array used by the implementations to lookup the correct output.
In most languages, looping is implemented with conditional jumps, but I actually think Python is unique in this case because of the way it uses exceptions for flow control. Rather than checking an index to see if the loop has reached the end of an iterator, the iterator just raises a StopIteration exception and the runtime catches it.
The key lookup in dict definitely has conditionals, though.
Of course, the guy could get rid of that by just using an 11-element array and addressing directly instead of hashing integers as keys.
>Rather than checking an index to see if the loop has reached the end of an iterator, the iterator just raises a StopIteration exception and the runtime catches it.
And how does the iterator know that it should raise an exception? A conditional.
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.
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.
> 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.
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)).
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.)
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.
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.
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.
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.
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.
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.
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.
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.
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).
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