!macOS-11.1 !ruby-2.7.2p137

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

参考: ネイピア数 – Wikipedia

素数判定

引数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

では, これまでの関数を組み合わせて, プログラムを完成させます.

exp_prime.rb

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になるのが共通点だそうです.

では, その情報をもとにプログラムを作ります.

google_recruit.rb

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になります.

参考資料