{eの値中の最初の連続する10桁の素数}.com

\![macOS-11.1](<https://img.shields.io/badge/macOS-11.1-brightgreen>) \![ruby-2.7.2p137](<https://img.shields.io/badge/ruby-2.7.2p137-brightgreen>) 


# Preface (はじめに)

もう一方の課題であるGoogleの求人広告をRubyで解きたいと思います.


# Google recruit

Googleの求人広告とは
![exp_prime.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/266153/60294760-8d4d-0b58-d865-68308153bd68.jpeg)
上の写真のことです.和訳すると, {$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`に保存して, コードを動かすたびに読み込ませるようにします.

```ruby
def read_exp 
  exp = File.read('exp.txt')
  return exp.delete('.')
end
```

参考: [ネイピア数 &#x2013; Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%8D%E3%82%A4%E3%83%94%E3%82%A2%E6%95%B0)


## 素数判定

引数nが素数かどうかを判定する関数を作ります.

nが素数であるには, 2 ~ n-1のすべての数で割り切れないことが条件です.
なので, 2 ~ n-1までの数の剰余を求めその全てが0でなければ素数という関数を作ります.

```ruby
def prime? n
  for i in 2..n-1 do
    return false if n % i == 0
  end
  return true
end
```

ただ, これでは無駄な計算をしてしまいます.なので, 反復の上限は$\sqrt{n} + 1$とします.

<details>
<summary>どうして, このようにするかの説明は以下にします.</summary>
下の図は 緑が$xy = 6$の第一象限, 赤が$y = x$を表しています.
<img src=https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/266153/39dd3558-6ab0-956b-30fa-60bf6ab15d0e.png width=70%>
このとき, 緑線は赤線を軸に軸対象です. 
つまり, 二つのグラフの交点$(x, y) = (\sqrt{6}, \sqrt{6})$を境に, 順序は逆ですが同じ数同士の乗算を行っているということです. <br>
それなら半分だけを調べればいいので, 素数判定を行う範囲を2 ~$\sqrt{n} + 1$とすればいいということになります.
</details>
<br>
<br>
また, 2を超えた数での素数はすべて奇数であるため, 2つ飛ばしで剰余を求めるようにします.

```ruby
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

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

```ruby: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](https://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$の値の可能性が高そうです.
ただ, それ以外の共通点がわかりません. 

-----
<br>
<br>
悩みつくしたので, ggりました.
各桁の数を総和すると49になるのが共通点だそうです.

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

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


# 参考資料

-   [Google recruit problem, exp and prime](https://qiita.com/daddygongon/items/ba94b0f2a73990fc6a07)
-   [有名なＧｏｏｇｌｅの求人広告／ネイピア数の値と10桁の素数](http://blog.livedoor.jp/blogartmode/archives/51763852.html)