素数大富豪

はじめに

こんにちは、Life is Tech ! メンター Advent Calendar 2017 14日目です。皆さんモダンなプログラミングとかの技術紹介をしてくれていますね。

私は、Life is Tech!で5年前からAndroidコースやMediaArtコースのメンターをしています。去年はクリスマスイブにMediaArtコースっぽいことを書きました。openFrameworksを別スレッドでTwitter連携させる

さて今年のAdvent Calendarですが、
僕の通っている東京工業大学は、屈指の国立理系大学なので、みんな素数が大好きです。*1
そのため、素数にちなんだ何かを書いてみようと思います。

参考 :

• 知恵袋/なぜ東工大の人は素数があんなに好きなのですか？
• レゴ人形が素数を聞いて大喜びする「素数チャレンジ」を東工大が作成
  「東工大　素数」で調べるとたくさん出てきます。

素数大富豪について

みなさん、「素数大富豪」というゲームを知っていますか？もちろん知っていますよね。
万が一知らない人がいたら、 素数大富豪とは？初心者のためのルール＆ちょっとしたコツ集 もしくは 素数大富豪 Wiki を参考にしてください。以下の説明は前者から簡単に引用しています。

用意するもの

トランプ：一組以上
プレイヤー：２人以上

ゲームの流れ

もっとも基本的には、このゲームは「場と同じ枚数でより大きい素数を出していく」というゲームです。勝利条件は相手より早く自分の手札をなくすこと。

素数とは「自分より小さい正の数（１以外の）で割り切れない数」のことを言います。例えば「５」という数は自分より小さい４、３、２で割ると小数点以下が出てきてしまって割り切れないので、素数です。対して例えば「６」だったら、３や２で割り切れてしまうので素数ではありません。５は出せるけど６は出せない、というわけです。

各地でも流行っているみたいですね、下記のTweetリンクの画像がルール説明としてわかりやすかったです。

素数大富豪初心者のためのカンペ資料案できた！プレイしながらルールを確認する用。とりあえず今日の素数大富豪会in札幌で使ってみて修正する予定。 #素数大富豪 pic.twitter.com/Fwgi2DmVku

— 二世 (@m_2sei) February 11, 2017

*1 より、東工大では「素数大富豪」が流行っています。研究室の後輩が数学科の友人を倒すために奮闘していたので知りました。

例えば、ウェブでは 素数大富豪 ver.3 でコンピュータと対戦できます。

素数大富豪で戦うためのプログラムをかいてみる

私がプログラミングを始めたのは、中学三年生で、[エラトステネスの篩] (https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9) という「指定された整数x以下の全ての素数を発見するアルゴリズム」を数学の授業で習って、数が大きくなると、手計算で探すのが大変なのでプログラミングしてみようみたいな気持ちでやった気がします。

問題設定

素数大富豪で勝つためには、先の手を読んであえて出さないカードがあったり、手札をあえて増やして大きな素数を出すみたいな戦略も考えられますが、
今回は簡単のため、「ジョーカー」「合成数出し」「グロタンディーク素数」や「ラマヌジャン革命」は考えずに、自分の持ち札の中から、指定枚数を使ってその時に最大の素数を出すというのを問題に設定します。

実装

今回作成したプログラムはrepl.itでブラウザから実行を試せるような形で共有していますので、ぜひ試してみてください。
https://repl.it/@Hiroki11x/PrimeNumberMillionaire

今回は、素数判定に関して最も工夫をしない形で簡単に実装しています。

# 各種moduleのimport
import sys
import itertools

# 素数か判定する関数
def is_prime(x):
    # 2以上でない入力は素数でないのでFalseを返す
    if (x > 1):
        # 最小の素数は2なので2から割り始める
        divisor = 2
        # 範囲[2,x-1]の範囲で入力xが割れるかを確認
        for i in range(divisor,x):
            # 割り切れる数があった場合、素数でないのでfalse
            if (x % i) == 0:
                return False
    # 2以上でない入力は素数でないのでFalseを返す
    else:
        return False
    # 範囲[2,x-1]の範囲で入力xが割れず素数なのでTrue
    return True

# 全ての手札の数
sys.stdout.write("全ての手札の数: ")
num_of_hand=int(input())

# 使う手札の枚数
sys.stdout.write("使う手札の枚数: ")
search_range_of_hand=int(input())

# 手札のカードの入力
cards = []
for num in range(num_of_hand):
    sys.stdout.write("手札"+str(num+1)+": ")
    input_value = input()
    cards.append(input_value)

# カードの並び替えの組み合わせを生成
cards_combination_lists = list(itertools.permutations(cards,search_range_of_hand))

# 並べ替えた組み合わせを数字の形に結合
cards_string_list = []
for cards_list in cards_combination_lists:
    cards_string = ''.join(cards_list)
    cards_string_list.append(cards_string)
  
# 文字列のリストを数字のリストに変換
cards_int_list = list(map(int, cards_string_list))

# 大きい順に並べ換える
cards_int_list.sort(reverse=True)

# 大きい候補順に素数かどうか判定する
for candidate in cards_int_list:
    if(is_prime(candidate)):
        print("作成可能な最大の素数: "+str(candidate))
        break
else: print('素数が作れません')

実践

こんな感じで勝てます。

が、本来、「素数大富豪」でこれはずるなので、ダメです。
しかしながら、今この手札で最大の素数はなんなんだろうといった、新しい素数との出会いに使ってみてください。

最後に

今回は、「素数大富豪」というゲームを題材に、それをプログラムを書いて戦ってみる、みたいな紹介をしました。
プログラムで書いた素数の判定方法は、一番工夫のないプレーンなものですが、カードの枚数が増えて探索の範囲が大きくなると、かなり実行時間を要してしまいます。
そのため、例えば素数の性質に着目し、ある整数Nに対して[2,N-1]の範囲で割るといった今回の実装をしなくても、[2,N/2]の範囲の探索に留めることや、フェルマーの小定理を利用した判定法、またエラトステネスの篩を用いて、あらかじめ素数のリストを作っておいてそれと比較する方法など工夫のしようがいっぱいあるので、ググってコピペするだけでなく、まず自分で考えてみるのも面白いかもしれません。
アプリやウェブサイト・ゲームを作るだけがプログラミングじゃないよ、数学みたいな面白さもあるよみたいな雰囲気が伝わるといいなとおもっています。

明日は、大学の先輩でもあり、なんでもできちゃう黒ポロメンターのタナカこと@kenta71さんです！お楽しみに！

追記(2017/12/15)

数学アレルギーの私が素数大富豪に出会ったらアレルギーが治って生きるのが楽しい話という記事を読んで感動してしまいました。やはり素数は素敵ですね。
素数大富豪 Advent Calendar 2017も参考にみてみてください。