[プロジェクト・オイラー]
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}
|