Rosettacode.org has this excellent one-line FizzBuzz solution in Ruby.
1.upto(100){|n|puts'FizzBuzz '[i=n**4%-15,i+13]||n}
The trouble is, I don’t understand it. The part that puzzles me is the ”n to the power of 4 modulo -15”. Does anyone have an explanation or a reference to an explanation? I want to use this way of selecting substrings in other problems. For more information on FizzBuzz, see [https://rosettacode.org/wiki/FizzBuzz]
I don't know how they discovered to raise to the fourth power, but the -15 is because FizzBuzz deals with multiples of 3 or multiples of 5 or multiples of both 3 and 5 (ie, multiples of 15)...then negating it ends up working with negative indices quite well. We can see that it works with Modular Exponentiation. The Memory-efficient method section there says:
c mod m = (a ⋅ b) mod m
c mod m = [(a mod m) ⋅ (b mod m)] mod m
In our case, the c is our n, so we have
c ** 4 % m
using the law of exponents, we know that (c ** e1) * (c ** e2) = c ** (e1 + e2), so c ** 4 = (c ** 2) * (c ** 2), so we now have an a and a b, which are both c ** 2. Thus:
(c ** 4) % m = ((c ** 2) * (c ** 2)) % m
= (((c ** 2) % m) * ((c ** 2) % m)) % m
= (((c ** 2) % m) ** 2) % m
and following the same steps, again:
(c ** 2) % m = (c * c) % m
= ((c % m) * (c % m)) % m
= ((c % m) ** 2) % m
and finally:
(c ** 4) % m = ((((c % m) ** 2) % m) ** 2) % m
When m = -15, the only values for c % m are (-14..0) and we can build a simple table to look at. Since we only ever operate on the result of a modulo, we only need to be able to prove these 15 numbers work:
c%m **2 %m **2 %m
-14 => 196 => -14 => 196 => -14
-13 => 169 => -11 => 121 => -14
-12 => 144 => -06 => 36 => -09
-11 => 121 => -14 => 196 => -14
-10 => 100 => -05 => 25 => -05
-09 => 81 => -09 => 81 => -09
-08 => 64 => -11 => 121 => -14
-07 => 49 => -11 => 121 => -14
-06 => 36 => -09 => 81 => -09
-05 => 25 => -05 => 25 => -05
-04 => 16 => -14 => 196 => -14
-03 => 9 => -06 => 36 => -09
-02 => 4 => -11 => 121 => -14
-01 => 1 => -14 => 196 => -14
00 => 0 => 00 => 0 => 00
Now, looking at our table, the values for all multiples of 3 are -09, the values for all multiples of 5 are -05, and things that are multiples of 3 and 5 are set to 00; everything else is -14 (If we had used 15 instead of -15, we'd have 6, 10, 0, and 1, respectively, and would need a look up to turn that into string indices). Plugging those in for the start parameter of String#[] with the string 'FizzBuzz ' gives us:
'FizzBuzz '[-9] # => 'F'
'FizzBuzz '[-5] # => 'B'
'FizzBuzz '[0] # => 'F'
'FizzBuzz '[-14]# => nil
and adding 13 to those numbers to get the length:
'FizzBuzz '[-9, 4] # => "Fizz"
'FizzBuzz '[-5, 8] # => "Buzz "
'FizzBuzz '[0, 13] # => "FizzBuzz "
'FizzBuzz '[-14, -1] # => nil
Quite tricky.
Modulus is a periodic function. You can get more periodic function with the same schema, changing the exponent (k) and divisor (h):
y = x**k % h
Or just see the x,y pairs for the case:
h = 4 # exponent
k = -15 # divisor
xy = []
1.upto 100 do |n|
i= n**h % k
xy << [n, i]
end
p xy
The periodicity is evident choosing a basic example of y = x % 2: k = 1 and h = 2.
You get a series of 1, 0, 1, 0, 1, ...
To visualise the function used in this case, you can plot in ruby for example using gnuplot gem.
require 'gnuplot'
Gnuplot.open do |gp|
Gnuplot::Plot.new( gp ) do |plot|
plot.title "Periodic function for FizzBuzz"
x = (0..100).collect { |v| v }
p y = x.collect { |v| v ** 4 % -15 }
plot.data << Gnuplot::DataSet.new( [x, y] ) do |ds|
ds.with = "linespoints"
end
end
end
I'll try to add a simpler explanation to @Simple Lime's excellent answer.
If n is a multiple of 3, let's denote it as 3k, Now:
(3k)^4 == 81(k^4)
81 % 15 == 6 and let's subtract 15 (since it's modulo -15) to get -9.
Likewise when n is a multiple of 5, it's 625(k^4) and 625 % 15 == 10 and after subtracting we get -5.
Otherwise, n might be a multiple of 2, 7, 11, and 13. In all these cases n^4 % 15 will be 1 (see Simple Lime's table) and -15 will get us -14.
