Google Recruit

過去に出題された Google のリクルート問題を解いていく．問題は次の通り．

Google Recruit Problem

e(自然対数の底)の値で連続する10桁の数のうち，最初の素数をrubyで求めよ．ただし，e(自然対数の底)は以下の200桁までとする．

2.71828182845904523536028747135266249775
7247093699959574966967627724076630353547
5945713821785251664274274663919320030599
2181741359662904357290033429526059563073
81323286279434907632338298807531952510190

解法

それでは実際に解いていく．まずはじめに方針を決める必要があるので，タスクをまとめてみると

数値ファイルを読み込む．
10桁の数を取り出す．
素数を判定する．

これらを順に実装していこう．

ファイルの読み込み

まずは 200 桁のe(自然対数の底)を exp.txt に保存し，ファイルを読み込む．標準入力から読み込む場合，

exp = gets.to_s.chomp.delete(".")

のように実装できるがこの場合，実行時に

$ ruby google_recruit.rb < exp.txt

とリダイレクトで exp.txt を指定しなければならない．

今回はexp.txt を変更することはないので，コマンドではなくプログラム内でファイルを参照することにする．ruby では File クラスの read メソッドを使うことでファイルを読み込むことができる．

exp = File.read('exp.txt').delete(".")

読み込んだデータを格納した変数 exp を出力すると

271828182845904523536028747135266249775
7247093699959574966967627724076630353547
5945713821785251664274274663919320030599
2181741359662904357290033429526059563073
81323286279434907632338298807531952510190

改行されて出力される.これはexp.txt の中身自体が改行されているため，読み込まれたものも改行されてしまっている．

改行をなくすには delete メソッドで改行コードを指定すればよい．

exp = File.read('exp.txt').delete(".").delete("\n")

27182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251664274274663919320030599218174135966290435729003342952605956307381323286279434907632338298807531952510190

問題なくファイルを読み込むことができた．

連続する 10 桁の数の取り出し

先ほど読み込んだデータを格納した変数 exp について，先頭から順に連続する 10 桁を取り出したい．変数 exp は文字列として扱えば各桁を指定することができるので each を用いて 10 桁ずつ取り出す．

exp = File.read('exp.txt').delete("\n").delete(".")

[*0..exp.length-10].each do |i|
  x_digits = exp[i..i+10-1].to_i
  puts xdigit
end

実行してみると

問題なく先頭から順に連続する 10 桁を取り出すことができた．

素数判定のメソッド

今回のメインになる素数判定について見ていく．引数が素数であれば true, 素数でなければ false を返す is_prime メソッドを実装する．

素数とは自身の数 n と 1 以外で割り切れない数字なので，n を 2 ~ n-1 で順に割っていき，割り切れたら false を返すようにする．プログラムは以下のとおり.

def is_prime(num)
  [*2..num-1].each do |i|
    return false if num%i == 0
  end
  return true
end

しかし，実際に実行してみると1つの10桁の数に対して愚直に数十万回比較するので，自然対数の底 e の 200 桁の実行時間はとてつもなくかかってしまう．

何か上手い方法はないのか？

これは以下のように変更することで解決できる．

def is_prime(num)
  [*2..Math::sqrt(num).to_i+1].each do |i|
    return false if num%i == 0
  end
  return true
end

num-1 を Math::sqrt(num).to_i+1 に書き換えるだけでできる．これは素数でない合成数の性質を上手に利用している．

その性質とは 合成数 x は p ≦ √x を満たす素因子 p をもつ ．わかりやすく説明すると x が合成数の場合，√x 以下の約数を持つ ということ．これで最高 100 万回近く比較していたものも 1000 回程度で済むようになる．

完成プログラム

上記を組み合わせたものは，以下のとおり．

# coding: utf-8
def is_prime(num)
  # 愚直に 1 ずつ比較する場合
  # [*2..num-1].each do |i|

  # 
  [*2..Math::sqrt(num).to_i+1].each do |i|
    return false if num%i == 0
  end
  return true
end

exp = File.read('exp.txt').delete("\n").delete(".")

[*0..exp.length-10].each do |i|
  x_digits = exp[i..i+10-1].to_i
  if is_prime(x_digits)
    print("[", i,", ", x_digits,", true]")
    break
  end
end

実行すると，

$ ruby google_recruit.rb
[99, 7427466391, true]

99 桁目から連続する 10 桁の 7427466391 が最初の素数であることがわかった．

さらなる高速化

コメントにて @ib_sis さんから 処理速度を早める観点でいうと偶数の場合はスキップするとよいかもしれません。 というご指摘をいただきました，ありがとうございます．

一緒に頂いたコードを拝借し，実行時間を計測してみた．Ruby の標準ライブラリ benchmark を用いると元の完成プログラムは

# coding: utf-8
require 'benchmark'

result = Benchmark.realtime do
  def is_prime(num)
    # 愚直に 1 ずつ比較する場合
    # [*2..num-1].each do |i| 
    [*2..Math::sqrt(num).to_i+1].each do |i|
      return false if num%i == 0
    end
    return true
  end

  exp = File.read('exp.txt').delete("\n").delete(".")

  [*0..exp.length-10].each do |i|
    x_digits = exp[i..i+10-1].to_i
    if is_prime(x_digits)
      print("[", i,", ", x_digits,", true]\n")
      break
    end
  end
end

puts "実行時間: #{result}s"

偶数の場合はスキップする改編後のプログラムは

# coding: utf-8
require 'benchmark'

result = Benchmark.realtime do
  def is_prime(num)
    # 愚直に 1 ずつ比較する場合
    # [*2..num-1].each do |i| 
    [*2..Math::sqrt(num).to_i+1].each do |i|
      return false if num%i == 0
    end
    return true
  end

  exp = File.read('exp.txt').delete("\n").delete(".")

  [*0..exp.length-10].each do |i|
    x_digits = exp[i..i+10-1].to_i
    next if x_digits.even?

    if is_prime(x_digits)
      print("[", i,", ", x_digits,", true]\n")
      break
    end
  end
end

puts "実行時間: #{result}s"

のようになる．

実行した結果，

> ruby google_recruit-origin.rb
[99, 7427466391, true]
実行時間: 0.20240300009027123s

> ruby google_recruit-edit.rb
[99, 7427466391, true]
実行時間: 0.1098970000166446s

予想通り実行時間が半分に短縮された．これはかなり大きな時間短縮．

発展問題

先ほどの問題の続きとして，

f(1)=7182818284
f(2)=8182845904
f(3)=8747135266
f(4)=7427466391
f(5)=__________

f(5) に入る数字を求める問題が出題される．これについて考察し，実行してみる．

素数とか完全数ではなさそう．共通点は 10 桁であることくらい．Google Recruit Problem の続きなのでネイピア数には関係していると考えて，ネイピア数の小数点を見ていくと f(1)=7182818284 が小数点の 1 桁目から 10 桁目であることがわかる．その他はどうなのか続きを見てみると f(2) は 5 桁目から 14 桁目，f(3) は 23 桁目から 32 桁目，f(4) は 99 桁目から 108 桁目であった．数列のようでもないし手がかりがない．

8 が多いけど偶数とか奇数とか関係あるのかなーと悩んでいると，10 桁の総和が49 になることを発見した．

これは各桁の総和が 49 になる 10 桁を求めるメソッドを作成し，先ほどのプログラムに組み込めば良い．作成したものは以下のとおり．

def is_49(num)
  sum = 0
  [*0..9].each do |i|
    sum += num[i].to_i
  end
  return true if sum == 49
  return false
end

exp = File.read('exp.txt').delete("\n").delete(".")

[*0..exp.length-10].each do |i|
  x_digits = exp[i..i+10-1]
  if is_49(x_digits)
    print("[", i,"~", i+9,": ", x_digits,"]\n")
  end
end

実行すると

$ ruby google_recruit2.rb
[1~10: 7182818284]
[5~14: 8182845904]
[23~32: 8747135266]
[99~108: 7427466391]
[127~136: 5966290435]
[145~154: 2952605956]

200 桁のe(自然対数の底)の中で連続する10桁の総和が49 になるものは 6 つあり， f(5) = 5966290435 であることがわかった．

参考ページ

今回参考にしたページはこちら．

Google recruit problem, exp and prime

【Ruby】ファイル読み込みメソッドまとめ

【Ruby】よく使うFileクラスを使ったファイル読み込み処理

謝辞

本投稿に編集リクエストを送ってくださった @torifukukaiou さん，ありがとうございました．

また，Elixir というプログラミング言語で本投稿の google recruit problem に挑戦されたようです．以下から @torifukukaiou さんの投稿に飛ぶことができますので，是非併せてご覧ください．

「Google Recruit」をElixirでやってみる

初めて聞いた言語 Elixir ．記述方法も全然異なっていてものすごく気になる！

source ~/grad_members_20f/members/e79a93e5b7b1/posts/class/google-recruit.org