Euler's Fizzbuzz (2020)

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

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.

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.

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.

I don't think it will be soon, but when it happens it won't necessarily be sad.

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.

    //pseudocode
    map(f, ns)
      for i in (0 .. ns.length - 1)
        f(ns[i])

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

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.

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

  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)

EDIT: Pasting into Lynx screwed formatting from Groff.

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