Euler's Fizzbuzz (2020)(philcrissman.net)
philcrissman.net
Euler's Fizzbuzz (2020)
http://philcrissman.net/posts/eulers-fizzbuzz/
91 comments
Modulus and power commute, so you can use ((n%15)**4)%15 to keep it small for any integer n
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.
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.
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.
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.
https://en.wikipedia.org/wiki/Commutative_property
> 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.
https://en.wikipedia.org/wiki/Commutative_property
No, it's called distributive property: https://en.m.wikipedia.org/wiki/Distributive_property
After some further reading, I don't think anyone in this thread is correct. Modulo in math is not an operator like a programmer might think of it. See: https://math.stackexchange.com/questions/2832649/modular-ari...
Right. This is a consequence of compatibility with exponentiation.
https://en.wikipedia.org/wiki/Modular_arithmetic#Properties
It should be easy to see that
https://en.wikipedia.org/wiki/Modular_arithmetic#Properties
It should be easy to see that
n ≡ (n % 15) (mod 15)
n^4 ≡ (n % 15)^4 (mod 15)
n**4 % 15 == (n % 15) ** 4 % 15I'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.
Here's the idea from math https://mathoverflow.net/questions/20968/rules-for-operator-...
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.
Here's the idea from math https://mathoverflow.net/questions/20968/rules-for-operator-...
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.
Well, not quite.
You really want to say that mod15(pow4(x)) == mod15(pow4(mod15(x))).
Example:
(3 ** 4) % 15 = 81 % 15 = 6.
But,
(3 % 15) ** 4 = 3 ** 4 = 81.
(That said, the two functions do commute when you restrict your domain and range to Z/15.)
edit: also, I wouldn't consider mod15 to be an injection, as it's, um, not injective (it maps multiple inputs to the same output).
You really want to say that mod15(pow4(x)) == mod15(pow4(mod15(x))).
Example:
(3 ** 4) % 15 = 81 % 15 = 6.
But,
(3 % 15) ** 4 = 3 ** 4 = 81.
(That said, the two functions do commute when you restrict your domain and range to Z/15.)
edit: also, I wouldn't consider mod15 to be an injection, as it's, um, not injective (it maps multiple inputs to the same output).
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.
> as it's, um, not injective
Er, surjection :)
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.
> as it's, um, not injective
Er, surjection :)
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
Then the desired statement showing commutativity is
pow4'(mod15(x)) = pow4'(x) = mod15(pow4'(x))
mod15 o mod15 = mod15
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).
Well, yeah... Exponentiation is O(2^n) (actually it’s also Omega(2^n)), modular exponentiation is O(n).
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.
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/)
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/)
My entry to use random-isn't-random: 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.
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.
I find that random-not-random implementation pretty incredible.
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.
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.
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)]
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)]
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.
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.
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.
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.
Therefore you need to pick a common multiple of 6 and 10.
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.
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
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.
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]
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.
Thanks!
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. :/
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:
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)
Thanks - this comment nicely summarizes the math involved here!
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.
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.
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
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.
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.
> 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.
I don't think it will be soon, but when it happens it won't necessarily be sad.
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...
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.
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.
Didn't I read somewhere that quantum computing basically gets you a factor of 2, like 2^(N-1)? It's a lot but at the same time it's just a bit.
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.
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.
In this case though you could just use an 11-element array as a lookup table which would technically make this branchless.
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.
heh, the branching is now in the implementation of the lookup table
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);
go to (0, 100, 200, 300, ...), message_type / 100 -- integer division
0
go to ...
100
go to ...
200
go to ...
...If we're doing that then we may as well avoid the exponentiation with `lookup_table[n % 15]`.
Why would map have conditions?
//pseudocode
map(f, ns)
for i in (0 .. ns.length - 1)
f(ns[i])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.
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.
And how does the iterator know that it should raise an exception? A conditional.
because for has a termination condition ...
Yeah, they should profile.
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.
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.
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.
> 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.
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)).
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.
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.
I would do this:
Let i = ((n % 3) == 0) | ((n % 5) == 0) << 1
Then map output as { n, 'Fizz', 'Buzz', 'FizzBuzz' }
Let i = ((n % 3) == 0) | ((n % 5) == 0) << 1
Then map output as { n, 'Fizz', 'Buzz', 'FizzBuzz' }
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.)
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.)
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.
Conditional logic is, in general, harder to analyze for correctness than declarative data and mathematical formulae.
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.
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.
I think it's about the math porn, not execution time.
[deleted]
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]);
}if you want to practice programming and like mathematics, you should try Project Euler *
* heh! https://projecteuler.net
* heh! https://projecteuler.net
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.
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.
Good luck running ^4 on larger numbers and overflowing integer / long bounds orders of magnitude faster than the plain "boring" solutions
https://medium.com/@c0D3M/introduction-to-rsa-e8cb39af508e
EDIT: Pasting into Lynx screwed formatting from Groff.
EDIT: Pasting into Lynx screwed formatting from Groff.
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.
The trick is to do the modulus before the exponentiation. It gives the same result.
n^4 % x = m
== (n % x)^4 % x = m
n = 18, x = 15
18^4 = 104976 = 6 (mod 15)
----
18 % 15 = 3
3^4 = 81 = 6 (mod 15)
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.
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.
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))
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.
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)]
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 ;)
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.
I hope I remember this for the next time I have to answer fizzbuzz in an interview
[deleted]
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