Preface (はじめに)
もう一方の課題であるGoogleの求人広告をRubyで解きたいと思います.
Google recruit
Googleの求人広告とは
上の写真のことです.和訳すると, {$e$の値中の最初の連続する10桁の素数}.comですね.
どうやら昔のGoogleは凄腕のITエンジニアを雇うためにこんなユニークな求人広告を出していたようです.
では, 早速Rubyを使って解いていきましょう.
Ruby
eの値を読み込む
$e$はネイピア数と呼ばれ, その定義は,
収束数列的に表すと,$$ e = \lim_{x \to \infty} \left(1 + \frac{1}{x} \right)^x $$
微積分学的に表すと, $$ e = \sum_{n = 0}^\infty \frac{1}{n!} $$となります.
$e$は無理数ですが, 今回は200桁までのを扱います.
2.71828182845904523536028747135266249775
7247093699959574966967627724076630353547
5945713821785251664274274663919320030599
2181741359662904357290033429526059563073
81323286279434907632338298807531952510190
この値をexp.txtに保存して, コードを動かすたびに読み込ませるようにします.
def read_exp
exp = File.read('exp.txt')
return exp.delete('.')
end
素数判定
引数nが素数かどうかを判定する関数を作ります.
nが素数であるには, 2 ~ n-1のすべての数で割り切れないことが条件です.
なので, 2 ~ n-1までの数の剰余を求めその全てが0でなければ素数という関数を作ります.
def prime? n
for i in 2..n-1 do
return false if n % i == 0
end
return true
end
ただ, これでは無駄な計算をしてしまいます.なので, 反復の上限は$\sqrt{n} + 1$とします.
どうして, このようにするかの説明は以下にします.
下の図は 緑が$xy = 6$の第一象限, 赤が$y = x$を表しています.
このとき, 緑線は赤線を軸に軸対象です.
つまり, 二つのグラフの交点$(x, y) = (\sqrt{6}, \sqrt{6})$を境に, 順序は逆ですが同じ数同士の乗算を行っているということです. それなら半分だけを調べればいいので, 素数判定を行う範囲を2 ~$\sqrt{n} + 1$とすればいいということになります.
また, 2を超えた数での素数はすべて奇数であるため, 2つ飛ばしで剰余を求めるようにします.
def prime? n
i = 2
return true if n == 2
return false if n % i == 0
i += 1
max = Integer.sqrt(n) + 1
while i <= max do
return false if n % i == 0
i += 2
end
return true
end
Code
では, これまでの関数を組み合わせて, プログラムを完成させます.
def read_exp
exp = File.read('exp.txt')
return exp.delete('.')
end
def prime? n
i = 2
return true if n == 2
return false if n % i == 0
i += 1
max = Integer.sqrt(n) + 1
while i <= max do
return false if n % i == 0
i += 2
end
return true
end
require "./assert_equal"
def test
expected = [2,3,5,7]
results = []
[*2..10].each do |num|
results << num if prime?(num)
end
assert_equal(expected, results)
end
def main
exp = read_exp()
for i in 0..exp.length-10 do
next if exp[i] == '0'
exp10 = exp[i..i+9].to_i
if prime?(exp10)
puts exp10
break
end
end
end
if $PROGRAM_NAME == __FILE__
main()
end
これを動かすと
> ruby exp_prime.rb
-> 7427466391
見事, 素数を返しました.
類題
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)=__________
f(4)の値が先ほど出した値と等しいのでこれも$e$の値の可能性が高そうです.
ただ, それ以外の共通点がわかりません.
悩みつくしたので, ggりました. 各桁の数を総和すると49になるのが共通点だそうです.
では, その情報をもとにプログラムを作ります.
require './exp_prime'
def main
exp = read_exp()
cnt = 0
for i in 0..exp.length-10 do
sum = 0
for j in 0..9 do
sum += exp[i+j].to_i
end
if sum ==49
cnt += 1
puts "f(" + cnt.to_s + ") = " + exp[i..i+9]
end
end
end
if $PROGRAM_NAME == __FILE__
main()
end
このプログラムの出力は
f(1) = 7182818284
f(2) = 8182845904
f(3) = 8747135266
f(4) = 7427466391
f(5) = 5966290435
f(6) = 2952605956
したがって, 答えは5966290435になります.