[プロジェクト・オイラー]
n桁パンデジタルであるとは, 1からnまでの数を各桁に1つずつ持つこととする.
#下のリンク先にあるような数学的定義とは異なる
例えば2143は4桁パンデジタル数であり, かつ素数である. n桁（この問題の定義では9桁以下）パンデジタルな素数の中で最大の数を答えよ.
|
+
|
解答
|
|
|
- 考えたこと
- 問題文から、9桁以上のパンデジタル素数はなさそう
- なので9〜1桁まで下降していき、それぞれの桁数を1回だけ使った数字を素数判定すればOKか
def prime(n, primes)
if n == 1
return false,primes
elsif primes.include?(n)
return true,primes
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,primes
else
next
end
end
end
primes << n
return true,primes
end
end
primes=[]
9.downto(1) do |digit|
(1..digit).to_a.permutation(digit) do |arr|
n = arr.join.to_i
is_prime,primes = prime(n, primes)
if is_prime
p n
end
end
end
puts primes.max
|
三角数のn項は tn = ½n(n+1)で与えられる. 最初の10項は
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
である.
単語中のアルファベットを数値に変換した後に和をとる. この和を「単語の値」と呼ぶことにする. 例えば SKY は 19 + 11 + 25 = 55 = t10である. 単語の値が三角数であるとき, その単語を三角語と呼ぶ.
16Kのテキストファイル words.txt 中に約2000語の英単語が記されている. 三角語はいくつあるか?
|
+
|
解答
|
|
|
- 考えたこと
- 先に三角数のテーブルを作り確保しておく
- 「単語の値」の値もメモ化してとっておく
ALPHA_TABLE = ('a'..'z').to_a
$word_value_table = {}
def C(n)
n*(n+1)/2
end
$triangles = (1..10**3).map do |n|
{n=>C(n)}
end
def word_value(s)
word = s.split("").map do |c|
c.downcase
end.sort
unless $word_value_table.has_key?(word)
wv = word.map do |c|
ALPHA_TABLE.index(c)+1
end.inject(&:+)
$word_value_table[word] = wv
end
$word_value_table[word]
end
#wv = word_value("SKY")
#puts $triangles.detect{|hash| hash.values.include? wv}.keys
ans = 0
File.open("p042_words.txt", "r") do |f|
s = f.read.gsub(/\"/, "")
s.split(",").each do |word|
wv = word_value(word)
triangle = $triangles.detect{|hash| hash.values.include? wv}
unless triangle.nil? or triangle.empty?
ans += 1
end
end
end
puts ans
|
数1406357289は0から9のパンデジタル数である (0から9が1度ずつ現れるので). この数は部分文字列が面白い性質を持っている.
d1を上位1桁目, d2を上位2桁目の数とし, 以下順にdnを定義する. この記法を用いると次のことが分かる.
d2d3d4=406 は 2 で割り切れる
d3d4d5=063 は 3 で割り切れる
d4d5d6=635 は 5 で割り切れる
d5d6d7=357 は 7 で割り切れる
d6d7d8=572 は 11 で割り切れる
d7d8d9=728 は 13 で割り切れる
d8d9d10=289 は 17 で割り切れる
このような性質をもつ0から9のパンデジタル数の総和を求めよ.
五角数は Pn = n(3n-1)/2 で生成される. 最初の10項は
1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...
である.
P4 + P7 = 22 + 70 = 92 = P8 である. しかし差 70 - 22 = 48 は五角数ではない.
五角数のペア Pj と Pk について, 差と和が五角数になるものを考える. 差を D = |Pk - Pj| と書く. 差 D の最小値を求めよ.
|
+
|
解答
|
|
|
- 考えたこと
- 愚直に五角数を出して計算しても計算量がかかりすぎてだめっぽい
|
三角数, 五角数, 六角数は以下のように生成される.
三角数 Tn=n(n+1)/2 1, 3, 6, 10, 15, ...
五角数 Pn=n(3n-1)/2 1, 5, 12, 22, 35, ...
六角数 Hn=n(2n-1) 1, 6, 15, 28, 45, ...
T285 = P165 = H143 = 40755であることが分かる.
次の三角数かつ五角数かつ六角数な数を求めよ.
|
+
|
解答
|
|
|
- 考えたこと
- それぞれの数列を集合と考えれば、求める「三角数かつ五角数かつ六角数な数」はその積集合になるはず
- n=1～10^5までの数列のテーブルを作って、積集合を求めた中で40755以上になるものをとればよい
def T(n)
n*(n+1)/2
end
def P(n)
n*(3*n-1)/2
end
def H(n)
n*(2*n-1)
end
TT = (1..10**5).map{|n| T(n)}
PT = (1..10**5).map{|n| P(n)}
HT = (1..10**5).map{|n| H(n)}
p (TT&PT&HT).detect{|x| x>40755}
|