不思議数

 投稿者：永野護  投稿日：2012年 3月13日(火)10時37分4秒
  不思議数（ふしぎすう、英: weird number）は、自然数のうち過剰数でありながら擬似完全数でない数のことである。言い換えるとその数自身を除く約数の総和が元の数より大きくなる数で、どのように約数を（重複させずに）組み合わせてその和をとっても元の数にならないような数である。例えば70の自身を除く約数の総和は 1+2+5+7+10+14+35=74>70 であり元の数より大きくなるが、どのようにこれらの約数を組み合わせて和を計算しても70にはならないので70は不思議数である。不思議数は無数に存在し、そのうち最小のものは70である。

不思議数を70から小さい順に列記すると

70, 836, 4030, 5830, 7192, 7912, 9272, 10430, 10570, 10792, 10990, 11410, 11690, 12110, 12530, 12670, 13370, 13510, …
奇数の不思議数は発見されていないが、もし存在するなら 10＾18 より大きい数であることが知られている。以上WIKIPEDIAより。
-----------------------------------------------------------------------------------
この不思議数を10万以下で求めるにはどのようなプログラムを組めばよろしいでしょうか。
ご教授いただければ幸いです。よろしくお願いします。

 		 

Re: 不思議数

 投稿者：山中和義  投稿日：2012年 3月13日(火)17時16分32秒
  > No.1813[元記事へ]

永野護さんへのお返事です。

> 不思議数を70から小さい順に列記すると
>
> 70, 836, 4030, 5830, 7192, 7912, 9272, 10430, 10570, 10792, 10990, 11410, 11690, 12110, 12530, 12670, 13370, 13510, …

10万は、マシンパワーがかなり必要です。


!不思議数


LET t0=TIME


LET N=20000 !検索範囲 [1,N]
FOR i=0 TO N
   IF WeirdNumberQ(i)=1 THEN PRINT i;"は、不思議数です。"
NEXT i


PRINT "計算時間=";TIME-t0

END


EXTERNAL FUNCTION WeirdNumberQ(N) !不思議数かどうか確認する　1:不思議数、0:そうでない
LET WeirdNumberQ=0

IF N<0 OR N<>INT(N) THEN EXIT FUNCTION !引数を確認する
!０以上の整数なら

IF MOD(N,6)<>0 THEN !∵完全数6とその倍数は、n=n/2+n/3+n/6より、擬似完全数となる

   LET M=INT(N/2)+1 !高々
   DIM D(M)
   CALL Divisors(N,C,D) !約数を得る

   LET S=0 !その数自身を除くすべての約数の和
   FOR k=1 TO C-1
      LET S=S+D(k)
   NEXT k
   IF S>N THEN !過剰数なら
   !!!PRINT N;C !debug

      FOR L=0 TO 2^(C-1)-1 !組合せと2進法（ビットパターン）を対応させる
         LET t=L

         LET S=0 !その数自身を除くいくつかの約数の和
         LET k=C-1 !大きい約数から順に
         DO WHILE t>0
            IF MOD(t,2)=1 THEN
               LET S=S+D(k)
               IF S>N THEN EXIT DO !これ以降は可能性なし
            END IF
            LET t=INT(t/2)
            LET k=k-1
         LOOP
         IF S=N THEN EXIT FOR !一致する
      NEXT L
      IF L>2^(C-1)-1 THEN LET WeirdNumberQ=1 !すべての組合せで一致しないなら

   END IF

END IF
END FUNCTION


EXTERNAL SUB Divisors(N, C,D()) !正の約数を列挙する　※N≧1
LET C=0 !個数
IF N<1 OR N<>INT(N) THEN EXIT SUB !引数を確認する
!１以上の整数なら
LET C=1
LET D(1)=1 !１

LET i=2
DO WHILE i*i<=N !２～√Ｎ
   IF MOD(N,i)=0 THEN !割り切れるなら
      LET C=C+1
      LET D(C)=i !除数
   END IF
   LET i=i+1
LOOP

LET M=C !残りの片方を求める
IF D(C)*D(C)=N THEN LET M=M-1 !平方数の場合

FOR i=1 TO M
   LET D(C+i)=N/D(M-i+1) !商
NEXT i

LET C=C+M !個数
END SUB

 		 

不思議数

 投稿者：永野護  投稿日：2012年 3月14日(水)11時23分1秒
  山中様、お忙しい中ありがとうございました。丁寧なプログラムを作っていただきましたことに深く感謝いたします。季節の変わり目です。お体を大切になさってください。
敬具 		 

Re: 不思議数

 投稿者：山中和義  投稿日：2012年 3月16日(金)19時26分46秒
  > No.1814[元記事へ]

10万個の数値の配列は確保可能なので、篩い法で求めてみました。
原始擬似完全数の倍数で篩います。かなり速く処理できます。


!不思議数 - 自然数のうち過剰数でありながら擬似完全数でない数
!擬似完全数 - 自然数のうち自身を除くいくつかの約数の和が元の数に等しい数
!原始擬似完全数 - 擬似完全数の内、その約数に他の擬似完全数を含まない数

!参考サイト　http://oeis.org/A006036　Primitive pseudoperfect numbers


LET t0=TIME


LET N=100000 !1～Nの範囲


!Step.1　不足数、完全数、過剰数に分ける。

DIM F(N) !篩い

FOR k=1 TO N !自明な約数は1
   LET F(k)=1
NEXT k
FOR t=2 TO N !約数（2以上）の候補
   FOR k=t TO N STEP t !倍数に対して
      LET F(k)=F(k)+t !約数の和
   NEXT k
NEXT t
!!!MAT PRINT F; !debug


!Step.2　過剰数が候補である。

FOR J=1 TO N
   IF F(J)>2*J THEN !未確認の過剰数（元の数自身を除く約数の和が元の数より大きい）なら

      DIM D(500)
      CALL Divisors(J,C,D) !約数を得る

      !!LET S=0 !その数自身を除くすべての約数の和
      !!FOR k=1 TO C-1
      !!   LET S=S+D(k)
      !!NEXT k
      LET S=F(J)-J !その数自身を除くすべての約数の和


      LET V=S-J !過剰な値

      FOR i=2 TO C-1 !約数でこれ以下のものを選んで組み合わせる
         IF D(i)>V THEN EXIT FOR
      NEXT i
      !!!PRINT N; V; i-1; C !debug

      FOR L=0 TO 2^(i-1)-1 !組合せと2進法（ビットパターン）を対応させる
         LET t=L

         LET S=0 !その数自身を除くいくつかの約数の和
         LET k=i-1 !大きい約数から順に
         DO WHILE t>0
            IF MOD(t,2)=1 THEN
               LET S=S+D(k)
               IF S>V THEN EXIT DO !これ以降は可能性なし
            END IF
            LET t=INT(t/2)
            LET k=k-1
         LOOP
         IF S=V THEN EXIT FOR !一致する
      NEXT L
      IF L>2^(i-1)-1 THEN !すべての組合せで一致しないなら
         PRINT J;"は、不思議数です。"

      ELSE
         PRINT J;"は、原始擬似完全数です。"

         FOR k=2*J TO N STEP J !その倍数は、擬似完全数となる
            LET F(k)=-ABS(F(k)) !「確認済み」とする
         NEXT k

      END IF


   ELSEIF F(J)=2*J THEN !完全数（元の数自身を除く約数の和が元の数と等しい）なら
      PRINT J;"は、完全数です。"

      FOR k=2*J TO N STEP J !その倍数は、擬似完全数となる
         LET F(k)=-ABS(F(k)) !「確認済み」とする
      NEXT k


   END IF
NEXT J


PRINT "計算時間=";TIME-t0

END


EXTERNAL SUB Divisors(N, C,D()) !正の約数を列挙する　※N≧1
LET C=0 !個数
IF N<1 OR N<>INT(N) THEN EXIT SUB !引数を確認する
!１以上の整数なら
LET C=1
LET D(1)=1 !１

LET i=2
DO WHILE i*i<=N !２～√Ｎ
   IF MOD(N,i)=0 THEN !割り切れるなら
      LET C=C+1
      LET D(C)=i !除数
   END IF
   LET i=i+1
LOOP

LET M=C !残りの片方を求める
IF D(C)*D(C)=N THEN LET M=M-1 !平方数の場合

FOR i=1 TO M
   LET D(C+i)=N/D(M-i+1) !商
NEXT i

LET C=C+M !個数
END SUB

 		 

不思議数

 投稿者：永野護  投稿日：2012年 3月17日(土)13時31分44秒
  山中様のたびたびの回答に感謝します。ＥＸＣＥＬのソルバー機能を使うことも
考えたのですが。私がぜひ欲しかったのは部分和をどのように計算するかということでした。貴重なアドバイスありがとうございました。
敬具 		 

戻る