プロジェクト・オイラー(036-040)

• 考えたこと
  • まず回文検出のための大道具を用意する 回文検出

• 考えたこと
  • ある自然数Nが素数がどうか調べるときは、試し割りを√Nまでやればよいので
  • 切り詰め可能素数が11個見つかるまでそれをメモ化しながらやっていった

def prime?(n, primes)
  if n == 1
    false
  elsif primes.include?(n)
    true
  else
    m = Math.sqrt(n).round
    2.upto(m) do |step|
      if step != 2 and step % 2 == 0
        next
      else
        if n % step == 0
          return false
        else
          next
        end
      end
    end
    true
  end
end

def truncate_prime?(n, primes)
  arr  = n.to_s.split("")
  head = arr.dup
  tail = arr.dup

  while not head.empty?
    unless prime?(head.join.to_i, primes)
      return false
    end
    head.pop
  end
  while not tail.empty?
    unless prime?(tail.join.to_i, primes)
      return false
    end
    tail.shift
  end
  true
end

primes = []
truncate_primes = []

number = 2

while truncate_primes.length != 11
  if prime?(number, primes)
    # add primes into memo
    primes << number
    puts "  Prime found! => #{number}"
    if truncate_prime?(number, primes) and number > 9
      truncate_primes << number
      puts "* Tr prime found! => #{number}"
    end
  end
  number += 1
end

p truncate_primes
p truncate_primes.inject(&:+)

• 考えたこと

• 考えたこと
  • 与えられた式を変形すると が出るので、それを満たすpを３重ループで探索した

require 'set'

# a**2+b**2=c**2
# a+b+c=p

max_ans = {:pi => 0, :ans => 0}

for pi in 1..1000
  ans = Set.new
  for ai in 1..pi
    for bi in 1..(pi-ai)
      #puts "a=#{ai},b=#{bi}"
      if pi**2 == (2*pi*(ai+bi)-2*ai*bi)
        # puts "p = #{pi}"
        # puts "pi^2 = #{pi**2}"
        # puts "==> (pi^2)/2 = #{(pi**2)/2}"
        # puts "a=#{ai},b=#{bi},c=#{pi-ai-bi}"
        ans << [ai,bi,pi-ai-bi].sort.join(":")
      end
    end
  end
  puts "ans = #{ans.length}"
  if max_ans[:ans] < ans.length
    max_ans[:pi] = pi
    max_ans[:ans] = ans.length
  end
end

p max_ans

• 考えたこと