最終更新: 2011-03-12T02:24+0900
分母を一番深いところから順番に計算していく。
a = ([2] + (1..33).map{|k| [1,2*k,1] }.inject(&:+)).reverse
denom, numer = *a.inject([0,1]){|nd, x| [nd[1], x*nd[1]+nd[0]] }
require 'rational'
p Rational(numer, denom).numerator.to_s.chars.inject(0){|sum,c| sum - ?0 + c[0] }
xを増やしながらの総当たりで、最後に見つかった Dが答え。と思ったんだけど Dが見つかるペースがどんどこ落ちていく。一日以上かけても 969個の Dのうち 270個が残ってる。
Problem 18の延長で以前解いた。
前問に引き続いて、数学でもプログラミングでもなく、オラクルで。
最終更新: 2011-03-12T03:46+0900
"exactly five" って書いてあるから、同じ数字の並べ替えで作れる立方数が 6以上あってもダメだと思うんだ。
memo = Hash.new{|h,k| h[k] = [] }
n = 0
k_length = 1
loop{
n += 1
cube = n*n*n
k = cube.to_s.split(//).sort.join('')
if k.length != k_length
answer = memo.values.select{|cubes| cubes.size == 5 }
if not answer.empty?
answer.each{|cubes| p cubes }
exit
end
memo.clear
k_length = k.length
end
memo[k] << cube
}
# (x-1)/x <= log10(n) < 1 (n = ?,?,...)
count = 0
x = 0
loop{
x += 1
boundary = (x-1.0)/x
lower_bound = (1..9).to_a.reverse.find{|n| Math.log10(n) < boundary } || 0
count += 9 - lower_bound
break if lower_bound == 9
}
p count
またまた「Dreamshire | Project Euler Problem 63 Solution」の解答を検討してみたい。二重のループなんてない。logの計算だって 9回だけ。どういうことだ？
というストーリーをひねり出した。「9は 10より 0.046(=1-0.954)程度小さい数だ」ってくだりがいかにも苦しい。小数だからごまかしがきいてるけど、ぴったり 10一個分小さくなる場合は n桁、n-1桁、どっち？ (たぶんまだ n桁だな。1^1がそう)
ともあれ、明かされてみればワンライナーの問題だったよ。
p (1..9).inject(0){|sum,n| sum + (1/(1-Math.log10(n))).floor }
常用対数を直接求めるメソッドが用意されてるあたりが Rubyだなとおもた。
連分数っていうらしい。a_nの求め方、a += 1 while 0 <= r - (n - d*(a+1))**2 の条件部分が判然としない。スクリプト中のコメントにあるように、対象としてるルートの係数が必ず約分されて 1になることも理解できてない。
def next_frac(r, n, d) # (√r + n) / d = a + 1 / [(√r + n_) / d_]
a = 0
a += 1 while 0 <= r - (n - d*(a+1))**2
d_ = (r - (n - d*a)**2) / d
raise if (r - (n - d*a)**2) % d != 0 # why OK?
n_ = -(n - d*a)
return a, r, n_, d_
end
def period_of(r)
rnd = [r, 0, 1]
arr = []
loop{
a, *rnd = next_frac(*rnd)
arr << rnd
period = arr.size-1 - arr.index(rnd)
return period if 0 != period
return 0 if rnd[2] == 0 # √r is rational.
}
end
count = 0
1.upto(10000){|n|
count += 1 if period_of(n) % 2 == 1
}
p count
ところで、この問題を解くときに Math.sqrtを使うのってインチキくさくない？(だから使ってないんだけど)
最終更新: 2011-03-02T05:24+0900
何も考えずにコーディングしただけ。一瞬 CPUが考え込みます。
generators = [
lambda{ n = 0
lambda{ n+=1; n*(n+1)/2 }
}.call,
lambda{ n = 0
lambda{ n+=1; n*n }
}.call,
lambda{ n = 0
lambda{ n+=1; n*(3*n-1)/2 }
}.call,
lambda{ n = 0
lambda{ n+=1; n*(2*n-1) }
}.call,
lambda{ n = 0
lambda{ n+=1; n*(5*n-3)/2 }
}.call,
lambda{ n = 0
lambda{ n+=1; n*(3*n-2) }
}.call,
]
# 数を準備
d4polynumbers = generators.map{|g|
() while (p = g.call) < 1000
a = [p]
a.push(p) while (p = g.call) < 10000
a
}
# 端緒(の集まり)
bunch_of_chain = d4polynumbers[d4polynumbers.size-1].map{|p|
[[p, d4polynumbers.size-1]]
}
# 端緒を伸ばすもの
extender = lambda{|chain, pool|
xx = chain.last.first.to_s[-2,2]
( (0...(pool.size)).to_a - chain.map{|_| _.last } ).map{|i|
[i, pool[i]]
}.map{|i, nums|
nums.find_all{|num|
num.to_s[0,2] == xx
}.map{|num|
chain + [[num, i]]
}
}.inject(&:+)
}
# 伸ばしていく
(d4polynumbers.size-1).times{
bunch_of_chain = bunch_of_chain.map{|chain|
extender[chain, d4polynumbers]
}.inject(&:+)
}
# 輪っか？
bunch_of_cyclic_chain = bunch_of_chain.reject{|chain|
chain.first.first.to_s[0,2] != chain.last.first.to_s[-2,2]
}
# 出力
bunch_of_cyclic_chain.each{|chain|
puts chain.map{|a,_| a }.join("\t")
puts chain.map{|_,b| "P#{b+3}" }.join("\t")
puts "sum: #{chain.map{|a,_| a }.inject(&:+)}"
}
先は長いのにもう失速してる。「良いもの。悪いもの。: Project Eulerを100問解いてみた」テトレーションとか聞いたこともない単語なんだけど……。
中学生の時に 3^{50} の一の位は何かという問題が出た。でも Problem 188は何乗したらいいかもわからない。下手の考え休むに似たりっていうけどどうしたもんかなあ。ない知恵を絞るのも悪くないと思うんだけど。
最終更新: 2011-02-20T21:45+0900
10%未満っていうのは絶妙なポイントなのかな。全然 9%未満に落ちない。
def prime? x
return false if x < 2
return true if x == 2
quo, rem = x.divmod(2)
return false if rem == 0
t = 1
while t < quo
t += 2
quo, rem = x.divmod(t)
return false if rem == 0
end
return true
end
x, t = 1, 0
primes_on_diagonals = 0
loop{
t += 2
3.times{
x += t
primes_on_diagonals += 1 if prime? x
}
x += t
puts "#{primes_on_diagonals} primes out of #{2*t+1} (#{100*primes_on_diagonals/(2*t+1)}%, side length=#{t+1})"
exit if 100 * primes_on_diagonals / (2*t+1) < 10
}
encrypted_text = [79,59,12,...,22,73,0,0] # last 2 elements are padding.
text = ""
0.step(encrypted_text.size-1, 3){|i|
text += (encrypted_text[i+0] ^ (71 ^ " "[0])).chr
text += (encrypted_text[i+1] ^ (79 ^ " "[0])).chr
text += (encrypted_text[i+2] ^ (68 ^ " "[0])).chr
}
text.chop!.chop! # remove padding
puts text
puts "sum: #{text.bytes.inject(:+)}"
1を満たす素数を発見しながらそれを使って、1の集合から2へ、2の集合から3へ、3の集合から4へ、要素をプロモートしていけばよさそう。
# 寝る前にやる。
寝てしまった。答えが出ない。素数を分割するんでなく、素数のペアを組み合わせて素数かどうか判定した方がいいかもしれない。そろそろ身にしみて理解してきたけど、素数って印象よりありふれ過ぎてる。
ちょっとくらい時間がかかってもいーやって考えてたけど、何日もかけても四つ組みが 7つと、五つ組が 0個しか見つからないことがわかったので、1分以内に答えを出すべくもうちょっと考える。
def prime? x
return false if x < 2
return true if x == 2
quo, rem = x.divmod(2)
return false if rem == 0
t = 1
while t < quo
t += 2
quo, rem = x.divmod(t)
return false if rem == 0
end
return true
end
set012 = [[],[3],[]]
require 'mathn'
Prime.new.each{|prime|
break if 10000 <= prime
dmod3 = prime.to_s.bytes.inject(0){|sum,byte| sum+byte-?0 } % 3
set012[dmod3] << prime
}
set1, set2 = set012[1], set012[2]
set2[0] = 3
# set1 = [3,7,13,...]
# set2 = [3,5,11,...]
make_group_of_two = lambda{|set|
pair = {}
0.upto(set.size-2){|i|
(i+1).upto(set.size-1){|j|
if prime?("#{set[i]}#{set[j]}".to_i) and prime?("#{set[j]}#{set[i]}".to_i)
(pair[[set[i]]]||=[]) << set[j]
end
}
}
return pair
}
group1, group2 = make_group_of_two.call(set1), make_group_of_two.call(set2)
extend_group = lambda{|g|
group = {}
g.each_pair{|rest, last1s| # rest + one of last1s = group
last1s.each{|last1|
next1s = last1s
gg, out = rest.clone, last1
gg.size.times{|i|
gg[gg.size-1-i], out = out, gg[gg.size-1-i]
next1s &= g[gg]||[]
}
if ! next1s.empty?
group[rest+[last1]] = next1s
end
}
}
return group
}
group1, group2 = extend_group.call(group1), extend_group.call(group2) # sets of 3 primes
group1, group2 = extend_group.call(group1), extend_group.call(group2) # sets of 4 primes
group1, group2 = extend_group.call(group1), extend_group.call(group2) # sets of 5 primes
printer = lambda{|rest, last1s|
last1s.each{|last1|
puts %[#{rest.inject(&:+)+last1}:\t#{rest.join("\t")}\t#{last1}]
}
}
group1.each(&printer)
group2.each(&printer)
分単位の時間で答えはでたけどもその五つ組の合計が意外に大きくて、10000以上の素数を組に加えても最小の組み合わせになりうる。計算量の増大の仕方がひどくて、これ以上桁数を増やして試行するのは無理だというのに。
じゃないよね。
\begin{array}{rcl}
q & = & a_0 + 10a_1 + 10^2a_2 +……+ 10^na_n \quad\mbox{(}a_n\mbox{は 0以上 9以下の整数)}\\
& = & (a_0 + a_1 + a_2 +……+ a_n) + 9a_1 + 99a_2 +……+(10^n-1)a_n\\
\end{array}
a_0+a_1+a_2+……+a_n が 3の倍数の整数 qは 3の倍数です。
たしか 4の倍数についても同じような判定規則があった気がした。忘れたけど。
たしか 5の倍数についてもどこかの桁を見るだけで(略
4は 100を作るから下2桁だけ。5は 10を作るから下1桁だけを見ればいい。
一番時間を食ってるのは make_group_of_two. 異なる二要素の組み合わせということで n^2-n 回の素数判定を行ってる。素数判定自体も nの大きさに比例する(※1:1ではないけど)ループを持っている。大変なはずだ。
とりあえず、今の素数判定より賢い素数判定があるのはわかってるけどわからないので使ってない。(注:わかる => 知ってる, 理解できる) 丁寧にコードを読んだらわかるかもだけどそれはチートっぽい。大学入試の数論関係の問題だって、解答をチラ見したら誰だって理解できんだよ。
最終更新: 2011-02-12T22:42+0900
Bignumはできれば使いたくない。aが 100未満なので 8桁ずつ。
answer = [0, 0, 0] # sum, a, b
1.upto(99){|a|
digits = "1"
1.upto(99){|b|
sum = 0
carry = 0
0.step(digits.size-1, 8) {|i|
l, r = [0, digits.size-i-8].max, digits.size-i
carry, digits8 = (digits[l...r].to_i * a + carry).divmod(100000000)
digits8 = "00000000#{digits8}"[-8,8]
digits[l...r] = digits8
digits8.each_byte{|byte|
sum += byte - ?0
}
}
if carry != 0
digits8 = carry.to_s
digits = digits8 + digits
digits8.each_byte{|byte|
sum += byte - ?0
}
end
if answer[0] < sum
*answer = sum, a, b
end
}
}
p answer
とかいいながら Bignum。
count = 0
numer, denom = 1, 1
1000.times{
numer, denom = numer + denom + denom, numer + denom
count += 1 if numer.to_s.length != denom.to_s.length
}
p count
最終更新: 2011-02-10T04:56+0900
ただただ、手と CPUを動かすだけで精一杯。(頭は役に立ってないよ)
primes = [2]
is_prime = lambda{|x|
result = true
primes.each{|prime|
quo, rem = x.divmod(prime)
if rem == 0
result = false
break
end
break if quo < prime
}
return result
}
# replace 2 digits or 3 digits. キ・メ・ウ・チ
def find_8_prime_family(a)
return [] if a.size < 8
a.map!{|x| x.to_s }
h = Hash.new{|h,k| h[k] = [] }
# 2 digits
0.upto(a.first.size-3){|i|
(i+1).upto(a.first.size-2){|j|
h.clear
a.each do |prime|
if prime[i] == prime[j]
h[prime[0...i]+prime[(i+1)...j]+prime[(j+1)...(prime.size)]].push prime
end
end
h.each do |_,v|
return v if v.size == 8
end
}
}
# 3 digits
0.upto(a.first.size-4){|i|
(i+1).upto(a.first.size-3){|j|
(j+1).upto(a.first.size-2){|k|
h.clear
a.each do |prime|
if prime[i] == prime[j] and prime[j] == prime[k]
h[prime[0...i]+prime[(i+1)...j]+prime[(j+1)...k]+prime[(k+1)...(prime.size)]].push prime
end
end
h.each do |_,v|
return v if v.size == 8
end
}
}
}
return []
end
x = 1
start = 0 # start of primes of a width.
loop {
x += 2
next unless is_prime.call x
print "#{x}\r"
if primes[start].to_s.length != x.to_s.length
a = find_8_prime_family primes.last(primes.size-start)
if ! a.empty?
puts a.sort.join(" ")
exit
end
start = primes.size
end
primes.push x
}
桁数ごとに探索範囲を決めて、総当たり。
問題が xについても同じ数の組み合わせであることを求めてると思わなくてチェックしてないけど、結果的に xも 2x,3xなんかと同じ数字で構成されてた。
digits = 10
loop {
digits *= 10
(digits/2).upto((digits*10-1)/6){|x|
print "#{x}\r"
x2 = (x*2).to_s.split(//).sort
if [3,4,5,6].all?{|n|
x2 == (x*n).to_s.split(//).sort
} then
puts [1,2,3,4,5,6].map{|n| x*n }.join(" ")
exit
end
}
}
浮動小数点数なんてファジーなものを使っちゃったよ。Math.sqrtの使用をこれまで頑なに避けてたのも、結果が Floatになるからだったり。
count = 0
23.upto(100){|n|
cmb = 1.0
1.upto(n/2){|r|
cmb /= r
cmb *= (n-r+1)
count += (n-r == r) ? 1 : 2 if 1_000_000 < cmb
}
}
p count
問題文が難しかった。3割ぐらいは推測。
あっけなく答えが出たので to_s.reverse.to_i みたいなのをなくすべく、Integer#reverse を自作してみたら、かえって遅くなったし。
class Integer
# 負数については考えてない。
def reverse
x = 0
this = self
begin
this, rem = this.divmod(10)
x = 10*x + rem
end while 0 < this
x
end
end
count = 0
10.upto(10_000-1){|x|
is_lychrel = true
50.times{
x = x + x.reverse
if x == x.reverse
is_lychrel = false
break
end
}
count += 1 if is_lychrel
}
p count
最終更新: 2011-02-09T20:16+0900
時間がかかるので逐一進捗を表示してる。この問題に魔法の一手なんてあるのかね。
primes = []
is_prime = lambda{|x|
result = true
primes.each{|prime|
quotient, remainder = x.divmod(prime)
if remainder == 0
result = false
break
end
break if quotient < prime
}
return result
}
2.upto(999_999){|x|
primes.push x if is_prime.call x
}
puts "#{primes.size} primes under 1 million."
work = primes.dup
step = 0
primes_found = []
live_elements = work.size
while 0 < live_elements
step += 1
primes_found.clear
live_elements = 0
print "step #{step}\r"
0.upto(work.size-1-step){|i|
work[i] += primes[i+step]
if work[i] < 1_000_000
live_elements += 1
primes_found.push work[i] if is_prime.call work[i]
end
}
if primes_found.empty?
elsif primes_found.size < 10
puts "step #{step}: #{primes_found.join ' '}"
else
puts "step #{step}: #{primes_found.size} primes"
end
end
魔法の一手はなくても……
答えを出した後でググるのが楽しい。フォーラムは読んでないけど、多分これ以上ないっていうような答えが書いてありそうで、面白くなさそうな気がしてる。(理解できない数学的知識が使われてたら、print XXXXXXX(answer); って書かれてるのと変わらないから)
最終更新: 2011-02-09T01:05+0900
昨日よりちょっとはマシになったかと。アホすぎた素数判定を、素因数の数を数える処理と一体化した。でも 10秒以上かかります。
primes = [2]
have4primefactors = []
num_of_factors = lambda{|x|
prime_factors = 0
primes.each{|prime|
quotient, remainder = x.divmod(prime)
if quotient < prime
prime_factors += 1
break
end
if remainder == 0
prime_factors += 1
break if 4 < prime_factors
x /= prime while x % prime == 0
break if x == 1
end
}
return prime_factors
}
x = 2
loop {
x += 1
print "#{x}\r"
case num_of_factors.call(x)
when 1
primes.push x
have4primefactors.clear
when 4
have4primefactors.push x
p have4primefactors.first if have4primefactors.length == 4
else
have4primefactors.clear
end
}
恥ずかしいほどまっすぐで乱暴なスクリプトだけど、コンソールの表示も待てないくらいノーウェイトで答えが出るんだから仕方がない。
p (1..1000).inject(0){|sum,x| sum + x**x }
10秒くらいかかります。
primes = []
is_prime = lambda{|x|
result = true
primes.each{|prime|
quotient, remainder = x.divmod(prime)
if remainder == 0
result = false
break
end
break if quotient < prime
}
return result
}
2.upto(9999){|x|
primes.push x if is_prime.call x
}
primes_4digit = primes.last(primes.length - primes.rindex{|x| x < 1000 } - 1)
0.upto(primes_4digit.size-1){|i|
p = primes_4digit[i]
# next if p == 1487
(i+1).upto(primes_4digit.size-1){|j|
q = primes_4digit[j]
r = q + q - p
next if p.to_s.split(//).sort != q.to_s.split(//).sort or
q.to_s.split(//).sort != r.to_s.split(//).sort
k = nil
(j+1).upto(primes_4digit.size-1){|_k|
if r == primes_4digit[_k]
k = _k
break
elsif r < primes_4digit[_k]
break
end
}
if k
puts "#{p} #{q} #{r}"
# exit
end
}
}
最終更新: 2011-02-07T05:28+0900
squares[]はソート済みなのに .include?()でそれを活かせないのが不満。
primes = [] # Omit 2. Even prime is not needed.
squares = [1]
def prime?(n)
return false if 0 == n%2
3.step(n/2, 2) {|x|
return false if 0 == n%x
}
return true
end
x = 1
loop {
x += 2
squares.push((squares.size+1)**2) if squares.last < x
if prime?(x)
primes.push x
next
end
print "#{x}\r"
next if primes.any?{|prime| prime < x and squares.include?((x-prime)/2) }
p x # answer
break
}
何の工夫もないのですんごく時間がかかる。
def prime_gt2?(n)
return false if 0 == n%2
x, upper_bound = 3, n/2
while x <= upper_bound
upper_bound, remainder = n.divmod(x)
return false if 0 == remainder
x += 1
end
return true
end
primes = [2]
have4primefactors = []
have4primefactor = lambda{|x|
num_of_factors = 0
primes.each{|prime|
if x % prime == 0
num_of_factors += 1
break if 4 < num_of_factors
x /= prime while x % prime == 0
end
}
return num_of_factors == 4
}
x = 2
loop {
x += 1
print "#{x}\r"
if prime_gt2? x
primes.push x
have4primefactors.clear
elsif have4primefactor.call(x)
have4primefactors.push x
p have4primefactors.first if have4primefactors.length == 4
else
have4primefactors.clear
end
}
最終更新: 2011-02-05T10:26+0900
ちょっと前の日記から……
Q14
この漸化式は『珠玉のプログラミング』で見た。どうして収束するのかわからなかった。
見たっていうのはコラム4の問題で。
4.6問題
5.入力xが正の整数であるとき、以下のループが終了することを示してください。
while x != 1 do if xが偶数なら x = x/2 else x = 3*x+1
これがまんま「コラッツの問題 - Wikipedia)」と呼ばれる未解決の問題だということに、今日「d.y.d.」を読んでいて気がついた。本の巻末のヒントを読み直してみたらこんなことが書いてあるし。
もし、この問題が解けたら、近くの大学の数学科に急いで行って、博士号を申請しましょう。
ひどい(笑)。わからなくて当然だ。遅刻学生が黒板の問題を宿題だと思って解いて提出したら、それは未解決問題だったとかいうのは、お話の世界なんだから。
最終更新: 2011-02-05T05:33+0900
無駄にこったねえ。一瞬 JavaScriptで書こうとしたしたせいか、lambda多用。
generators = [
lambda {
n, tn = 1, 1
lambda { n+=1; tn+=n; tn } # triangle numbers generator
}.call,
lambda {
n, pn = 1, 1
lambda { pn+=3*n+1; n+=1; pn } # pentagonal numbers generator
}.call,
lambda {
n, hn = 1, 1
lambda { hn+=4*n+1; n+=1; hn } # hexagonal numbers generator
}.call
]
numbers = [1, 1, 1] # Ti, Pj, Hk
relations = "===" # Ti?Pj, Pj?Hk, Hk?Ti
actions = lambda {
relation = lambda {|a,b|
a==b ? '=' : a>b ? '>' : '<'
}
when_Nth_is_the_smallest = lambda {|i|
lambda {
numbers[i] = generators[i].call
relations[i] = relation.call(numbers[i], numbers[(i+1)%numbers.size])
j = (i-1) % relations.size
relations[j] = relation.call(numbers[j], numbers[(j+1)%numbers.size])
print "#{numbers[i]}\r"
}
}
(0..2).map{|i| when_Nth_is_the_smallest.call(i) }
}.call
action_table = Hash.new {|h,rel|
raise "missing action for '#{rel}'"
}
[
["<<>", "<>>", "<=>", "=<>", "<>="], # when Ti is the smallest
["><<", "><>", ">=<", "><="], # when Pj is the smallest (and Ti not)
[">><", "<><", "=><"], # when Hk is the smallest (and the other not)
].each_with_index {|rels, i|
rels.each {|rel| action_table[rel] = actions[i] }
}
action_table["==="] = lambda {
puts numbers[0] # answer
actions[0].call
}
loop {
action_table[relations].call
}
相当な時間をかけて(求められていない)三番目の数字が出た。>57722156241751
六角数は三角数なので、三角数は無視できる。五角数と六角数を並べて比較していくだけ。
それがわからない。
チート。
Hn = n(2n-1) = (2n-1)(2n)/2 = m(m+1)/2 = Tm (m = 2n-1)
nは自然数だから、mは正の奇数になる。Triangle Numbersの奇数番目が Hexagonal Numbers.(逆も真) 言われたらそうかもね。それぞれの数列を眺めてたら気付くかもね。(それが無理なのはわかってる)
最終更新: 2011-02-03T09:33+0900
愚直に。
divisors = [17, 13, 11, 7, 5, 3, 2, 1]
candidates = []
div = divisors.shift
div.step(999, div){|x|
triplet = [x/100, x/10%10, x%10]
candidates.push triplet if triplet.uniq!.nil?
}
until divisors.empty?
div = divisors.shift
candidates.size.times{
candidate = candidates.shift
(0..9).each{|d|
if ! candidate.include?(d) && 0 == (100*d + 10*candidate[0] + candidate[1]) % div
candidates.push [d] + candidate
end
}
}
end
candidates.reject!{|c| c[0] == 0 }
p candidates.inject(0){|sum,c| sum + c.join("").to_i }
最初に出てきた数字を書いたら通ったけど……。pentagonal numbersの名前の由来もわからんもんね。
_5 = [1] # [P1, P2,...]
_5_index = {1=>0} # 逆引き(Pn=>n-1)辞書
loop{
i = _5.size
_5.push(_5.last + 3*i + 1)
_5_index[_5[i]] = i
print "."
(i-1).downto(0){|j|
diff = _5[i] - _5[j]
break if diff > _5[j]
k = _5_index[diff]
next unless k
diff2 = _5[j] - _5[k]
l = _5_index[diff2]
next unless l
puts
puts "D=#{_5[j]-_5[k]}"
puts "#{_5[j]-_5[k]} = P#{j+1}-P#{k+1}"
puts "#{_5[l]} = P#{l+1}"
puts "#{_5[j]+_5[k]} = P#{j+1}+P#{k+1}"
print "#{_5[i]} = P#{i+1}"
gets
}
}
最終更新: 2011-02-01T10:42+0900
sum = 1
1.upto((1001-1)/2){|d|
sum += 2 * ( (2*d+1)**2 + (2*d+1)**2-3*2*d ) # (右上の数＋右下の数)の倍で対角4数の和
}
p sum
9の5乗が6万弱なので6桁までの探索で十分。
t = [0, 1, 2**5, 3**5, 4**5, 5**5, 6**5, 7**5, 8**5, 9**5]
sum = 0
10.upto(999999){|n|
sum += n if n == [n, n/10, n/100, n/1000, n/10000, n/100000].inject(0){|a,x| a+t[x%10] }
}
p sum
キレイに書けたんではないかと。
coins = [200, 100, 50, 20, 10, 5, 2] # ,1
remainder = [200]
coins.each{|coin|
remainder.length.times{|n|
remain = remainder[n]
while coin <= remain
remain -= coin
remainder.push remain
end
}
}
p remainder.size
メモリも CPUも節約できる真にすばらしい回答はこちら >Dreamshire | Project Euler Problem 31 Solution
target = 200
coins = [1,2,5,10,20,50,100,200]
ways = [1]+[0]*target
coins.each{|coin|
coin.upto(target){|i|
ways[i] += ways[i-coin]
}
}
p ways[target]
ways[]のインデックスが残金(200-i㌺)で、値が場合の数、なのかな？
有名な問題で、SICPやら何やらに載ってるらしい。2005年以来封印してきたコンクリートマテマティクスを繙くときが来たのかもしれない。<もったいぶってないで勉強しろ
def factorial(n)
r = 1; n.downto(2){|x| r *= x }; r
end
factorials = [1]
9.times{ factorials.push( factorials.last * factorials.length) }
# 9の階乗が36万ちょっとなので 7桁までで十分
sum = 0
10.upto(9999999){|n|
x = n
m = 0
while 0 < x
m += factorials[x%10]
x /= 10
end
sum += n if n == m
}
p sum
Q9の発展。
best_p = 0
solutions_for_p = 0
3.upto(1000){|p|
solutions = 0
1.upto(p/3){|a|
aa = a*a
p_a = p-a
a.upto(p_a/2){|b|
solutions += 1 if aa + b*b == (p_a-b)*(p_a-b)
}
}
if solutions_for_p < solutions
solutions_for_p = solutions
best_p = p
end
}
p best_p
# 一桁 1-9 9個
# 二桁 10-99 90個
# 三桁 100-999 900個
answer = 1
a = [1, 10, 100, 1000, 10000, 100000, 1000000]
width, count = 1, 9
n, pos = 1, 1
loop{
count.times{
if a.first < pos + width
answer *= n.to_s[a.first-pos,1].to_i
a.shift
if a.empty?
p answer
exit
end
end
n += 1
pos += width
}
width, count = width+1, count*10
}
names = ["A","ABILITY","ABLE",...]
name_values = names.map{|name| (0...(name.length)).inject(0){|wv,i| wv + name[i] - ?A + 1 } }.sort
count = 0
n, tn = 1, 1
until name_values.empty?
name_values.shift while ! name_values.empty? and name_values.first < tn
while ! name_values.empty? and name_values.first == tn
count += 1
name_values.shift
end
n, tn = n+1, tn+n+1
end
p count
わかんね。1^1, 2^2から 250250^250250までを、250で割った余りで 250種類に分類するところまでやったけど、そこから組み合わせの数を妥当な時間で計算できる気がしない。1要素で 250の倍数になるもの、ならないもの、2要素で 250の倍数になるもの、ならないもの、……、249要素で 250の倍数になるもの、を考えていくのかと思ったけど、それらの要素が有限なために自由には組み合わせられない(不可能な組み合わせが生じる)、単純に掛け合わせて可能な場合の数を求められない、というところで行き詰まった。ならばと、Q31で参考にしたスクリプトを下敷きに 250で割った余りをインデックスに、場合の数を値にした配列を使おうかと思ったけど、残金をインデックスにした場合と違って余りは循環する、というあたりで処理が一直線に進まなくてギブアップ。
memo = [[0, 1]]*250 # [exp, mod]
memo2 = (0...250).map{|x| x**250 } # exp=250特化版
set = [0]*250
1.upto(250250).each{|i|
basemod = i%250
mod = (memo[basemod][1] * (i-memo[basemod][0] == 250 ? memo2[basemod] : basemod**(i-memo[basemod][0]))) % 250
memo[basemod] = [i, mod]
set[mod] += 1
}
p set