Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Euler's Fizzbuzz (2020)

philcrissman.net

Post reply on HN
Print view View original

51–60 of 92 posts

Re: Euler's Fizzbuzz (2020)

#51

Post by uuidgen »

kingaillas wrote: post #27
tgb wrote: post #2

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 thi…

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

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

Re: Euler's Fizzbuzz (2020)

#52

Post by danbruc »

uuidgen wrote: post #46
Qub3d wrote: post #4

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 so…

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.

Re: Euler's Fizzbuzz (2020)

#53

Post by svat »

philcrissman wrote: post #47

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 lo…

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: Euler's Fizzbuzz (2020)

#54

Post by chongli »

uuidgen wrote: post #51
kingaillas wrote: post #27

Earlier quoted context omitted.

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

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

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.

Re: Euler's Fizzbuzz (2020)

#55

Post by ChrisLomont »

nickcw wrote: post #34

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 >> timeit("pow(1 >> 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.…

Modulus and power commute, so you can use ((n%15)**4)%15 to keep it small for any integer n

Re: Euler's Fizzbuzz (2020)

#57

Post by chinchilla2020 »

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.

Re: Euler's Fizzbuzz (2020)

#58

Post by ufo »

Sharlin wrote: post #13
draganm wrote: post #11

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.

If we're doing that then we may as well avoid the exponentiation with `lookup_table[n % 15]`.

Re: Euler's Fizzbuzz (2020)

#59

Post by Jtsummers »

ChrisLomont wrote: post #55
nickcw wrote: post #34

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 >> timeit("pow(1 >> 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.…

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.

Post reply on HN