読者です 読者をやめる 読者になる 読者になる

mu chance or much chance ?

日々の戯れ言

Project Euler 49

Project Euler

Problem49を解きました.

  • Prime permutations

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

https://projecteuler.net/problem=49

問題は「各項がそれぞれ素数であり,かつ他の項の置換で表される数列の3つの項を連結した12桁の数を求めよ.」.

require 'prime'
array = Prime.each(9999).to_a - Prime.each(999).to_a

array.length.times do |i|
  str1 = array[i].to_s.split('').sort.join
  for j in i + 1..array.length - 1 do
    str2 = array[j].to_s.split('').sort.join
    num = (array[j] * 2 - array[i]) # c = 2 * b - a (c - b = b - a)
    if str1 == str2 && array.include?(num) && str1 == num.to_s.split('').sort.join
      p array[i].to_s + array[j].to_s + num.to_s
    end
  end
end

今プログラムを実行すると,
例で挙げられている"148748178147"も出力されます.

a1, a2, a3の関係は「a3 - a2 = a2 - a1」から,
「a3 = 2 * a2 - a1」となる.
あとは条件に合う4桁の素数を求めれば,
結構簡単に求められます.