Googleは「難問」でどんな人材を求めたのか?

  • Facebook
  • Twitter
  • はてなブックマーク
  • Delicious
  • Evernote
  • Tumblr

CNETの記事渡辺千賀さんのblog でも紹介されていましたが、Googleがシリコンバレーの高速道路101沿いに、ナゾの看板を出したことが話題になってます。
看板には、
「first 10-digit prime found in consecutive digits of e (自然対数の底”e”の中で最初に出てくる連続した10桁の素数)」.com
とだけ書いてあって、答えは7427466391.com
(看板にはgoogleとも何とも書いて無くて、問題だけが書いてある。)
このアドレスにアクセスすると、さらに次の問題が待っているということになります。
要するに、Googleが人材募集のために、ある程度の数学の素養があるかどうかをふるいにかけるために、話題性のある看板を出した、ということのようです。
はじめから記事に答えが書いてあるので解く楽しみが台無しですが。この問題はどのくらい難しいのか。また、googleは、この問題でどんな能力を試そうとしているのか、というところが興味深いところです。
自然対数の底「e」を探してくる
問題を解くためには、まずは、自然対数の底eの数列を用意しないといけません。インターネット時代には、自分で計算するよりどっかから探して来た方が早い。
Googleで「e、2.718281828459」などのキーワードで探して、そこで見つかったより長い数列で検索していくと、何万桁といったeの数列を掲載しているページがいくつか見つかってきます。間違ってると意味ないので、一番頭の良さそうなNASAの人のページのものを引用させていただきますと、eは、

e =2.718281828459045235360287471352662497
7572470936999595749669676277240766303535
4759457138217852516642742746639193200305
9921817413596629043572900334295260595630
7381323286279434907632338298807531952510
1901157383418793070215408914993488416750
9244761460668082264800168477411853742345
4424371075390777449920695517027618386062
6133138458300075204493382656029760673711
3200709328709127443747047230696977209310
1416928368190255151086574637721112523897
8442505695369677078544996996794686445490
5987931636889230098793127736178215424999
2295763514822082698951936680331825288693
9849646510582093923982948879332036250944
3117301238197068416140397019837679320683
・・・

というような数列になることがわかります。(このページ、100万桁まで紹介しています。)
意外に早く答えに到達
記事のせいで、答えが「7427466391」だとわかっちゃっているので、どの辺にその10桁が出現するのかを見てみると、

e =2.718281828459045235360287471352662497
7572470936999595749669676277240766303535
4759457138217852516642742746639193200305

と、わずか100桁ちょっとのところに出てきました。(がっくり_| ̄|○)
わたしは、Googleが出した問題なので、数学知識+コンピュータのプログラミング能力が超バリバリの人でないと解けないような問題なのかと思ったのですが、これならちょっとExcelの知識がある人なら解けちゃいますね。
10桁の素数ですから、その平方根の10万くらいまでの素数で順に割っていけばいいだけです。
素数を探してくる
次に、素数を用意する必要があります。
自分で「エラトステネスのふるい」などのアルゴリズムで素数を計算してもいいですが、同じく、インターネット時代なので、素数を計算して結果を紹介されている方のホームページから素数を拝借するほうが早い、です。これなら「文系」でも素数を用意できます。
そういう方のデータで10万以下の素数の数を数えると、1万個弱。
これなら、Excelの縦の行に十分収まりますね。
eから10桁ずつ切り出した数字をExcelのセルに並べて、素数一覧で順に割っていき、割り切れたら次の数の検証にとりかかる、というような比較的簡単なマクロを組めば、マクロを組む時間を含めても半日もかからないで解けちゃいそうです。
素因数分解の困難性
素因数分解は「NP問題」であることが知られています。NP問題とは「非決定性チューリングマシンが多項式時間で解くことのできる決定問題のクラス」に属する問題のこと。つまり、答えがわかっていればコンピュータを使えばそこそこの時間で検算はできるが、答えをゼロから探す場合、桁数が増えるとその桁数の多項式以上(つまり指数関数のオーダーなどで)計算時間が増え、コンピュータでも何億年もかかってしまうようなことになる問題のこと、です。
(ちなみに、インターネットで利用するセキュリティ技術のSSL、PGP、RSA暗号などに使われている公開鍵暗号理論も、この素因数分解の困難性により、短い暗号キーでも解読が現実的に困難になることを利用したものです。)
つまり、今回の問題は10桁でしたが、桁数をちょっと増やせば急速に計算時間が長くなるので、Googleは、
「Excelのマクロ程度の知識ではとても解けないが、素因数分解の効率的なアルゴリズムやバリバリのプログラミングの知識があるヤツなら、そこそこの時間で解ける問題」
を簡単に作れたはずなわけです。
もしかしたら、この問題(2問目はまだ解いていないですが少なくとも1問目)は、バリバリの技術者を探す問題ではなく、「Googleで働くには技術者以外の(文系的)職種でも、こんくらいできないとね」、という軽いジャブなのかしらん、とか、HRの担当者がこの程度の問題を作れるのかしらん、と思ったりもしました。(・・・・そうだとしたら・・・恐るべしGoogle・・・・。)
(1問目ですが、とりあえず本日はここまで。)

[PR]
メールマガジン週刊isologue(毎週月曜日発行840円/月):
「note」でのお申し込みはこちらから。

Googleは「難問」でどんな人材を求めたのか?” への2件のコメント

  1. ふなといいます。
    グーグルの難問を正攻法で解いたのですね。
    私はグーグルの入社試験であるから
    WEBページ検索会社の入社問題として
    解いてみました(笑)
    http://ftvjapan.ddo.jp/~funa/mt/archives/000120.html
    こういう解き方もあるってことです。
    ではでは!
    あ、2問目の解答もあります。参考に
    #こっちはある意味正攻法。

  2. >WEBページ検索会社の入社問題として
    >解いてみました(笑)
    なーるほど。そういう解き方もありましたか!
    >あ、2問目の解答もあります。参考に
    しまった。答え見ちゃった。そんな単純なことだったとは・・・。(がーん。)
    どうもありがとうございます。
    ではでは。