/ 最近 .rdf 追記 設定 本棚

脳log[2011-02-20~]



2011年02月20日 (日) tDiaryの recent_listが特定の条件で動かない話>「[tDiary-devel] SAFE=1 で recent_list が動かない」 そういえば昔、recent_list.rbを書き直したことがあった。>20090114p01 多分に実験的な方法でだけど。……。自分で書いたものながら、いま読むと「h.fetch(k){loaded_months[k]}」の行の意図が不可解だった。よく読むとこれは diariesに新しいアクセサを追加している。わかりやすく書き直すとこういうこと>「h.fetch("yyyymmdd"){loaded_months["yyyymm"]}」 うまくないなあ。


2011年02月17日 (木) 「ロジクール ワイヤレスマウス M515」を発売」< ポイントは「M515の底面にあるトラッキングセンサー部分は…(中略)…マウスの動作不良の原因になりがちな、繊維やホコリ、ペットの毛などがセンサー部分に入り込むのを防ぎます」「マウスを握る手を検知した時にだけ駆動させる省エネセンサーが内蔵されており、ソファの上などで起こりうる意図しないマウスの動きを防ぐとともに…(後略)」どちらも MX610に対して持っていた不満点だ。良い。


2011年02月13日 (日) 「青空が降る少年」が「恋しさと せつなさと 心強さと」と同じくらい好きだ。

最終更新: 2011-02-20T21:45+0900

[ProjectEuler] Q58, Q59, Q60

 Q58

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
}

 Q59

  1. 暗号化キーの長さが 3文字なのがわかってるので、数列を 3列に並べて各列を眺める。
  2. 英単語には eが一番使われるとか、単語では theが再頻出だとかの統計データがあるらしい。(と書いてあるのを何度も目にしたが実際のデータは見たことがない)
  3. 文章なら文字としてはスペースが一番多いはずだ。
  4. 単語で theが一番多いなら、theの前後の空白は右下に向いて、(1行1列目)↘(2行2列目), (1行2列目)↘(2行3列目), (1行3列目)↘(2行1列目) の並びで現れるはずだ。
  5. というかんじでマジックナンバーが出てきた。
  6. あ、問題文のサマリに「Using a brute force attack, can you ...」って書いてある。しまった。
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(:+)}"

 Q60

  1. 素数二つ(A,B)に分割できてローテートしても素数な素数(AB,BA)。⇒ a set of 2 primes (A,B)
  2. (AX,XA),(BX,XB)が 1の条件を満たす 2 sets of 2 primes が見つかる。⇒ a set of 3 primes (A,B,X)
  3. (AY,YA),(BY,YB),(XY,YX)が 1の条件を満たす 3 sets of 2 primesが見つかる。⇒ a set of 4 primes (A,B,X,Y)
  4. (AZ,ZA),(BZ,ZB),(XZ,ZX),(YZ,ZY)が 1の条件を満たす 4 sets of 2 primesが見つかる。⇒ a set of 5 primes (A,B,X,Y,Z)

1を満たす素数を発見しながらそれを使って、1の集合から2へ、2の集合から3へ、3の集合から4へ、要素をプロモートしていけばよさそう。

# 寝る前にやる。

寝てしまった。答えが出ない。素数を分割するんでなく、素数のペアを組み合わせて素数かどうか判定した方がいいかもしれない。そろそろ身にしみて理解してきたけど、素数って印象よりありふれ過ぎてる。


 @2011-02-17

ちょっとくらい時間がかかってもいーやって考えてたけど、何日もかけても四つ組みが 7つと、五つ組が 0個しか見つからないことがわかったので、1分以内に答えを出すべくもうちょっと考える。

  1. 小中学生の頃に読んだ数字遊びの本から得た知識によれば、10進表記の各桁の和が 3の倍数の数はそれ自体も 3の倍数だという。だというwww
  2. 各桁の和を 3で割った余りが 0の素数は 3だけ。
  3. 各桁の和を 3で割った余りが 1の素数と 2の素数を組にすると、それをつなげた数は 3の倍数になってしまい素数ではなくなるので組にできない。
  4. 各桁の和を 3で割った余りで素数を分類すると 5つ組みとして考えられるのは (0,1,1,1,1), (0,2,2,2,2), (1,1,1,1,1), (2,2,2,2,2)の 4パターンだけ。
  5. 3桁までの素数で総当たりしてみよう。
  6. 見つからなかったので 4桁までで総当たり。
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の倍数についてもどこかの桁を見るだけで(略


 @2011-02-19

4は 100を作るから下2桁だけ。5は 10を作るから下1桁だけを見ればいい。

 「計算量の増大の仕方がひどくて」

一番時間を食ってるのは make_group_of_two. 異なる二要素の組み合わせということで n^2-n 回の素数判定を行ってる。素数判定自体も nの大きさに比例する(※1:1ではないけど)ループを持っている。大変なはずだ。

とりあえず、今の素数判定より賢い素数判定があるのはわかってるけどわからないので使ってない。(注:わかる => 知ってる, 理解できる) 丁寧にコードを読んだらわかるかもだけどそれはチートっぽい。大学入試の数論関係の問題だって、解答をチラ見したら誰だって理解できんだよ。


2011年02月12日 (土) テイラー展開とかマクローリン展開。言葉は出てこなかったけど積分の演習問題として高校で出てきてた(ことを後に知った)。コンピュータ向けの計算だよね。展開して多くの項を計算すればするだけ精度のいいπが求まるとか。昨日の Q57から連想したんだけど、平方根の計算はまた別っぽい。手計算で平方根を求める方法は俺の時代の教科書からは消えてたよ。消えてたといえば行列を使った回転も消えてたよ。高校数学は新しく習う概念がバラバラのままなんだよ。統合してよ。///「冪剰余 - Wikipedia」っていう言葉があるのね。(ギブアップした Q250関連) 「剰余」から「n-進展開 (Wikipedia(ja):剰余)」→「p進数 - Wikipedia」とんでもないところに飛んでしまった。

最終更新: 2011-02-13T04:35+0900

やばかった。

7500の正の約数は何個あるか。

素因数の数を数えてしまってた。その間違いに気づいたら今度は、1って約数に数えるの?その数自身も約数のうち?なんて、約数の定義が消えかかってる。(補足。素数の定義を思い出せば疑問は解ける)

復習~。

  1. 7500 = 5×5×5×5×3×2×2
  2. 約数は 5^i × 3^j × 2^k (i=0,1,2,3,4, j=0,1, k=0,1,2) で表される。(0乗が 1とか、0の階乗が 1とか、何気に落とし穴)
  3. 組み合わせは 5×2×3 = 30通り
  4. 重複はないので約数の数も 30個。
  5. たぶん。

コメントに↑そのまんま書いてあった(変数名まで一緒)。無駄なエントリになってしまった。

最終更新: 2012-12-12T02:17+0900

[tDiary] MathMLが使いたかったので。>「ひらくの工房 - tDiary XHTML化キット

  • HTMLモードなんていらないから拡張子は xhtmlでなく htmlで、とか
  • \times より × って書きたい、とか
  • <option selected="selected"> <input checked="checked"> みたいに属性名を省略してない HTMLもあるのよ、置換しすぎないで、とか

適当にカスタマイズして設置した。

XHTML化キットの存在は投稿されたアナウンスを読んで知ってたんだけど、XHTML好きにもかかわらず今まで導入してなかったのは、日記に数式を書く機会がなかったのと、出力段階での文字列置換による XHTML化が乱暴に思えたから。結局、他に方法がないので目をつぶったが。

閲覧不可能になった日記がないか月別表示で全日記を表示してみたら 10か所くらい見つかった。パターンは以下の通り。

  • プラグインが埋め込む JavaScriptに含まれる & 記号
  • etDiaryスタイルがエスケープしてくれなかった本文中の & 記号
  • プラグイン記法( {{~}} )で直接埋め込んだ HTML片に含まれる & 記号

 JavaScriptの &

<script>タグの中であっても & は &amp; と書かなければいけない。不等号も。でも if(a &amp;&amp; b) {} とか置換してしまったらアホだ。CDATAセクションを使う。

scriptタグが解釈できないブラウザなんて PCを手に入れた当時から持ってなかったので

<script><!--
--></script>

なんて最初から書かなかったし、XHTMLを知ってからは下のように書くことにしてる。

<script>/*<![CDATA[*/
/*]]>*/</script>

コメントで囲うのは JavaScriptとして正しくあるため。より字数の少ない行コメントにしないのは、なにかでエラーになったから。MSがリリースしてた JavaScriptを暗号化(難読化)するツールに <script>タグを含んだ HTMLファイルを通したときだったか……。

 etDiaryの &

但し書きを付けても無駄。HTMLと日本語は混ぜるな危険。中途半端な HTMLの隠蔽は悪。tDiaryスタイルと etDiaryスタイルより Wikiスタイル。

 手書き HTMLの &

自業自得。さすがに、タグに挟まれた部分に & や <, > を放置してたわけではない。

<a href="ttp://hoge/script.cgi?a=b&c=d">
<img src="ttp://hoge/script.cgi?a=b&c=d">

すべてこの形の & がエラーになっていた。HTMLを出力するスクリプトでは、属性値は機械的に必ず HTMLエスケープするようにしてるんだけど、手書きだと上のような (X)HTMLは正しく見えてしまうのか、忘れられてた。こんなことがあるとやっぱりセミコロンで区切りたいねえ。

それにしても、ちらちら目に入る古い日記が恥ずかしくて死ねる。読む人間も、そもそも読める内容もないのであえて気づかぬふりで放置するけども。


2011年02月11日 (金)

最終更新: 2011-02-12T22:42+0900

[ProjectEuler] Q56, Q57

 Q56

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

 Q57

とかいいながら 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月10日 (木) 「それは仕様です」ってそんなに嫌いではない。発言者にその宣言を遵守する意志があるのなら。言われた方はその宣言を以て、即座にその仕様(と手元の実装)に依存できる。言った方は修正の手間がないし、挙動を変えて周囲(期待と実際の違いに気付いていなかった方の集団)を騒がせるおそれもない。とはいえ一般には「仕様のわけねーだろ。バグだよ、バグ」って言いたくなるようなものに対して「これは仕様でしょうか?」ってのも嫌みったらしく聞こえそうなので控えたい。何回かやってるけど。

最終更新: 2011-02-10T23:58+0900

それは無理でしょ。>クロネコヤマト(金沢物流システム支店)

経過荷物受付02/1012:36金沢物流システム支店
経過発送02/1012:36金沢物流システム支店
最新配達完了02/1012:06○○センター

受付は昨日のはずだ。このせいで一切のトラッキングができなくて、今日着くのか明日着くのかがわからなかった。時間帯指定で不在はくらいたくないでしょうに。

最終更新: 2011-02-11T00:59+0900

[SakuraEditor] SourceForge.net Repository - [sakura-editor] Revision 1887

Fix: 検索(ツールバー)を使うとプラグインコマンドが実行される(2)

検索ボックスのコードをほとんどコピーした自作ツールバーボタンもやばい気がするものの、CBN_SELCHANGEはツールバーボタンで処理してるんだよね。処理しなかったメッセージが誤った取り扱いを受ける、ということなんだろうか。わからないよん。

>>脳log[2008-06-04-p01] 現在適用されているファイルタイプを表示/変更するツールバーボタン


2011年02月09日 (水) カレーライスのライスは右か左か。答えはでてるんだろうか。右利きだから左にご飯があると、1.スプーンをご飯に突き立てる。2.右側からカレーを巻き込みながらご飯のブロックをすくい上げる。という動作がスムーズに行えるな、なんて事を考えるんだけど、ぶっちゃけどっち向きでも食べられるし、量が減ってくるとお皿に熱を奪われたくなくて、縦向きに持って手前に寄せて食べてる。

最終更新: 2011-02-10T04:56+0900

[ProjectEuler] Q51, Q52, Q53, Q55

 Q51

ただただ、手と 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
}

 Q52

桁数ごとに探索範囲を決めて、総当たり。

問題が 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
	}
}

 Q53

浮動小数点数なんてファジーなものを使っちゃったよ。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

 Q55

問題文が難しかった。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月08日 (火)

最終更新: 2011-02-09T20:16+0900

[ProjectEuler] Q50

 Q50

  1. 100万未満の素数リストを作成。
  2. リストをコピーして作業領域とする。
  3. コピーしたリストの要素に、一つ右の位置の素数、二つ右の位置の素数、以下略を加えていき、都度、和が素数かどうか確かめる。

時間がかかるので逐一進捗を表示してる。この問題に魔法の一手なんてあるのかね。

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

魔法の一手はなくても……

  • 素数列の作成と和の評価を同時進行にできるかも。
  • 作業領域の範囲の狭め方が下手。
  • 奇数ステップ(偶数個の素数の和)は不要。
  • 100万に近い素数は不要。(それを一つ加えただけで 100万を超えるんでは項数を稼げない)
  • 項数の上限は求められる。

答えを出した後でググるのが楽しい。フォーラムは読んでないけど、多分これ以上ないっていうような答えが書いてありそうで、面白くなさそうな気がしてる。(理解できない数学的知識が使われてたら、print XXXXXXX(answer); って書かれてるのと変わらないから)


2011年02月07日 (月) 間違いさがし。『コールド メディシン A錠』の背表紙に「COLD MEDICINE CAPUSULE A」って書いてある。

最終更新: 2011-02-09T01:05+0900

[ProjectEuler] Q47, Q48, Q49

 Q47

昨日よりちょっとはマシになったかと。アホすぎた素数判定を、素因数の数を数える処理と一体化した。でも 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
}

 Q48

恥ずかしいほどまっすぐで乱暴なスクリプトだけど、コンソールの表示も待てないくらいノーウェイトで答えが出るんだから仕方がない。

p (1..1000).inject(0){|sum,x| sum + x**x }

 Q49

  1. 4桁の素数リストを作る
  2. リストから条件を満たす二つの素数を選ぶ
  3. 計算で求めた三番目の数(三つのうち一番大きい)が条件を満たすか調べる。

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月06日 (日)

最終更新: 2011-02-07T05:28+0900

[ProjectEuler] Q46, Q47

 Q46

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
}

 Q47

何の工夫もないのですんごく時間がかかる。

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月05日 (土)

最終更新: 2011-02-05T10:26+0900

[ProjectEuler] Q14, 『珠玉のプログラミング』, Collatz予想

ちょっと前の日記から……

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月03日 (木)

最終更新: 2011-02-05T05:33+0900

[ProjectEuler] Q45

 Q45

無駄にこったねえ。一瞬 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月02日 (水)

最終更新: 2011-02-03T09:33+0900

[ProjectEuler] Q43, Q44

 Q43

愚直に。

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 }

 Q44

最初に出てきた数字を書いたら通ったけど……。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
	}
}