CodeIQ：素因数分解で和が同じ

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「素因数分解で和が同じ」（CodeIQ）を参照してください。

問題の概要

問題を引用します。

整数を素因数分解し、分解した素数の和を求めることを考えます。
例えば、36を素因数分解すると2×2×3×3となり、分解した素数の和は 2+2+3+3=10 となります。
また、32を素因数分解すると2×2×2×2×2となり、分解した素数の和は 2+2+2+2+2=10 となります。

このように、分解した素数の和が同じになることがあります。
そこで、分解した素数の和 n が与えられたとき、元の整数がいくつあるかを求めます。
例えば、n = 10 のとき、上記の32, 36以外に21, 25, 30がありますので、全部で5つあります。

標準入力から n が与えられたとき、元の整数がいくつあるかを求め、標準出力に出力してください。
ただし、2≦n≦250とします。

【入出力サンプル】
標準入力

10

標準出力

5

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby
require 'prime'

$Memo = {}

def a008472(n)
	arr = Prime.prime_division(n)

	ret = 0
	for a in arr
		ret += a[0]
	end

	return ret
end

def a000607(n)
	return 1 if n==0
	return $Memo[n] if $Memo[n] != nil

	ret = 0
	for k in 1..n
		ret += a008472(k)*a000607(n-k)
	end

	$Memo[n] = ret/n
	return ret/n
end

# main
while line = gets
	line.strip!
	next if line.empty?

	p a000607(line.to_i)
end

解説

最初、メモ化再帰あたりで簡単にできそうと思いましたができず、OEIS頼りになりました。

考え方

冒頭に書いた通り、自力で解いたわけではないのでなぜこれでできるのかは説明できません。

とりあえず、時間切れになりますが再帰で答えを求めるのは簡単です。

#!/usr/bin/ruby
require 'prime'

def count(primes, n, st)
	return 0 if st >= primes.size
	return 1 if n == 0
	return 0 if n < primes[st]

	ret = 0
	for i in st...primes.size
		ret += count(primes, n-primes[i] , i)
	end

	return ret
end

def solve(n)
	primes = Prime.each(n).to_a
	ret = count(primes, n, 0)
	return ret
end

# main
while line = gets
	line.strip!
	next if line.empty?

	p solve(line.to_i)
end

このコードは総当たりで答えを求めます。
素因数分解してその素数の和がnになるので、素数はn以下のものしかありません。
なので、n以下の素数をnから引いてみて結果的に0になるパターンを探せば良いわけです。
で、これをメモ化すれば完了と思ったのですがうまくメモ化できませんでした。
再帰呼び出しごとにnをキーとしてメモを作った場合、重複してしまう場合があってうまく行かないのです。
結局、これを解決できずOEIS行きになりました。

いかにもOEISにありそうな数列だったのでやはり存在し、それがA000607の数列です。

main

入力値を数値にしてsolve()に渡し、結果を印字します。

a000607(n)

答えはk=1..nでA008472(k)*A000607(n-k)を足し合わせたものということです。
再帰呼び出しになっていて何回も同じnについて計算するのでメモ化しています。

a008472(n)

OEISを見ればそれまでですが、nを素因数分解した時に現れる素数について重複をのぞいて足し合わせた値を求めます。
例えば、
n=2 => [2] => 2
n=4 => [2²] => 2
n=6 => [2,3] => 2+3=5
n=8 => [2³] => 2
n=9 => [3²] => 3
n=12 => [2²,3] => 2+3=5
という感じです。

雑感

最初に考えた単純な再帰の方法を拡張してうまくメモ化する方法はあるのでしょうか。
時々OEIS頼りで問題を解いていますが、私には数学が足りないのでOEISに書いてあることがわからない部分もかなりあります。また、サンプルコードも提示されているのですがMathematicaだったりMapleだったりが大半でこれも読めないのでOEISで見つけたら即回答できるというわけにも行きません。