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

41–50 of 92 posts

Re: Euler's Fizzbuzz (2020)

#41

Post by Qub3d »

enriquto wrote: post #7
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…

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

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

Re: Euler's Fizzbuzz (2020)

#42

Post by isaacimagine »

LanceH wrote: post #29
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/ )

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 find that random-not-random implementation pretty incredible.

Re: Euler's Fizzbuzz (2020)

#43

Post by nonameiguess »

Sharlin wrote: post #17
islon wrote: post #15

Earlier quoted context omitted.

Why would map have conditions? //pseudocode map(f, ns) for i in (0 .. ns.length - 1) f(ns[i])

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.

Re: Euler's Fizzbuzz (2020)

#44

Post by nonameiguess »

bidirectional wrote: post #38
kirillcool wrote: post #33

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

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.

Re: Euler's Fizzbuzz (2020)

#45

Post by chronolitus »

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…

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.

Re: Euler's Fizzbuzz (2020)

#46

Post by uuidgen »

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.

Re: Euler's Fizzbuzz (2020)

#47

Post by philcrissman »

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.

Re: Euler's Fizzbuzz (2020)

#48

Post by namelessUser »

chronolitus wrote: post #45
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…

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

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.

Re: Euler's Fizzbuzz (2020)

#49

Post by philcrissman »

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…

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.

Re: Euler's Fizzbuzz (2020)

#50

Post by LanceH »

isaacimagine wrote: post #42
LanceH wrote: post #29

Earlier quoted context omitted.

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

Post reply on HN