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

71–80 of 92 posts

Re: Euler's Fizzbuzz (2020)

#71

Post by uuidgen »

chongli wrote: post #54
uuidgen wrote: post #51

Earlier quoted context omitted.

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.

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.

Re: Euler's Fizzbuzz (2020)

#72

Post by anthk »

Jtsummers wrote: post #65
anthk wrote: post #63

Earlier quoted context omitted.

https://medium.com/@c0D3M/introduction-to-rsa-e8cb39af508e EDIT: Pasting into Lynx screwed formatting from Groff.

> a^n % b = a % b. That is not generally true. A quick counterexample: a = 2, n = 3, b = 5 2^3 % 5 = 8 % 5 = 3 2 % 5 = 2 3 != 2

I was to type something like

       (a ^ n) % n = a % n

Re: Euler's Fizzbuzz (2020)

#73

Post by konjin »

henryfjordan wrote: post #69
sblom wrote: post #61

Earlier quoted context omitted.

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

No, it's called distributive property: https://en.m.wikipedia.org/wiki/Distributive_property

Re: Euler's Fizzbuzz (2020)

#74

Post by contravariant »

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

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.

Re: Euler's Fizzbuzz (2020)

#75

Post by uuidgen »

danbruc wrote: post #52
uuidgen wrote: post #46

Earlier quoted context omitted.

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

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

Re: Euler's Fizzbuzz (2020)

#76

Post by henryfjordan »

konjin wrote: post #73
henryfjordan wrote: post #69

Earlier quoted context omitted.

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

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

Re: Euler's Fizzbuzz (2020)

#77

Post by vitus »

henryfjordan wrote: post #76
konjin wrote: post #73

Earlier quoted context omitted.

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

    n ≡ (n % 15) (mod 15)
which, applying compatibility of exp, then gives us

    n^4 ≡ (n % 15)^4 (mod 15)
which can be rewritten in Python's notation as

    n**4 % 15 == (n % 15) ** 4 % 15

Re: Euler's Fizzbuzz (2020)

#78

Post by joppy »

sblom wrote: post #61
ChrisLomont wrote: post #55

Earlier quoted context omitted.

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

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.

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

Re: Euler's Fizzbuzz (2020)

#79

Post by philcrissman »

svat wrote: post #53
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 th…

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

#80

Post by edflsafoiewq »

henryfjordan wrote: post #76
konjin wrote: post #73

Earlier quoted context omitted.

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

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.
Post reply on HN