Problem 9
https://projecteuler.net/problem=9
ピタゴラス数は一般に、
と書ける(mとnは互いに素でどちらかが偶数で、)て、直角三角形の周囲の長さはとなるので、周囲の長さ/2を2つの約数に分けて、さらにその一方を2つの約数に分ける必要があるが、mとm+nが互いに素なのを利用すると、余分な計算をしなくて済む。
function factorize_naive(n) fs = Dict() for d in Iterators.countfrom(2) if d*d > n break elseif n%d == 0 e = 1 n = div(n, d) while n%d == 0 e += 1 n = div(n, d) end fs[d] = e end end if n != 1 fs[n] = 1 end return fs end function f_div(fs1, fs2) fs3 = Dict() for fac in fs1 p = fac.first e1 = fac.second if haskey(fs2, p) e = e1 - fs2[p] if e != 0 fs3[p] = e end else fs3[p] = e1 end end return fs3 end function f_value(fs) return reduce((x, fac) -> x*fac.first^fac.second, fs, init=1) end function divisors(fs) L = length(fs) if L == 0 return [Dict()] elseif L == 1 for fac in fs p = fac.first e = fac.second divs = [Dict{Int64,Int64}()] append!(divs, [ Dict(p => e1) for e1 in 1:e ]) return divs end else mid = div(L, 2) fss1 = divisors(Dict(Iterators.take(fs, mid))) fss2 = divisors(Dict(Iterators.drop(fs, mid))) return [ merge(fs1, fs2) for (fs1, fs2) in Iterators.product(fss1, fss2) ] end end function divisors_coprime(fs) w = collect(pairs(fs)) L = length(w) if L == 0 return [1, 1] elseif L == 1 f = first(fs) x = f.first^f.second return [1, x] else v::Array{Int} = [] mid = div(L, 2) for x in divisors_coprime(Dict(w[1:mid])) for y in divisors_coprime(Dict(w[mid+1:L])) push!(v, x*y) end end return v end end function divisors3(fs) triplets::Array{Tuple{Int,Int,Int}} = [] num = f_value(fs) for fs_ in divisors(fs) num1 = f_value(fs_) if num1%2 != 0 continue end l = div(num, num1) for m in divisors_coprime(fs_) num2 = div(num1, m) n = num2 - m if 0 < n && n < m push!(triplets, (l, m, n)) end end end return triplets end function Pythagoreans(perimeter) fs = factorize_naive(div(perimeter, 2)) return [ (l*(m*m-n*n), 2*l*m*n, l*(m*m+n*n)) for (l, m, n) in divisors3(fs) ] end function e009(n) v = Pythagoreans(n) println(length(v), v) return reduce(*, v[1]) end N = parse(Int, ARGS[1]) println(e009(N))
素因数分解は、Dict(p=>e)で表している。
ここで、mergeはDict同士をmergeしている。
julia> dic1 = Dict(1=>2, 2=>3) Dict{Int64,Int64} with 2 entries: 2 => 3 1 => 2 julia> dic2 = Dict(3=>3, 4=>2) Dict{Int64,Int64} with 2 entries: 4 => 2 3 => 3 julia> merge(dic1, dic2) Dict{Int64,Int64} with 4 entries: 4 => 2 2 => 3 3 => 3 1 => 2
ここではこれがたまたまハマっているが、そんなに使わないと思われる。
Iterators.takeとIterators.dropは素因数分解を半分に使っている。それぞれ、第2引数の個数まで取る、あるいは落としている。