Perfect Numberを再帰で求めたい

Question

再帰法を使ってPerfect Numberを出力するプログラムを考えていますが、n>=5000でスタックオーバーフローになってしまいます。

新たなメソッドやクラス、ループ、メルセンヌ数などを使用せず、また下記の平易な再帰的アルゴリズムを維持したまま最低4つまで出力したいです。

m%2==0を用い計算回数を減らすための除法を導入するなど、試行錯誤しましたがなかなか上手くいきません。(やり方が悪かったのかもしれません...)

条件が多く恐縮ですが、知恵をお貸しください。

def perfect_numbers(n)
	perfect_numbers_r(n, 1, Array.new(0), 0)
end

def perfect_numbers_r(n, m, perfect_numbers, count)
	if m > n
		perfect_numbers
	elsif sod(m,m/2) == m
		perfect_numbers[count] = m
		perfect_numbers_r(n, m+1, perfect_numbers, count+1)
	else
		perfect_numbers_r(n, m+1, perfect_numbers, count)
	end
end

def sod(t, k)
	if k == 0
		0
	else
		if t % k == 0
			t + sod(t, k-1)
		else
			sod(t, k-1)
		end
	end
end

Comments

[KSwordOfHaste]

システムのコールスタック領域を拡大したり末尾再帰をしてくれる別のシステムを利用するといった方法ではなく、アルゴリズムを工夫することで「再帰呼び出しの深さを軽減する改善方法はあるか？」を考えておられるのですよね？そうなのであればその旨を明確に表明したほうがよいと思います。

[KSwordOfHaste]

titorさんの回答拝見しましたが上のコメントは蛇足でした。無視してくださいませ。

[akasatana]

ご質問ありがとうございます。おっしゃる通り、アルゴリズムを工夫することで、再帰呼び出しの深さを軽減する改善方法を探索しています。もし良い案がございましたらご教示下さいませ。

[raccy]

そもそも、今のコードですと素数の配列が返ってくるようなのですが、少ない数での動作はあっているんですか？

Answer 1

何をしたいのかよくわからないのですが、条件に一致するならこうでしょうか。(countは意味が無いので使ってません)

# frozen_string_literal: true
def perfect_numbers(n)
  perfect_numbers_r(n, 1, [])
end

def perfect_numbers_r(n, m, nums)
  pn = m.upto(n).detect { |x| sod(x, x / 2) == x }
  return nums if pn.nil?
  perfect_numbers_r(n, pn + 1, nums + [pn])
end

def sod(t, k)
  return 0 if k <= 0
  d = k.downto(1).detect { |x| (t % x).zero? }
  d + sod(t, d - 1)
end

p perfect_numbers(10000)

• メソッド … 増やしてない
• クラス … 使ってない
• ループ … 使ってない
• メルセンヌ数 … 使ってない

どのようなアルゴリズムにしろ、m + 1の部分とk - 1の部分を変えない限り、n回再帰、n/2回再帰が発生します。この部分のアルゴリズムを変更しない限り再帰回数を減らすのは無理です。なお、速度は全く考慮していませんので、あしからず。

Answer 2

n=10000
def perfect_number m
  if m==1
    []
  else
    if sod(m,(Math.sqrt(m)).to_i)==m*2
      perfect_number(m-1)+[m]
    else
      perfect_number(m-1)
    end
  end
end
def sod t,k
    if k <= 0
        0
    else
        if t % k == 0
            k + t/k +sod(t, k-1)-(k**2==t ? k:0)
        else
            sod(t,k-1)
        end
    end
end
p perfect_number n

sodへ渡す第二引数をsqrt(m)・・sqrt(4)=2,sqrt(16)=4 とすればいいと思います。
12{
(1 2 3)
(12 6 4)
}
と２分割したときに上の範囲だけ再帰で追う形です。
m**2の判定がコーナーケースです。

Answer 3

如何に完全数を求めるかが趣旨ではなく、完全数を例にとりf(n)とf(n+1)の間になんらかの関係があるようなf(n)とは何かを考えるのが趣旨なのですね。それが練習問題なのであればそれを考えさせるのが目的なのだから質問するのではなく頑張って自分でf(n)を見つけないと練習にならないと思います...

ところで某大学の演習問題に同じようなものを見つけました。
Ruby の基礎: 再帰プログラム演習
この問題では完全数を再帰を使って求めよとあります。また「[ヒント] 関数 sod_r(n,m) を利用しなさい．」とあります。sod_rが何を求める関数のことを言っているのか調べればそれがヒントになるような気もします。

Answer 4

完全数を求めるのに再帰を使うのはtitorさんのおっしゃる通りで不合理ですが、Rubyの演習だと思ってやる分には
工夫の余地が多少あって面白いですね。
同じようなことをなさっている方を見つけました。
rubyで再帰で完全数を求めた。4つぐらいまでは行ける。perfect_number(m)
Rubyの再帰の上限について調べた方もいました。
Rubyの再帰の限界を調べてみる

再帰を使う使わないに関わらず、お気軽に計算できる範囲では奇数の完全数は見つかっていないので、対象を偶数だけにするとか、対象を偶数に限定するなら1と2で割り切れるのは自明だから計算を省略するとかいうセコい作戦も意外と効果があるかもしれませんね。

Answer 5

根本的な質問ですが、なぜ再帰を使わなければならない、そして「新たなメソッドやクラス、ループ、メルセンヌ数などを使用せず」でなければならないのでしょうか。

外的要因でかかった制約条件であれば、「制約条件を外すことができる」場合もありますので、そちらにかかったほうが適切ではないかと思います。

もしこれらの制約条件が「個人の好みで設定したもの」であれば、はっきり言って「なくしたほうがずっとかんたん」です。

Answer 6

約数の総和は12=22+31のとき
(1+2+4)*(1+3)=28 で表せます。
5が完全数でないことと、6が完全数であることに相関がないので再帰する意味がないです。
事前におおよその目処をつけた値を再帰に渡さない限り8128を見つけることは不可能だと思います。

Comments

[akasatana]

回答ありがとうございます！私も他の方法でしたら(forを使うなど)簡単なのに、と思うところはございますが、とある練習問題において、「再帰で」との指定があったため、このような質問をさせていただいております。