[プロジェクト・オイラー]
palindromes = 回文
585 = 1001001001_2 (2進) は10進でも2進でも回文数である.
100万未満で10進でも2進でも回文数になるような数の総和を求めよ.
(注: 先頭に0を含めて回文にすることは許されない.)
3797は面白い性質を持っている. まずそれ自身が素数であり, 左から右に桁を除いたときに全て素数になっている (3797, 797, 97, 7). 同様に右から左に桁を除いたときも全て素数である (3797, 379, 37, 3).
右から切り詰めても左から切り詰めても素数になるような素数は11個しかない. 総和を求めよ.
注: 2, 3, 5, 7を切り詰め可能な素数とは考えない.
+
|
解答
|
|
|
- 考えたこと
- ある自然数Nが素数がどうか調べるときは、試し割りを√Nまでやればよいので
- 切り詰め可能素数が11個見つかるまでそれをメモ化しながらやっていった
def prime?(n, primes)
if n == 1
false
elsif primes.include?(n)
true
else
m = Math.sqrt(n).round
2.upto(m) do |step|
if step != 2 and step % 2 == 0
next
else
if n % step == 0
return false
else
next
end
end
end
true
end
end
def truncate_prime?(n, primes)
arr = n.to_s.split("")
head = arr.dup
tail = arr.dup
while not head.empty?
unless prime?(head.join.to_i, primes)
return false
end
head.pop
end
while not tail.empty?
unless prime?(tail.join.to_i, primes)
return false
end
tail.shift
end
true
end
primes = []
truncate_primes = []
number = 2
while truncate_primes.length != 11
if prime?(number, primes)
# add primes into memo
primes << number
puts " Prime found! => #{number}"
if truncate_prime?(number, primes) and number > 9
truncate_primes << number
puts "* Tr prime found! => #{number}"
end
end
number += 1
end
p truncate_primes
p truncate_primes.inject(&:+)
|
192 に 1, 2, 3 を掛けてみよう.
192 × 1 = 192
192 × 2 = 384
192 × 3 = 576
積を連結することで1から9の パンデジタル数 192384576 が得られる. 192384576 を 192 と (1,2,3) の連結積と呼ぶ.
同じようにして, 9 を 1,2,3,4,5 と掛け連結することでパンデジタル数 918273645 が得られる. これは 9 と (1,2,3,4,5) との連結積である.
整数と (1,2,...,n) (n > 1) との連結積として得られる9桁のパンデジタル数の中で最大のものはいくつか?
辺の長さが {a,b,c} と整数の3つ組である直角三角形を考え, その周囲の長さを p とする. p = 120のときには3つの解が存在する:
{20,48,52}, {24,45,51}, {30,40,50}
p ≤ 1000 のとき解の数が最大になる p はいくつか?
+
|
解答
|
|
|
- 考えたこと
- 与えられた式を変形すると
が出るので、それを満たすpを3重ループで探索した
require 'set'
# a**2+b**2=c**2
# a+b+c=p
max_ans = {:pi => 0, :ans => 0}
for pi in 1..1000
ans = Set.new
for ai in 1..pi
for bi in 1..(pi-ai)
#puts "a=#{ai},b=#{bi}"
if pi**2 == (2*pi*(ai+bi)-2*ai*bi)
# puts "p = #{pi}"
# puts "pi^2 = #{pi**2}"
# puts "==> (pi^2)/2 = #{(pi**2)/2}"
# puts "a=#{ai},b=#{bi},c=#{pi-ai-bi}"
ans << [ai,bi,pi-ai-bi].sort.join(":")
end
end
end
puts "ans = #{ans.length}"
if max_ans[:ans] < ans.length
max_ans[:pi] = pi
max_ans[:ans] = ans.length
end
end
p max_ans
|
正の整数を順に連結して得られる以下の10進の無理数を考える:
0.123456789101112131415161718192021...
小数第12位は1である.
dnで小数第n位の数を表す. d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000 を求めよ.
+
|
解答
|
|
|
d = ""
(0..10**6).to_a.each do |n|
d += n.to_s
break if d.length > 1000000
end
# d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000
puts d[0,100]
puts d[10**0].to_i
puts d[10**1].to_i
puts d[10**2].to_i
puts d[10**3].to_i
puts d[10**4].to_i
puts d[10**5].to_i
puts d[10**6].to_i
puts (0..6).to_a.map{|i| d[10**i].to_i}.inject(&:*)
|