Edited at

pythonとフェルマーの小定理で1行FizzBuzz


FizzBuzzでフェルマーの小定理が使えるらしい

フェルマーの小定理がFizzBuzzに使えると聞いて、調べてもわかりやすいコードと記事が見つけられなかったのでpythonで自分で作ってみました。以下のコードはできあがったものです。

for n in range(1,101):print("FizzBuzz"[n**2%3*4:12-n**2%3*4-n**4%5*8] or n)

これを見ても普通はよくわからないと思うので作成時の思考過程をこの記事で書いていきます。


フェルマーの小定理

まずはフェルマーの小定理の主張を確認しましょう。

n^{p-1} ≡ 1 \quad (mod \hspace{5pt} p)

ただしpとnは互いに素で、pは素数。

n**(p-1)をpで割った余りが1になるということです。


FizzBuzzへの応用

nがp(3または5)の倍数でないとき、nとpは互いに素だから

n^{2} ≡ 1 \quad (mod \hspace{5pt} 3)\\

n^{4} ≡ 1 \quad (mod \hspace{5pt} 5)

が成り立ちます。

nがp(3または5)の倍数のとき、余りはもちろん0です。つまり3(または5)の倍数でないかどうかを1と0で表せるわけです。


実装

以下の式はnが3の倍数のとき0、そうでないとき1になります。


n**2%3

0と1を反転させたければ以下のようにします。


1-n**2%3

5も同様です。


n**4%5
1-n**4%5

これを利用すると次のようなFizzBuzzコードが書けます。


for n in range(1,101):print((1-n**2%3)*"Fizz"+(1-n**4%5)*"Buzz" or n)


文字列"FizzBuzz"からのスライス

上記のコードはn**2%3などが数字であることを活かしきれていません。これではつまらないので"FizzBuzz"という文字列から必要に応じて必要な部分だけをスライスするプログラムを実装してみます。

image.png

手書き失礼しました。

上の画像は"FizzBuzz"の各文字のインデックスとスライスの開始(黒丸)および終了(白丸)の対応で、上から順に数字、Fizz、Buzz、FizzBuzzの場合に相当します。紫の数字はn**2%3およびn**4%5を並べたものです。

スライスに含まれるのはは開始点のインデックス以上かつ終了点のインデックス未満のインデックスを持つ要素です。また、終了点のインデックスが開始点のインデックス以下になると文字列を返しません。したがって例えば上の画像のような開始・終了の位置が考えられます。

n**2%3およびn**4%5の値をベクトル(x,y)で表し開始点と終了点を(X,Y)で表すと


X = ax + by + c\\
Y=dx+ey+f

を満たすような6つのパラメータa,b,c,d,e,fを見つけます。上の図の通りだと拘束条件が8個で解は存在しない事になってしまいますが、(0,1)と(0,0)のときの開始点Xは4以下であればよく(1,0)と(0,0)のときの終了点Yは8以上であればよいので例えば(a,b,c,d,e,f)=(4,0,0,-4,-8,12)などを選びます。


X = 4x \\
Y=-4x-8y+12

このX,Yで"FizzBuzz"[X:Y]のようにスライスします。これを実装したのが冒頭のコード(以下に再掲)です。

for n in range(1,101):print("FizzBuzz"[n**2%3*4:12-n**2%3*4-n**4%5*8] or n)


追記:平方の記述(2019/04/27)

コードゴルフとしてはn**2ではなくn*nとしたほうがよいという指摘をいただきました。

for n in range(1,101):print("FizzBuzz"[n*n%3*4:12-n*n%3*4-n**4%5*8] or n)


追記2:n*n%3*4をまとめる(2019/04/28)

n*n%3*4が2回現れているのでoとして以下のようにまとめるとさらに2文字短くなるという指摘をいただきました。

for n in range(1,101):o=n*n%3*4;print("FizzBuzz"[o:12-o-n**4%5*8] or n)