和と積の一致問題（考察５）

　和と積の一致問題（考察５）を示します。

（考察５）

　一般に、合成数pq(2≦p≦q)について、つぎの等式が成り立つ。

　　pq = p×q×1×…×1 = p+q+1+…+1
1がpq-p-q個 1がpq-p-q個

　自然数の個数N(p,q)は、pq-p-q+2個となる。

　合成数pqr(2≦p≦q≦r)について、つぎの等式が成り立つ。

　　pqr = p×q×r×1×…×1 = p+q+r+1+…+1
1がpqr-p-q-r個 1がpqr-p-q-r個

　自然数の個数N(p,q,r)は、pqr-p-q-r+3個となる。

このとき、N(p,q,r)>N(p,q) が成り立つ。

　　N(p,q,r)-N(p,q)=(pqr-p-q-r+3)-(pq-p-q+2)
=pqr-pq-r+1
=pq(r-1)-(r-1)
=(pq-1)(r-1)>0

　合成数pqrs(2≦p≦q≦r≦s)について、つぎの等式が成り立つ。

　　pqr = p×q×r×s×1×…×1 = p+q+r+s+1+…+1
1がpqrs-p-q-r-s個 1がpqrs-p-q-r-s個

　自然数の個数N(p,q,r,s)は、pqrs-p-q-r-s+4個となる。

このとき、N(p,q,r,s)>N(p,q,r) が成り立つ。

　　N(p,q,r,s)-N(p,q,r)=(pqrs-p-q-r-s+4)-(pqr-p-q-r+3)
=pqrs-pqr-s+1
=pqr(s-1)-(s-1)
=(pqr-1)(s-1)>0

そこで、合成数を生成しながら、この性質を使って、与えられた自然数の個数を満たす和と積が一致する等式を求める効率のよいプログラムが書ける。

●プログラム

' Tiny Basic で記述。
' 和と積の一致するつぎの等式を満たす解を求めるプログラム
' 等式　P(1)*P(2)*…*P(K-1)*1…*1 = P(1)+P(2)+…+P(K-1)+1+…+1
' 
Public P(9):  ' 深さkの因数P(k)(≧2)の値を保存する配列。
              ' 2≦P(1)≦P(2)≦…≦P(9)
Public PMAX:  ' 因数の最大値。
Public KMAX:  ' 探索する最大の深さ。
Public COUNT: ' 解の個数。
Public N:     ' 自然数の個数。
'
' 初期設定。
PMAX=50
KMAX=9
P(0)=2
'
Do
  ' 自然数の個数Nを読み込む。
  Read N
  If N <= 0 Then Exit Do
  '
  Print Using"自然数の個数=####　";N
  '
  ' 初期設定。
  COUNT=0
  ' 探索の開始。
  Call Tansaku(1)
  Print
Loop
End
'
' 
Sub Tansaku(K)
  If K > 2 Then
    ' 等式　P(1)*P(2)*…*P(K-1)*1…*1 = P(1)+P(2)+…+P(K-1)+1+…+1
    ' における自然数の個数Tの計算。
    W=1
    For J=1 To K-1: W=W*P(J): Next J
    For J=1 To K-1: W=W-P(J): Next J
    T=W+K-1
    '
    ' 合成数P(1)*P(2)…*P(K-1)を利用する等式の自然数の個数Tが
    ' Nを超えた場合、その後の合成数を利用する等式の自然数の個数は
    ' 必ずTを超える性質を利用して、探索を進めないで戻る。
    If T > N Then Exit Sub
    '
    ' 解の表示。
    If T = N Then
      COUNT=COUNT+1
      Print Using"[###] ";COUNT;
      ' 等式の表示。
      For I=1 To K-1: Print Using"##×";P(I);: Next I
      Print Using"(1が###個) = ";W;
      For I=1 To K-1: Print Using"##＋";P(I);: Next I
      Print Using"(1が###個)";W;
      Print
      Exit Sub
    End If
    '
    ' 探索の深さ制限KMAXを超えたら戻る。
    If K > KMAX Then Exit Sub
  End If
  ' 
  ' つぎの因数候補を指定する。因数の最大値はPMAXとする。
  For I=0 To PMAX-P(K-1)
    P(K)=P(K-1)+I
    Call Tansaku(K+1)
  Next I
End Sub
'
' データ。
Data 2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20
Data 21,22,23,24,25
Data 0