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

• 考えたこと
  • 回文検出のロジックを考えて実装
  • 10進数の場合、2進数の場合どちらも回文になっていれば加算

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

p palindromes?(45854.to_s)
p palindromes?(45854.to_s(2))


ans = 0
(0..1_000_000).each do |n|
  if palindromes?(n.to_s) and palindromes?(n.to_s(2))
    puts n
    ans += n
  end
end

puts ""
puts ans

• 考えたこと
  • ある自然数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^2 = 2 \cdot ( a \cdot p + b \cdot p - a \cdot b) が出るので、それを満たす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

• 考えたこと
  • チャンパノウン数 - MathWills
  • これは愚直にいったが、もっと早い解き方がありそう

d = ""
(0..10**6).to_a.each do |n|
  d += n.to_s
  break if d.length > 1000000
end

# d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000
puts d[0,100]

puts d[10**0].to_i
puts d[10**1].to_i
puts d[10**2].to_i
puts d[10**3].to_i
puts d[10**4].to_i
puts d[10**5].to_i
puts d[10**6].to_i

puts (0..6).to_a.map{|i| d[10**i].to_i}.inject(&:*)