最終更新: 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-04T22:27+0900
認証結果(GET/POSTデータ)の再利用によるなりすましを防ぐために nonceを使うのが一般的。でもそうするとコメントのプレビュー時にはまだ認証ができないことになる。事前に認証してしまったら自分自身がその結果を再利用するかたちになるから。tDiaryはアカウントやログインって概念を管理してないから OpenIDによる認証結果をそれらと結びつけて持続させることができない。認証とコメントの投稿が同時のぶっつけ本番。書き込み前にどういう表示になるのかはやっぱり知りたいよ。
Bloggerの解。
表示名には、OpenID プロバイダから Google に送信されたあなたの名前が使用されます。表示名がない場合は、OpenID の URL から表示名の取得を試みます。
こういう割り切りが必要なのかな。でも Yahoo!!!なんかは味気ない URLしか返してこないよね(※1)。mixiしか聞かない、表示名が取得できたってのは。もちろん、myOpenIDもユーザーフレンドリーな名前を返す。ペルソナをかぶることすらできるから選んだ。OpenID Providerとしての Googleはひと味違って claimed_idが realmごとに固有のものに変化するらしい(※2)。Webサービスからすると、ユーザーをリダイレクトしたときと返ってきたときの claimed_idが変わったように見える。OpenIDをいろんなサービスへのログイン手段としてだけみるなら、余分な情報を渡さないのはメリット。自己紹介として URLを提示したときにはそれと違うものが claimed_idとして Webアプリに渡るのはデメリット。さて、独自ドメインの URLを提示しておいて、そのドメインから Googleへ認証を delegateした場合の claimed_idはどうなる？
※1 知らぬ間に AX(Attribute Exchange)に対応してた。「Yahoo! JAPAN、OpenIDでプロフィール情報を提供 拡張仕様「AX」「UI」に対応：CodeZine」でも、SREGには対応しないってどういうこと？ AXの汎用性は却って対応が面倒なんだけど。「Attribute Exchange のメモ - Yet Another Hackadelic」定義済みのシェーマがあるらしいが、すでに二つもある。
※2 もっとも、そのことを知ったのはこういうタイトルの記事。「OpenIDでGoogleからグローバルユニークなユーザー識別子を取得できるかもしれない方法 - r-weblife」realm(Webサービスのドメイン)固有の claimed_id ↔ 「グローバルユニークなユーザー識別子」
閑話休題。nonceをワンタイムでなく時限式にするしかないのだろうか。タイムアウトって嫌いなんだけど。
OpenID Providerへコメントの全文ごとユーザーをリダイレクトするのはまずいかなと思って、通常通りコメントを保存した後でリダイレクトし、正しく認証されて返ってきたときに、その印としてコメントに OP名を付与することを考えた。問題はその認証がどのコメントに対するものなのかだ。ユーザーを送り出すときに「このパラメータと一緒に返ってきてね」ということはできるが……。コメントを他者が推測できない UUIDみたいなものとともに保存しておいてユーザーにそれを運んでもらおうか。(もちろんどの日の日記に対するコメントなのかを表すパラメータもユーザーに運んでもらう)
最終更新: 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-08-08T21:28+0900
目当てはペルソナ機能。OpenIDは自分が何者かを名乗るためのもので、また他人に自分の名を騙らせないためのものだと思っている。だもんで、IDとなる URLとは別に表示名として、どう名乗るのかを対象 Webアプリごとに選べるペルソナ機能は魅力。
OpenIDについて認証結果(Webアプリに対する GET/POSTリクエスト)の改ざんを防ぐ仕組みと再利用を防ぐ仕組みを勉強した。再利用が悪なのかはわからないけど。
日記データとしては openid.claimed_idと openid.sreg.email, openid.sreg.nicknameを保存するとする。email, nicknameは従来の自由入力欄と同じ扱い。オプションだし自由に書き換えられる。認証と同時に取得できたらそれをデフォルト値にするってだけ。URLの形をした openid.claimed_idはこれまでなかったもので、ユーザーの識別情報として使いなりすましを排除する。と同時にユーザーのホームページであることが期待される。Facebookやはてなダイアリーなど、人となりがわかる主たる活動場の URL。俺だったら「http://vvvvvv.sakura.ne.jp/ds14050/ (identified by www.myopenid.com)」となる。本当はアイコンも取得してそのリンク先を claimed_idとしたい。URLは表示するには長すぎる。
Cookieには openid.claimed_idを保存しておいて、ダメ元で JavaScriptに immediateモードで認証を行わせると二回目から便利かも。どういうフローだと迷わず最小の手間でコメントを投稿できるだろう。Webサービスを利用した経験が皆無で模範が思い浮かばない。