グッドスタインの定理の検証

 投稿者：GAI  投稿日：2009年10月31日(土)20時10分12秒
  覆面算はすぐに見破られてしまいました。
そこで、次の定理がどこまで計算機で確認可能かお願いします。

任意の自然数を一つ選ぶ（例：１０７７）
これを２進数で表す。（1077=2^10+2^5+2^4+2^2+1)
さらに指数も２進表示する。(=2^(2^3+2)+2(2^2+1)+2^(2^2)+2^2+1)
指数部分に残る３もさらに２の累乗形で表す。(=2^(2^(2+1)+2)+2(2^2+1)+2^(2^2)+2^2+1)・・①

こうして書き換えた形①に対して、次の規則を交互に繰り返す。
(A)　基底を１大きくする。
(B)　(A)で出来た数から１を引く。

例を用いると
(A)：3^(3^(3+1)+3)+3^(3^3+1)+3^(3^3)+3^3+1
(B): 3^(3^(3+1)+3)+3^(3^3+1)+3^(3^3)+3^3
(A): 4^(4^(4+1)+4)+4^(4^4+1)+4^(4^4)+4^4
(B): 4^(4^(4+1)+4)+4^(4^4+1)+4^(4^4)+3*4^3+3*4^2+3*4+3
(A): 5^(5^(5+1)+5)+5^(5^5+1)+5^(5^5)+3*5^3+3*5^2+3*5+3
(B): 5^(5^(5+1)+5)+5^(5^5+1)+5^(5^5)+3*5^3+3*5^2+3*5+2
・・・・・・・・・・・
・・・・・・・・・・・
・・・・・・・・・・・
と繰り返していくと数は無限に大きくなる印象をあたえるが、いつかは最大値に達し、その後はどんどん小さくなっていき最後はゼロになるらしい。
（グッドスタインの定理）
これを確かめてもらいたい。 		 

Re: グッドスタインの定理の検証

 投稿者：山中和義  投稿日：2009年11月 1日(日)10時10分0秒
  > No.699[元記事へ]

GAIさんへのお返事です。
!グッドスタインの定理（R.L.Goodstein）

!ウィキペディアより
!http://www.cwi.nl/~tromp/pearls.html#goodstein のRuby版を移植

FUNCTION s(b,e,n)
   IF n=0 THEN LET s=0 ELSE LET s=MOD(n,b)*(b+1)^s(b,0,e)+s(b,e+1,INT(n/b))
END FUNCTION
FUNCTION g(b,n)
   IF n=0 THEN LET g=b ELSE LET g=g(b+1,s(b,0,n)-1)
END FUNCTION
DEF f(n)=g(2,n) !自然数ｎに対する０になるときの底を返す

PRINT f(0) !f(0)=2,f(1)=3,f(2)=5,f(3)=7
PRINT f(1)
PRINT f(2)
PRINT f(3)

PRINT f(4) !f(4)=3*2^402653211-1　※スタック・オーバーフロー

END

スタック・オーバーフローが回避できればいいのですが、、、（再帰処理を繰り返し処理に置き換える）

また、数値計算だと巨大な数を扱うことになるので、数式計算（代数計算）を行えば可能かと思います。 		 
 

戻る