GoogleEntExam

Stefanie Olsen (CNET News.com)

2004/07/12 08:40

先週、シリコンバレーの中心を走るハイウェー101沿いのビルボードに、複雑な数 学の問題を載せた広告が現れた。(中略)

この広告には、「｛eの値中の、最初の連続する10桁の素数｝.com」("{first 10 digit prime found in consecutive digits e}.com." )と書かれている。この答えの「7427466391.com」にアクセスすると、そのウェブページにはさらに別の問題(下記参照)が用意されているが、ここにもGoogleが関与していることを示すものは全くない。 この問題を解くと、Googleの研究開発部門「Google Labs」へのページに辿りつく。このページには、「Googleの構築を通して我々が学んだことの1つに、自分が何かを探しているとき、向こうも自分を探している場合のほうが見つかりやすいということがある。我々が探しているのは、世界最高のエンジニアであり、あなたこそその人なのだ」と書かれている。

例題

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

2.71828182845904523536028747135266249775
7247093699959574966967627724076630353547
5945713821785251664274274663919320030599
2181741359662904357290033429526059563073
81323286279434907632338298807531952510190

である．これをテキストにコピーして読みこませよ．

解法

各個撃破(あるいは分割統治)で解いて行く．おおまかな流れは，

1. eの値中の、連続する10桁の数
   1. 数の読み込み
   2. 10桁の整数の生成
2. 素数判定
3. 最初の連続する10桁の素数を捜す

である．

eの値中の、連続する10桁の数

まずうまく読み込めるか試す．

[BobsNewPBG4-6:~/Ruby/google] bob% cat google.rb
exp1=gets.to_s.chomp
puts exp1
[BobsNewPBG4-6:~/Ruby/google] bob% ruby google.rb < exp.txt
2.71828182845904523536028747...

exp.txtの内容を"<"で読み込ませている．次に，10桁ずつ表示させることを考える． 文字列exp1を配列とみなしてexp1[0]として表示させようとすると失敗する．ここで 出てくるのはasciiコードの番号．そこで，chrで表示させる．

[BobsNewPBG4-6:~/Ruby/google] bob% cat google2.rb
exp1=gets.to_s.chomp
puts exp1
puts exp1[0]
puts exp1[1]
puts exp1[2].chr
puts exp1[3].chr.to_i
puts exp1[3..12].to_i

[BobsNewPBG4-6:~/Ruby/google] bob% ruby google2.rb < exp.txt
2.71828182845904523536028747135266...
50
46
7
1
1828182845

もっと簡単には最後のputs exp1[3..12].to_i でいいが，これは後の問題でつかえないのでもうすこしちまちま作る．

   num=10*num+exp1[i+j].chr.to_i

でjを０から９まで回せば10桁の整数となる．

[BobsNewPBG4-6:~/Ruby/google] bob% cat google2.rb
exp1=gets.to_s.chomp
puts exp1
puts exp1[0]
puts exp1[1]
puts exp1[2].chr
puts exp1[3].chr.to_i
puts exp1[3..12].to_i

i=3
j=0
num=0
while j<10 do
  num=10*num+exp1[i+j].chr.to_i
  j+=1
end
puts num





[BobsNewPBG4-6:~/Ruby/google] bob% ruby google2.rb < exp.txt
2.7182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251664274274663919320030599218174135966290435729003342952605956307381323286279434907632338298807531952510190
50
46
7
1
1828182845
1828182845

これを２重ループにして次々に10桁の整数を切り出す．今は，最初の10個を表示．このとき，expの"."が邪魔なので(プログラムでしてもいいけど，面倒なので)テキスト側で削っとく．

[BobsNewPBG4-6:~/Ruby/google] bob% cat google2.rb
exp1=gets.to_s.chomp

i=0
while i<10 do
  j=0
  num=0
  while j<10 do
    num=10*num+exp1[i+j].chr.to_i
    j+=1
  end
  i+=1
  puts num
end




[BobsNewPBG4-6:~/Ruby/google] bob% ruby google2.rb < exp1.txt
2718281828
7182818284
1828182845
8281828459
2818284590
8182845904
1828459045
8284590452
2845904523
8459045235

素数判定

rubyのサブルーチンにあたるメソッドのひな形を作成．下では仮引数nを読み込んで， それをそのまま返している．

[BobsNewPBG4-6:~/Ruby/google] bob% cat isprime.rb
def isprime(n)
  return n
end

exp1=gets.to_s.chomp
puts isprime(exp1)
[BobsNewPBG4-6:~/Ruby/google] bob% ruby isprime.rb
37
37

先週作ったisprimeをcopy&paste．さらに変数をあわせる．

[BobsNewPBG4-6:~/Ruby/google] bob% cat isprime0.rb
def isprime(n)
  i_max=n
  i=1
  warden=0
  while (i<i_max) do
    i +=1
    if (n%i==0) then 
      warden=1 
      break 
    end
  end
  
  if (warden==0) then 
    return 1
  else
    return 0
  end
end

exp1=gets.chomp.to_i
puts isprime(exp1)
[BobsNewPBG4-6:~/Ruby/google] bob% ruby isprime0.rb
37
0

2行目のi_maxはnではなくsqrt(n)でよい．rubyでは

i_max=Math.sqrt(n)

とする．こうしておかないと次のプログラムが時間がかかる(30分待ったがやめた)

最初の連続する10桁の素数を捜す

あとは上のプログラムを集めて，whileループで回せばよい．はじめは途中結果を全て表示しながらデバッグを進める．

[BobsNewPBG4-6:~/Ruby/google] bob% cat google.rb
def isprime(n)
  puts n
  i_max=Math.sqrt(n)+1
  i=1
  warden=0
  while (i<i_max) do
    i +=1
    if (n%i==0) then 
      warden=1 
      break 
    end
  end
  
  if (warden==0) then 
    return 0
  else
    return 1
  end
end

exp1=gets.to_s.chomp
i=0
i=0
while i<10 do
  j=0
  num=0
  while j<10 do
    num=10*num+exp1[i+j].chr.to_i
    j+=1
  end
  i+=1
  puts num
  puts isprime(num)
end



[BobsNewPBG4-6:~/Ruby/google] bob% ruby google.rb < exp1.txt
2718281828
2718281828
1
7182818284
7182818284
1
1828182845
1828182845
1
8281828459
8281828459
1
2818284590
2818284590
1
8182845904
8182845904
1
1828459045
1828459045
1
8284590452
8284590452
1
2845904523
2845904523
1
8459045235
8459045235
1

200桁までを使って求めた「eの値中の、連続する10桁の素数」は以下のとおり．

[BobsNewPBG4-6:~/Ruby/google] bob% ruby google.rb < exp1.txt
100:7427466391
124:7413596629
150:6059563073
172:3490763233
183:2988075319

類題

Congratulations. You've made it to level 2. Go to www.Linux.org and enter Bobsyouruncle as the login and the answer to this equation as the password.

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