/ 最近 .rdf 追記 編集 設定 本棚

脳log[20110213] Q58, Q59, Q60



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ではないけど)ループを持っている。大変なはずだ。

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