プロジェクト・オイラー(051-055)

[プロジェクト・オイラー]

プロジェクト・オイラー(051-055)

  Problem 51 「素数の桁置換」

Probem

 *3の第1桁を置き換えることで, 13, 23, 43, 53, 73, 83という6つの素数が得られる.
  
 56**3の第3桁と第4桁を同じ数で置き換えることを考えよう.
 この5桁の数は7つの素数をもつ最初の例である: 56003, 56113, 56333, 56443, 56663, 56773, 56993. よって, この族の最初の数である56003は, このような性質を持つ最小の素数である.
  
 桁を同じ数で置き換えることで8つの素数が得られる最小の素数を求めよ. (注:連続した桁でなくても良い)

Answer

  Problem 52 「置換倍数」

Probem

 125874を2倍すると251748となる. これは元の数125874と順番は違うが同じ数を含む.
  
 2x, 3x, 4x, 5x, 6x が x と同じ数を含むような最小の正整数 x を求めよ.

Answer

def digits_match?(x)
  x1 = (1*x).to_s.split("").sort
  x2 = (2*x).to_s.split("").sort
  x3 = (3*x).to_s.split("").sort
  x4 = (4*x).to_s.split("").sort
  x5 = (5*x).to_s.split("").sort
  x6 = (6*x).to_s.split("").sort

  if x1==x2 and x2==x3 and x3==x4 and x4==x5 and x5==x6
    true
  else
    false
  end
end

for x in 1..10**10
  if digits_match?(x)
    puts x
    break
  end
end

  Problem 53 「組み合わせ選択」

Probem

 12345から3つ選ぶ選び方は10通りである.
  
 123, 124, 125, 134, 135, 145, 234, 235, 245, 345.
 組み合わせでは, 以下の記法を用いてこのことを表す: 5C3 = 10.
  
 一般に, r ≤ n について nCr = n!/(r!(n-r)!) である. ここで, n! = n×(n−1)×...×3×2×1, 0! = 1 と階乗を定義する.
  
 n = 23 になるまで, これらの値が100万を超えることはない: 23C10 = 1144066.
  
 1 ≤ n ≤ 100 について, 100万を超える nCr は何通りあるか?

Answer

MOD = 1_000_000_007

class Combination
  def initialize(n)
    @fact = (1..n).to_a
    @fact.each_with_index do |e, idx|
      @fact[idx] = @fact[idx] * @fact[idx-1] % MOD if idx > 0
    end
  end

  def choose(n, r)
    return 0 if not (0 <= r and r <= n)
    return 1 if r == 0 or r == n
    fact(n) * inverse( fact(r) * fact(n-r) % MOD ) % MOD
  end

  def fact(n)
    @fact[n-1]
  end

  def inverse(x)
    pow(x, MOD-2)
  end

  def pow(x, n)
    ans = 1
    while n > 0
      ans = ans * x % MOD if n.odd?
      x = x * x % MOD
      n >>= 1
    end
    ans
  end
end

ans  = 0
comb = Combination.new(100)
for n in 1..100
  for r in 1..n
    ncr = comb.choose(n,r)
    if ncr > 10**6
      puts "#{n}C#{r} = #{ncr}"
      ans += 1
    end
  end
end
puts ans

  Problem 54 「ポーカーハンド」

Probem

 カードゲームのポーカーでは, 手札は5枚のカードからなりランク付けされている. 役を低い方から高い方へ順に並べると以下である.
  
 役無し(ハイカード): 一番値が大きいカード
 ワン・ペア: 同じ値のカードが2枚
 ツー・ペア: 2つの異なる値のペア
 スリーカード: 同じ値のカードが3枚
 ストレート: 5枚の連続する値のカード
 フラッシュ: 全てのカードが同じスート (注: スートとはダイヤ・ハート・クラブ/スペードというカードの絵柄のこと)
 フルハウス: スリーカードとペア
 フォーカード: 同じ値のカードが4枚
 ストレートフラッシュ: ストレートかつフラッシュ
 ロイヤルフラッシュ: 同じスートの10, J, Q, K, A
 ここでカードの値は小さい方から2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, Aである. (訳注：データ中で10は'T'と表される)
  
 もし2人のプレイヤーが同じ役の場合には, 役を構成する中で値が最も大きいカードによってランクが決まる: 例えば, 8のペアは5のペアより強い (下の例1を見よ). それでも同じランクの場合には (例えば, 両者ともQのペアの場合), 一番値が大きいカードによってランクが決まる (下の例4を見よ). 一番値が大きいカードが同じ場合には, 次に値が大きいカードが比べれられ, 以下同様にランクを決定する.
  
 例:

 poker.txtには1000個のランダムな手札の組が含まれている. 各行は10枚のカードからなる (スペースで区切られている): 最初の5枚がプレイヤー1の手札であり, 残りの5枚がプレイヤー2の手札である. 以下のことを仮定してよい
  
 全ての手札は正しい (使われない文字が出現しない. 同じカードは繰り返されない)
 各プレイヤーの手札は特に決まった順に並んでいるわけではない
 各勝負で勝敗は必ず決まる
 1000回中プレイヤー1が勝つのは何回か? (訳注 : この問題に置いてA 2 3 4 5というストレートは考えなくてもよい)

Answer

  Problem 55 「Lychrel数」

Probem

 47とその反転を足し合わせると, 47 + 74 = 121となり, 回文数になる.
  
 全ての数が素早く回文数になるわけではない. 349を考えよう,
  
 349 + 943 = 1292,
 1292 + 2921 = 4213
 4213 + 3124 = 7337
 349は, 3回の操作を経て回文数になる.
  
 まだ証明はされていないが, 196のようないくつかの数字は回文数にならないと考えられている. 反転したものを足すという操作を経ても回文数にならないものをLychrel数と呼ぶ. 先のような数の理論的な性質により, またこの問題の目的のために, Lychrel数で無いと証明されていない数はLychrel数だと仮定する.
  
 更に, 10000未満の数については，常に以下のどちらか一方が成り立つと仮定してよい.
  
 50回未満の操作で回文数になる
 まだ誰も回文数まで到達していない
 実際, 10677が50回以上の操作を必要とする最初の数である: 4668731596684224866951378664 (53回の操作で28桁のこの回文数になる).
  
 驚くべきことに, 回文数かつLychrel数であるものが存在する. 最初の数は4994である.
  
 10000未満のLychrel数の個数を答えよ.
  
 注: 2007/04/24にLychrel数の理論的な性質を強調するために文面が修正された.

Answer

def palindromes?(n_str)
  if n_str.size.odd?
    mid = n_str.size/2
    first_half = n_str[0, mid]
    second_half = n_str[mid+1, mid]
    return first_half == second_half.reverse
  end
  if n_str.size.even?
    mid = n_str.size/2
    first_half = n_str[0, mid]
    second_half = n_str[mid, mid]
    return first_half == second_half.reverse
  end
end

def reverse_sum(n)
  n + n.to_s.reverse.to_i
end

def lychrel?(n)
  50.times{
    n = reverse_sum(n)
    if palindromes?(n.to_s)
      return false
    end
  }
  return true
end

ans = 0
(0..10_000).each do |n|
  if lychrel?(n)
    puts n
    ans += 1
  end
end
puts ""
puts ans