Googleの問題を解く

問題

「e(自然対数の底)の値で連続する10桁の数のうち、最初の素数」を求める。

素数判定

回答

def getNums()
  line = readlines
  len = line.length
  num = ''

  (0..len-1).each do |i|
    num = num + line[i].chomp
  end

  return num
end

def prime?(num)
  (2..Math.sqrt(num).to_i).each do |i|
    if(num%i == 0)
      return false
    end
  end
  return true
end

digits = 10

if $PROGRAM_NAME == __FILE__
  num = getNums().delete('.')
  res = 0

  (0..num.length-digits).each do |i|
    res = num[i, digits].to_i
    prime?(res) ? break : next 
  end

  puts "e(自然対数の底)の値で連続する10桁の数のうち, 最初の素数は#{res}"
end

解説

問題が、外部ファイルに記述された e の数字を入力としていたので getNums() で複数行の入力を結合するようになっています。が、まぁそこは気にせずに、数値の標準入力を受け取ります。

prime? の実装

require 'prime' によって Prime.prime?(n) が利用でき、高速に素数判定できますが面白く無いので今回は利用しません。自力で prime? を実装します。

def prime?(num)
  (2..Math.sqrt(num).to_i).each do |i|
    if(num%i == 0)
      return false
    end
  end
  return true
end

短っ!いや、もっと高速にするなら 偶数は弾く とかもあるけど、とりあえずこれでいいや。

理論的には、自分より低い数字で割り切れるかを見て、 true or false を出力しているだけ。

(2..Math.sqrt(num).to_i).each do |i|

(2..Math.sqrt(num).to_i).each do |i| ここが重要な部分です。
(2..num).each do |i| とするのが理論的ですが、これだと桁が多いときに処理が終わりません。いや、終わるけど時間がかかりすぎます。

Math.sqrt(num).to_i までの演算でいい理由

合成数(素数とは逆の意味) に関する性質$x$ が合成数ならば $\sqrt{x}$ 以下の約数を持つ
を利用しています。ですので、 num が合成数(=素数でない)なら

(2..Math.sqrt(num).to_i).each do |i|
  if(num%i == 0)
    return false
  end
end

ここで引っかかって false を返します。逆に、ここをすり抜けた num は合成数でない(=素数)ので、 true を返します。

実行結果

テキストファイルに e の値を記述します。

2.71828182845904523536028747135266249775
7247093699959574966967627724076630353547
5945713821785251664274274663919320030599
2181741359662904357290033429526059563073
81323286279434907632338298807531952510190

これをプログラムに渡してあげます。

$ ruby google_recruit.rb < in.txt
e(自然対数の底)の値で連続する10桁の数のうち, 最初の素数は7427466391

答えは 7427466391 である!

発展課題!?

この問題には続きというか、この問題の回答者だけに次の問題が用意されていたらしい。それが次の問題。

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

なるほどー。規則性を見つけるやつ。そして f(1)=7182818284 に見覚えがあった。
上の問題の e にこの数字あったやん
f(2)=8182845904 これもあるやん。

解く

規則性を見つけましょう。

何桁目にあるか

小数第何位〜何位にその数が現れているかを探しましょう。

def getNums()
  line = readlines
  len = line.length
  num = ''

  (0..len-1).each do |i|
    num = num + line[i].chomp
  end

  return num
end

if $PROGRAM_NAME == __FILE__
  num = getNums().delete('.')

  ["7182818284", "8182845904", "8747135266", "7427466391"].each do |i|
    pos = num.index(i)
    puts "#{i} -> #{pos} ~ #{pos+(10-1)}"
  end
end

こんなん作って

$ ruby google_recruit_find.rb < google_recruit_in.txt
7182818284 -> 1 ~ 10
8182845904 -> 5 ~ 14
8747135266 -> 23 ~ 32
7427466391 -> 99 ~ 108

さっぱりわからん。笑

テレビのクイズ問題にあるやつやろ

こういうのは大体、足したらいいねん

def getNums()
  line = readlines
  len = line.length
  num = ''

  (0..len-1).each do |i|
    num = num + line[i].chomp
  end

  return num
end

if $PROGRAM_NAME == __FILE__
  num = getNums().delete('.')

  ["7182818284", "8182845904", "8747135266", "7427466391"].each do |n|
    sum = 0
    (0..9).each do |i|
      sum += n[i].to_i
    end
    puts "#{n} -> #{sum}"
  end
end

こんなん作って

$ ruby google_recruit_sum.rb < google_recruit_in.txt
7182818284 -> 49
8182845904 -> 49
8747135266 -> 49
7427466391 -> 49

天才かもしれん (テレビの見過ぎ)
各桁の合計(10桁分)が49になる数字を e から探して5番目が答え。

回答

Ruby でこれを探すプログラムを書いて、回答を得る。

def getNums()
  line = readlines
  len = line.length
  num = ''

  (0..len-1).each do |i|
    num = num + line[i].chomp
  end

  return num
end

digits = 10

if $PROGRAM_NAME == __FILE__
  e = getNums().delete('.')
  num = 0
  (1..e.length-digits).each do |i|
    sum = 0
    (0..digits-1).each do |j|
      sum += e[i, digits][j].to_i
      break if sum > 49
    end
    puts "f(#{num = num.succ})=#{e[i, digits]}" if sum == 49
  end
end

こんな感じ？？

$ ruby google_recruit2.rb < google_recruit_in.txt
f(1)=7182818284
f(2)=8182845904
f(3)=8747135266
f(4)=7427466391
f(5)=5966290435
f(6)=2952605956

答えは 5966290435 である!