脳log[20110209] Q51, Q52, Q53, Q55

最終更新: 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