pythonを使えば、かのgoogleの問題もさくっと解ける

どーもどもども絨でーす！

リアルの方で色々とあって、時間が出来たので、大学院時代に使っていたpythonで遊ぼうかなと思い、

今回は

かの有名なgoogleの看板問題をpythonで解いてみたので、少しプログラムの内容を紹介しようと思います。pythonを使うとプログラミングが苦手な自分でもかなり簡単に解けるので、やはりpythonは神。

1. googleの看板問題って何？
2. pythonプログラムのソースコード

1. googleの看板問題って何？

2000年代前半というかなり昔、アメリカ・シリコンバレーの101号線の道路沿いに突如現れた問題が書かれた巨大看板で、そのシュールさに当時話題になったそうです。

f:id:mathpacejyu:20210505134129j:plain — googleの看板問題の写真。仮に自分が見かけたとしても、問題として認知出来ない自信しかない。

この問題を簡単にいうと、

自然対数 $e$ の無限小数に登場する連続する10桁の数字の中で、一番最初に登場する10桁の素数は何か？

という問題です。

ちょっと分かりづらいので、簡単な例を用いて問題の意味を確認して行きます。

自然対数の無限小数は、2.71828182845904523536028747・・・です。

この時、連続する2桁を順番に見ていくと、最初が27、続いて71、続いて18、次が82、、、となっていることが分かります。この場合、一番最初に登場する素数は71ということになりますね。

連続する3桁の場合は、最初が271、次が718、続いて182、続いて828、、、となり、一番最初に登場する素数が271であることが分かります。

では連続する10桁ではどうなるでしょう。最初が2718281828、次が7182818284、続いて1828182845、続いて8281828459、、、となりますね。残念ながらこの中に素数はないので、もっと10桁の数字を確認しなければならない問題となる訳です。

2. pythonプログラムのソースコード

まずは、この看板問題を解くpythonプログラムのソースコードを紹介します。

import math

list_n = [] #自然対数の無限小数の数字を1桁ずつリスト化(数列化)して格納するためのリスト
z = 200 #zの初期値(sの計算で使う)

while z > 0: #zが0より大きい間、以下の計算を繰り返す
  n = 27182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251664274274663919320030599218174135966290435729003342952605956307380251882050351967424723324653614466387704

  s = math.floor((n % (10**z))/(10**(z-1)))

  list_n.append(s) #sの値をリストに格納する

  z = z - 1 #zの値を1減らす



b = 9 #bは10桁の数字の内、一の位を指定するリストのアドレス(10の位はb-1、100の位はb-2、、、で指定出来る)

k = 0 #kの初期値(k=1になったら素数が見つかったとみなすような判断をするための数字)

while k == 0: #k=0の間は以下の計算を繰り返す

  if list_n[b]==1 or list_n[b]==3 or list_n[b]==7 or list_n[b]==9: #10桁の数字の中で一の位が偶数かつ5の場合は整数ではないため除外している

    if (list_n[b-9]+list_n[b-8]+list_n[b-7]+list_n[b-6]+list_n[b-5]+list_n[b-4]+list_n[b-3]+list_n[b-2]+list_n[b-1]+list_n[b]) % 3 != 0: # 10桁の数字の各桁の数字の和が3の倍数でないことを確かめる 

      l = list_n[b-9]*10**9+list_n[b-8]*10**8+list_n[b-7]*10**7+list_n[b-6]*10**6+list_n[b-5]*10**5+list_n[b-4]*10**4+list_n[b-3]*10**3+list_n[b-2]*10**2+list_n[b-1]*10**1+list_n[b]*10**0 #リストに格納した数字を使って、計算することで10桁の数字を生成(割られる数)

      t = 0

      ll = math.floor(math.sqrt(l)) #llは、割る数の最大数。素数かどうか調べる数(今回はl)の平方根までの大きさの数字で割り切れる数が無ければ、素数であると言えるため。

      c = 2 #cはlを割る数

      x = 1 #xは、割った余りが格納される変数。初期値は1

      while x != 0:#余りが0で無ければ、割る数を1ずつ大きくして割り算を試す。割り切れた(x=0になった)場合は計算を終了し、次の10桁の数字に移行する。
        x = l % c
        c = c + 1 #割る数を1大きくする

        if c > ll: #余りが0にならずに割る数が割られる数の平方根より大きくなった場合は、割られる数が素数なので、k=1にして割られる数を出力する

          k = 1 #k=1にする

          print(l)#素数だった割られる数を出力する

          break #breakして全ての計算を終了する

      b = b + 1 #素数ではなかった場合はbを1大きくして次の10桁の数字を生成し、素数であるか判定する
    else:
      b = b + 1
  else:
    b = b + 1