|
|
>「各桁の数の積」による持続係数（multiplicative persistence）
> 与えられた整数のすべての桁の数を掛けて第２の数を作り、
> その数の各桁の数を掛けて第３の数を作り、この操作を反復して、
> 最後に１桁の数を得るまでの反復回数である。
> たとえば、８９は８９→７２→１４→４と３回で１桁の数になるから、８９の持続係数は３である。
0からnまでコツコツと順に計算していく過程で、効率よく求める方法はないか検討する。
nの持続係数をP(n)とする。
正整数nの各桁の数字をかけて得られる値をmとすると、n＞mとなり、P(n)=P(m)+1となる。
★ケース１ 組合せより「場合の数」を減らす
２桁の場合、たとえばn=36とn=63はm=18で同じ値になる。
また、桁に0を含むものも除けば、9^2通りの中のH(9,2)=COMB(9+2-1,2)=45通りとなる。
３桁の場合、たとえば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となる数の組を対象とすればよい。
★ケース２ mの持続係数の計算
P(n)=P(m)+1より、帰納的に「(持続係数がBの最小数)≦P(m)」でないと、nが持続係数が(B+1)と成らない。
計算過程でチェックして中断できる。（最後まで計算しなくてよい）
p進法でも同様である。
!15桁までは、10進または２進モードで実行可能です。
!持続係数（耐久数）
! 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 !第１の数
LET n=1 !第２の数
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
|
|