『パスカルの三角形 Part2』解答


◆愛知県 Y.M.Ojisan さんからの解答。

【解答】

難しいですね。
x が単独素数の冪である場合に限り、N と x から単純に数える(計算量:N2のオーダー)よりは簡単に計算する方法(計算量:log(N)のオーダー)を示します。

【xが素数=Pの場合】

xが素数の場合を下図(x=2,3,5の場合をmod xで計算し色分け)に示す。
xの倍数ではない方に着目すると、
次元log(x(x+1)/2)./log(x)のフラクタルになっていることが分かります。

従って、Nを通常のx進法で表わし 
N= K

k=0
Rk*xk であるとき

「N段のパスカルの三角形の項」のxの倍数の項数G(N)は次のように表わせます。

G(N)=N2-H(K)

ここで
H(k)= Rk(Rk+1)
2
*(x(x+1)
2
) k +(1+Rk)H(k-1)  & H(-1)=0

証明はx=Pmの場合に含みます。

【xが単独素数の冪 x=Pmの場合】

この場合も単純ではありませんが、一応フラクタルになっています。
下図参照。

【補題1】

Pを素数とし、0≦A<Pk, 0≦B<Pk ,
0≦α<P, 0≦β<P,1≦kの整数であるとき、
F P ( Combination(A+B+(α+β)Pk, A+αPk)
Combination(A+B, A)
)=[A+B+(α+β)Pk
Pk+1
]

ここでFP (Q)はQの素因数Pの冪数である。
また[ ]はガウス記号である。

∵ 一般にFP(Q!)= log(Q)/log(P)

J=1
[ Q
PJ
] である。

従って、
FP((A+αPk )!)


J=1
{[ A
PJ
] +αP k―J }+
J=1
[ α
PJ
]
=FP(A! )+α Pk-1
P-1
同様に、FP((B+βPk )!) =FP(B! )+β Pk-1
P-1

また、

FP((A+B+(α+β)Pk )!)


J=1
{[ A+B
PJ
] +(α+β)P k―J }+ [ A+B
Pk+1
α+β
P
]
=FP((A+B)! )+(α+β) Pk-1
P-1
+[ A+B+(α+β)Pk
Pk+1
]

F P ( Combination(A+B+(α+β)Pk, A+αPk)
Combination(A+B, A)
)
=FP((A+B+(α+β)Pk )!)−FP((A+αPk )!)−FP((B+βPk )!)−FP((A+B)! )+FP(A! )+FP(B! )
=[A+B+(α+β)Pk
Pk+1
]

そしてこの値は0か1である。以上

 これは、A,B<PにおけるFP ( Combination(A+B, A))が分かっているとき、
C,D<Pk+1に対するFP ( Combination(C+D, C)) は
C+D<Pk+1 のとき FP ( Combination(A+B, A))に等しく、
C+D>Pk+1のとき FP ( Combination(A+B, A))+1であることである。
ただし C≡A、D≡B mod P

【補題2】

Pを素数とし、0≦α<P, 0≦β<Pの整数であるとき。
F P (Combination(α+β))=[ α+β
P
]

∵ 補題1でk=0 A=B=0の場合と考えればよい。
0か1である。

【本題】

よってN段のパスカルの三角形のPMの倍数の個数GP(M,N)は次のアルゴリズムで計算することができます。

<定義>

引数の数が可変の関数、
UP(K,m,[RK-1,RK-2,RK-3,・・・ ,R1,R0,])、
DP(K,m,[RK-1,RK-2,RK-3,・・・ ,R1,R0,])
を定義します。

ここで[RK-1,RK-2,RK-3,・・・ ,R1,R0,]P はK桁のP進数を表わします。

UP(K,m,[RK-1,RK-2,RK-3,・・・ ,R1,R0,])  m=0〜M :
0≦A,0≦B,A+B<PK  において Fp(Combination(A+B, A))=m の数
ただし、m=Mの場合は Fp(Combination(A+B, A))≧M の数

DP(K,m,[RK-1,RK-2,RK-3,・・・ ,R1,R0,]) m=0〜M :
A<PK,B<PK,PK≦A+B において Fp(Combination(A+B, A))=m の数
ただし、m=Mの場合は Fp(Combination(A+B, A))≧M の数

従って GP(M,N)=UP(Y,M,[RY-1,RY-2,RY-3,・・・ ,R1,R0,])

また、特別の場合として特に Up(K,m,[P,0,0,・・・ ,0,0,])= Up(K,m)、
Dp(K,m,[P,0,0,・・・ ,0,0,])= Dp(K,m) と書きます。

<手順>

(1) N=[RY-1,RY-2,RY-3,・・・ ,R1,R0]を求めておきます。
つまりNはY桁です。

(2) 次の漸化式で 
Up(K,m)、Dp(K,m)、 K=1〜Y m=0〜Mを求めておきます。

Up(1,0)=P(P+1)/2
Up(1,m)=0 for M≧m>0
Dp(1,0)=0
Dp(1,1)=P(P-1)
Dp(1,m)=0 for M≧m>1

Y>K>0

Up(K+1,m)=(P(P+1)/2)*Up(K,m)+(P(P-1)/2)*Dp(K,m)   for m=1〜M
Dp(K+1,0)=0
Dp(K+1,m,)=(P(P-1)/2)*Up(K,m-1)+(P(P+1)/2)*Dp(K,m-1)  for m=1〜M−1
Dp(K+1,M,)=(P(P-1)/2)*(Up(K,M)+Up(K,M-1))+(P(P+1)/2)*(Dp(K,M)+Dp(K,M-1))
(3) 次の漸化式で
Up(K,m, [RK-1,RK-2,RK-3,・・・ ,R1,R0,])、
Dp(K,m ,[RK-1,RK-2,RK-3,・・・ ,R1,R0,])、
K=1〜Y  m=0〜Mを求めます。

Up(1,0)=R0(R0+1)/2
Dp(1,0)=0
Up(1,1)=0
Dp(1,1)= R0(2P-1-R0)/2
Up(1,m)=0  for M≧m>1
Dp(1,m)=0 for M≧m>1

K+1>1

Up(K+1,m,[RK-1,RK-2,RK-3,・・・ ,R1,R0,])
= (RK(RK+1)/2)*Up(K-1,m)+(RK(RK-1)/2)*Dp(K-1,m) +(RK+1)*Up(K-1,m, [RK-2,RK-3,・・・ ,R1,R0,])+RK*Dp(K-1,m, [RK-2,RK-3,・・・ ,R1,R0,])
Dp(K+1,0,[RK-1,RK-2,RK-3,・・・ ,R1,R0,])=0

Dp(K+1,m,[RK-1,RK-2,RK-3,・・・ ,R1,R0,])
= (RK(2P-1-RK)/2)*Up(K-1,m-1)+(RK(2*P+1-RK)/2)*Dp(K-1,m-1)+(P-1-RK)*Up(K-1,m-1, [RK-2,RK-3,・・・ ,R1,R0,])+(P-RK)*Dp(K-1,m-1, [RK-2,RK-3,・・・ ,R1,R0,]) 
for m=1〜M−1

Dp(K+1,M,[RK-1,RK-2,RK-3,・・・ ,R1,R0,])
= (RK(2P-1-RK)/2)*(Up(K-1,M-1)+Up(K-1,M))+(RK(2*P+1-RK)/2)*(Dp(K-1,M-1)+ Dp(K-1,M))+  (P-1-RK)*(Up(K-1,M-1, [RK-2,RK-3,・・・ ,R1,R0,])+ Up(K-1,M, [RK-2,RK-3,・・・ ,R1,R0,]))+(P-RK)*(Dp(K-1,M-1, [RK-2,RK-3,・・・ ,R1,R0,])+ Dp(K-1,M, [RK-2,RK-3,・・・ ,R1,R0,])) 

ややこしいので、EXCELのマクロとしてのBASICのソースを添付しておきます。

【xが合成数の場合】

x=2×3の場合を下図に示します。
フラクタルとフラクタルの合成はカオスのようで、このアプローチではうまく行かないようです。


 『パスカルの三角形 Part2』

 数学の部屋へもどる