持続係数(耐久数)

 投稿者:山中和義  投稿日:2011年 6月23日(木)10時30分3秒
  >「各桁の数の積」による持続係数(multiplicative persistence)
> 与えられた整数のすべての桁の数を掛けて第2の数を作り、
> その数の各桁の数を掛けて第3の数を作り、この操作を反復して、
> 最後に1桁の数を得るまでの反復回数である。
> たとえば、89は89→72→14→4と3回で1桁の数になるから、89の持続係数は3である。

0からnまでコツコツと順に計算していく過程で、効率よく求める方法はないか検討する。

nの持続係数をP(n)とする。
正整数nの各桁の数字をかけて得られる値をmとすると、n>mとなり、P(n)=P(m)+1となる。


★ケース1 組合せより「場合の数」を減らす
2桁の場合、たとえばn=36とn=63はm=18で同じ値になる。
また、桁に0を含むものも除けば、9^2通りの中のH(9,2)=COMB(9+2-1,2)=45通りとなる。

3桁の場合、たとえば123と132と213と231と312と321はm=6で同じ値になる。
したがって、H(9,3)=COMB(9+3-1,3)=165通り。(実際に679は152番目に現れる)

順に求めるとしても、このように組合せを適用すれば計算量(回数)が減る。

一般的に、
10進法の場合
持続係数が0、1になるのは、0、10である。

k桁の数nの各桁を、a[1],a[2],…,a[k](k≧2, a[1]≠0)とすると、
n=a[1]*10^(k-1)+a[2]*10^(k-2)+ … +a[k-1]*10+a[k]と表される。
mは、i=2,…,kでa[i]に0を含む場合は、m=0
1を含む場合は、1の数だけ桁数が減ったものに帰着される。
0と1を含まない場合、i=1,2,…,kで、2≦a[i]≦9なので、
m=a[1]*a[2]* … *a[k]=2^q * 3^r * 5^s * 7^t と表される。

したがって、k桁の数nは、2≦a[1]≦a[2]≦ … ≦a[k]≦9となる数の組を対象とすればよい。


★ケース2 mの持続係数の計算
P(n)=P(m)+1より、帰納的に「(持続係数がBの最小数)≦P(m)」でないと、nが持続係数が(B+1)と成らない。
計算過程でチェックして中断できる。(最後まで計算しなくてよい)


p進法でも同様である。



!15桁までは、10進または2進モードで実行可能です。

!持続係数(耐久数)
! a 持続係数がaである最小数
! 0  0
! 1  10
! 2  25
! 3  39
! 4  77
! 5  679
! 6  6788
! 7  68889
! 8  2677889
! 9  26888999
!10  3778888999
!11  277777788888899


LET t0=TIME


PUBLIC NUMERIC P !進法
LET P=10

LET K=15 !最大の桁数 a1,a2,a3,…の数

PUBLIC NUMERIC B !持続係数
LET B=2 !※2以上

DIM A(K) !組(a1,a2,a3,…)の並び

PUBLIC NUMERIC MN(0 to 20) !持続係数がaの最小数
LET MN(0)=0
LET MN(1)=P

PUBLIC NUMERIC KETA !探索対象の桁数
FOR KETA=2 TO K !※2以上
   PRINT P;"進法"; KETA;"桁の数"; COMB((P-2)+KETA-1,KETA);"通り"
   CALL try(1, 2,1, A)
NEXT KETA


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

END


EXTERNAL SUB try(s, q,w, A()) !2≦A1≦A2≦A3≦…≦Ak≦P-1を満たす整数の組 H(P-2,k)通り
FOR i=q TO P-1 ![q,P-1]
   LET A(s)=i
   LET m=w*i !「各桁の数の積」を求める

   IF s=KETA THEN !ひとつの組が求まったら
      CALL check(m,p, t) !それ以降を算出して、該当するもの
      IF t+1=B THEN
         CALL Horner(A,KETA,P, n) !10進法表記へ
         PRINT "持続係数";B;"= "; n
         MAT PRINT A; !P進法表記

         LET MN(B)=n !持続係数がbの最小数

         LET B=B+1 !次へ
      END IF
   ELSE
      CALL try(s+1, i,m, A) !次へ
   END IF
NEXT i
END SUB


EXTERNAL SUB Horner(A(),k,P, t) !ホーナー法でΣA[i]*p^(n-i)を求める
LET t=A(1)
FOR i=2 TO k
   LET t=t*P+A(i)
NEXT i
END SUB


EXTERNAL SUB check(n,P, w) !P進法表示の持続係数
LET w=0 !持続係数
DO WHILE n>=P !一桁になるまで
   LET w=w+1

   LET t=n !第1の数
   LET n=1 !第2の数
   DO WHILE t>0 !P進法の進数変換より
      LET n=n*MOD(t,P) !※各桁の数の積
      IF n=0 THEN EXIT DO !※
      !!!LET x=MOD(t,P) !※各桁の数で0でないものの積
      !!!IF x>0 THEN  LET n=n*x !※
      LET t=INT(t/P) !次の桁へ
   LOOP
   !!PRINT n; !遷移を表示する

   IF n<MN(B-1-w) THEN EXIT DO !持続係数がbの最小数≦P(m)
LOOP
!!PRINT w !値を表示する
END SUB
 

戻る