分割数の2つの特別なモデル

自然数Nの2つの特別なパーティションを使用して、分解アルゴリズムを構築できます。 以前の投稿では、これについて議論され、著者に質問が行われました。因数分解の研究では、検討中のアプローチにより、特別なパーティションを生成するプログラムがあれば、原理的に多数の因数分解（FBCH）の問題を短時間で解決できると規定されていました。 この作業では、著者はパーティションの特殊化の詳細をより詳細に明らかにします。 Habrコミュニティのメンバーの大半はプログラマーなので、WFBHに興味を示し、許容時間内（年、月、または数十時間ではなく）に解決し、手を試して、特別なフラグメンテーションジェネレーターのプログラムの開発にスキルを投入することをお勧めします。 以下のテキストから次のように分割するには、数値Nのf不変量 、数値のビット数に依存しないプロパティ、または数値N自体が必要です。数値13のすべてのパーティションのテーブルは、4つだけが特別であり、最初の3つの特別なパーティション。





自然数を破る問題

正の整数Nのパーティションは、Nより小さい正の整数k0、k1、k2、k3、...、ktの有限の非増加シーケンスであり、合計k0 + k1 + k2 + k3 +、...、+ kt = N、数値k _i 、 i = 0 （1）tは、パーティションのブロック（パーツ）と呼ばれます。 番号のパーティションは順序付けられており、無秩序です。 番号[1、2]の奇数部分への分割と偶数部分への分割、数字の分割が同一部分と異なる部分に分割などがあります。 この目的のために、Ferrerのポイントグラフを使用して、パーティションのある部分と別の部分の差（Δ= 1）を制限して、数字を異なる部分に分割するグラフィカル表現を使用します。

数の因数分解の問題に関連する数Nの分割の問題では、数N自体ではなく、そのφ不変量である数k _p （N）/ 2、つまりNの制限輪郭の半分の数のパーティションの2つの特殊なケースを扱います。さらに、整数（k）（N）/ 2のパーティションを整数と小数に対応し、左（N）と右（N）の奇数の自然数に対応します。 数k _p （N）/ 2のパーティションのパーティションセットのグラフィカル表現は、連続する後続の線から形成される三角形の点線のフェレール図の一部として台形の形をしています。 台形のベースの1つ（上部または下部）には常にそのポイントの半分のみが含まれます。 ここで考慮される2つのタイプのパーティションの主な特化は、互いに番号のパーティションの部分の差が1 だけ ∆ = 1であり、番号のパーティションの極端な部分（グラフィック表現の台形の底辺であるライン）のみが隣接するパーティションと異なる量よりも大きくなる可能性があることですユニット。 極端な線（上-Nlの場合、下-Npの場合）は常に半分に分割されます。 パーティション内の用語については、こちらをご覧ください（こちら） 。 半分に分割されたラインに偶数個のポイントが含まれている場合、Nのパーティションのすべての部分は整数です。そのようなラインのポイントの数が奇数である場合、パーティションの極端な部分とk _n （N）/ 2自体は小数です。 これらの特別なパーティションの他の機能にも注意してください。 これらの機能は、本質的に作品の主要な内容である数値の例を考慮すると、簡単かつ明確に認識されます。



まず、N（正しい数）の場合、パーティションによるk（N）/ 2の表現は常に異なる項によってのみ形成され、その数の半分のみが小さい輪郭からの合計に含まれます。

第二に、Nl（左の数値）の場合、k _p （N）/ 2が小数の場合、パーティションによる限界輪郭数の半分（数値k _p （N）/ 2）の表現は常に異なる部分によって形成されます。

第3に、Nlの場合、k _p （N）/ 2が整数の場合、合計の2つの項は一致し、さらに、そのようなペアの1つの項は合計の大きい輪郭の数の半分になります。 これらの概念を数値例で説明しましょう。



例1 119 = 3（mod4）なので、左の奇数Nl = 119が与えられます。 この数の限界輪郭の長さは119 + 121 = 240です。限界輪郭の数はk _p （119）= 240/8 = 30です。数119のF不変量はk _p （119）/ 2 = 30/2 = 15です。数値Nのf不変式の形式は15 = 3 + 4 + 5 + 6/2 = 3 + 4 + 5 + 3です。 合計で、3に等しい2つの同一の用語が得られました。 φ不変量のパーティションが数N = 119の因数分解につながることを確認するために、パーティションからNを復元します。そのすべての項は輪郭の数です。 項に8を掛けます：

3•8 + 4•8 + 5•8 + 6•8 = 24 + 32 + 40 + 48

最後の（より大きな）項は、合計でその左半分のループ23 + 25 = 48、つまり 23.したがって、Nl = 119（チェック）24 + 32 + 40 + 23 = 119の間隔の長さを設定します。

LFDの等高線と半回路の境界は常に正方形であり、それらの値は区間の極端な項から取得されることを思い出してください。

小さい境界（3）番号3の回路の場合、（3）=（2•3-1） ² = 25 = 5 ² ;

回路番号6のGB間隔の大きな境界（6）、GB = Hz（6）=（2•6） ² = 144 = 12 2-6番目の回路の左半円の右境界。

最後の仕上げ：Nは二乗の差、つまり 間隔差

N = 12 2-5 ² =（12-5）（12 + 5）= 7•17 = 119で、因数分解が得られます。



自然奇数N（x1、xo）= 3tの3の倍数は、常に3つの隣接するセミループのみで形成され、そのうちの2つはループ全体です。 このような番号の場合、番号付けモデルは非常に単純です。 k-数Nの完全な輪郭の数を見つけます。

左の奇数の場合

k _p （N）/ 2 =（k + 1）/ 2 + k => k _p （N）= 3k + 1 => k =（k _p （N）-1）/ 3。

右の奇数の場合

k _p （N）/ 2 =（k –1）/ 2 + k => k _p （N）= 3k-1 => k =（k _p （N）+ 1）/ 3。

例2 129 = 1（mod4）なので、右の奇数N= 129が与えられます。 この数値の限界輪郭の長さは127 + 129 = 256です。限界輪郭の数はk _p （129）= 256/8 = 32です。数値129のf不変量はk _p （129）/ 2 = 32/2 = 16です。計算された値k =（32 + 1）/ 3 = 11これは、2つのハーフループ43 + 45 = 88 = 11•8.の大きな輪郭の数です。 間隔を形成するために、11-1 = 10の番号を持つ前の回路の半回路の合計に含めます。 M = 4k +1 = 41。

そして最後に、半回路の合計41+ 43 + 45 =129。区間の境界を見つけ、数N = 129を因数分解するために残ります。



1つの極値項を除くパーティションの合計のすべての項は、常に単位が異なります。つまり、これらは自然数列で次の数値k _iです 。k _p （N）/ 2 = ∑ ^t _{i = p} k _i ±k / 2

ここで、pは初期（より小さい）輪郭全体のインデックス番号です。

tは、有限の（より大きな）輪郭全体のインデックス番号です。

±-合計の符号は、数値Nの形式（左k> k _t 、右k <k _p ）によって決定されます。

kは極端な等高線（インデックスなし）の数であり、そのうちの半分のみが合計に含まれます。 数k _p （N）/ 2のパーティションの合計が1増加する自然数によって形成されるという事実は、自然数の番号付けモデルにとって重要です。

このタイプのすべてのパーティション（すべての和k _n （N）/ 2）は、フェレールの三角ポイント図（パーティションのグラフィック表示）で表されることが判明し、そこから取得できます。

表1に、このような図と、Nの間隔および番号付けモデルに関する追加情報を添付しています。

表1-間隔の特性と数Nの番号付けモデル





表の中央部分では、数値231 = 3∙77 = 7∙33 = 11∙21の制限ハーフループk _p （N）/ 2）のグラフィックパーティションの値が、他のユニットとは異なる部分（ドットのある行）に配置されます。 より小さい除数は、Nの間隔を形成する半回路の数を常に示します。



間隔モデルは、等高線/半回路の位置（長さ）の間隔であり、その合計はNに等しくなります。

N = 231の場合、次のようになります。

第1間隔モデル1回路+半回路152 + 79 = 75 + 77 + 79-2つのユニットの長さが異なる3つの連続した半回路。

第2区間モデル3回線+半回線56 + 64 + 72 + 39 = 27 + 29 + 31 + 33 + 35 + 37 +39-2ユニットの長さが異なる7つの連続した半回線。

5回路+半回路の3番目の間隔モデル

24 + 32 + 40 + 48 + 56 + 31 = 11 + 13 + 15 +17 +19 +21 + 23 + 25 + 27 + 29 +31

-2つのユニットの長さが異なる11の連続した半回路。



番号付けモデルは、数Nを表す等高線番号と半回路の集合であり、その合計はf不変量の値に等しくなります。

したがって、N = 231の場合、f不変量はk _p （N）/ 2 = k _p （231）/ 2 = 29です。

k _p （N）/ 2 = k _p （231）/ 2 = 19 + 20/2 = 7 + 8 + 9 + 10/2 = 3 + 4 + 5 + 6 + 7 + 8/2

平等な量は3つの番号付けモデルです。 これらの用語は、図の線kに対応します。

両方のタイプのモデルは密接に関連しており、必要に応じて相互に変換できます。

この図に基づいて、最初の1000以内の奇数の正の整数Nの場合、2つの因子に分解できます。 表の最初の4列には、区間モデルの特性（回路特性）が含まれています。 散布図の右側の列はアウトライン番号です。 最後の2列は、番号付けモデルの特性です。 レベルは、テーブルの最下部からn番目の行です。 行の特性値は、下の行から増分で表示されます。 最後の列では、前の行のポイントの合計が、現在の行の半分のポイント数と合計されます。 最後から2番目の列では、完全な行のポイントの合計

左Nl数の場合、長さNlの間隔に対応するそのような合計k _p / 2は、三角形からの特定の数のポイントとラインを常に含み、上部にはラインのポイント数の半分のみを含みます。 明らかに、k _p / 2に等しい値または最も近い大きい値に対応するが、上の行の半分を含む合計から行を修正する場合、合計の下の行の番号を決定するために、下の（より小さい）輪郭または対応する行の数のみを決定するために残りますk _p / 2の合計。 この値は、固定された最上行のレベルのポイントの合計とk _p / 2の値の差によって決まります。 考慮中の列にそのような差がある場合、それに対応する行とその下の行は合計で考慮されません。

値C ² _{k + 1} > k _p / 2から差C ² _{k + 1} -k _p / 2の検索を開始し、計算された差が一致するまでk 2/2と比較します。 不一致がある場合は、kの値を増やします。



例3 正しい数N（x1、x®）= 621に対して、因数分解して、数k _p （N）= k _p （621）=（621–1）/ 4 =（619 + 621）/ 8 = 155の限界輪郭の長さの値を決定します。次に、k _p （621）/ 2 = 77.5の値を決定し、LFDの先頭に最も近い差C ² _{k + 1} -k _p / 2の値を見つけます。 表1の列C ² _{k + 1では、} k = 12について、k _p （621）/ 2 = 77.5を超える78の値を見つけます。

次に、望ましい差はC ² _{k + 1} -k _p / 2 = 78-77.5 = 0.5です。 kのある値について、見つかった差がk 2/2の値と一致するかどうかをチェックします。 一致は、テーブルの一番下の行の値が0.5で発生します。

これから、形成された間隔の小さい輪郭の数k _p ^2/2 = 0.5 => k = 1が決定されます。 数値N = 621を表す間隔は、最初の回路の中央の正方形（偶数）ポイントから始まり、12番目の回路に包括的に到達します。 境界の値を通じて、数Nの間隔の長さは式N =-=1i2-i2で表されることが知られています。 区間の境界での輪郭の数がわかると、その境界点が見つかります。 間隔の境界は次のとおりです。

•k = 1の左境界線、GL =（2k） ² =（2•1） ² = 4

•k = 12の正しい値は=（2k + 1） ² =（2•12 + 1） ² = 625です。

その場合、N =-=1i2-i2 = 625-4 =621。一方、境界二乗が存在する場合、数値N =1i2-i2 =（25 + 2）の因数分解は簡単に実行できます（25-2） = 27•23。



例で検討した因数分解問題を解決するためのスキームは、境界の他の代替ペアの検出を保証します。 k 2/2と一致する差C ² _{k + 1} -k _p / 2を検索すると、k = 19が大きくなるとそのような一致が生じます。等式C ² _{k + 1} -k _p / 2 = 190-77.5 = 112 、5つのうち小さい方を見つけます。 k =√2×112.5 =√225= 15.これで、区間と因数分解Nの境界の検索を開始できます。

間隔の境界は次のとおりです。

•k = 15での左境界、Gl =（2k） ² =（2•15） ² = 900、

•k = 19の正しい値は=（2k + 1） ² =（2•19 + 1） ² = 392 = 1521

•N =-=1i2-i2 = 1521-900 = 621および

•N =1i2-i2 =（39 + 30）（39-30）= 69•9。



例4 （ 左の数値の除算で、合計の数値の半分（整数ではない）は、より大きな輪郭から取られます）。

数N = 235を与え、数N = 235≡3（mod4）を残します。

限界輪郭の長さLn = 235 + 237 = 472、その数k _p = L / 8 = 472/8 = 59、k _p / 2 = 29.5、限界輪郭の境界の値：右=（2k _p ） ² = 118 ² 、左のGL =（2k _n –1） ² = 117 ²それらは、数N = 235∙1の自明な展開に対応します。

ナンバリングモデルから、k _p / 2 = 29.5です。 N = 235の場合（前述の例を参照）k _p （235）/ 2 = 29.5

列k 2/2 = 40.5の最も近い値は、行k = 9にあります。

これは、差k 2/2-k _p / 2 = 40.5-29.5 = 11に対応します。これは、列「sum」にはありません。

次のレベルはk = 11およびk 2/2 = 60.5です;これは、差k 2/2-k _p / 2 = 60.5-29.5 = 31に対応し、「合計」列にもありません。 次のレベルはk = 13およびk 2/2 = 84.5で、これは差に対応します

k 2/2-k _p / 2 = 84.5-29.5 =55。これは、数k = 10の行の「sum」列にあります。

このことから、10番以下から始まるすべての行がk _p / 2の合計に含まれないという結論になります。 したがって、k _p / 2 = 29.5 = 11+ 12 + 13/2。

与えられた数を因数分解します。 番号の番号付けモデルを形成する等高線番号が見つかります：k = 11、12、および13。k= 13から、この等高線の左半分のみが式に入ります。

輪郭の長さL（11）= 8•11 = 88を計算します。 L（12）= 8•12 = 96; L（13）= 8•13 = 104; 13番目の等高線の左半分はm（13）= 104/2 –1 = 51です。間隔モデルは88 + 96 + 51 = 43 + 45 + 47 + 49 + 51 = 235です。

区間モデルの境界を定義します。

•（13）=（2•13） ² = 26 ² = 676;

•Ch（11）=（2•11–1） ² = 21 ² = 441。

数N = 235を因数分解できるようになりました

N（x1、xo）= 235 =（x1 + xo）（x1-xo）=（26 + 21）（26–21）= 47•5 = 235。

例5 （ 正しい数値の除算。ここで、数値の半分（整数ではない）は小さい輪郭から取られます）。

N = 357とします。これは正しい数ですN = 357≡1（mod4）。限界輪郭の長さはLn = 357 + 355 = 712、その数はk _p = L / 8 = 712/8 = 89、k _p / 2 = 44.5、境界制限回路：

•左GL =（2k _p –1） ² = 177 ² 、

•平均Hz =（2k _n ） ² = 178 ² 、

•右側のΓ=（2k _n + 1） ² = 179 ²これらは、数N = 357∙1の自明な展開に対応します。

a）x1 = 19; ho = 2; N =（2∙58）-（58∙2-1）=1i2-i2 = 19 2-2 ² = 361-4 =（19 + 2）∙（19-2）= 21∙17 = 357、k _n / 2 =½+ 2 + 3 + 4 +5 + 6 + 7 + 8 + 9 = 44.5

b）x1 = 61; ho = 58; N =（2∙58）-（58∙2-1）=1i2-i2 = 61 2-58 ² = 3721-3364 =（61 + 58）∙（61-58）= 119∙3 = 357; k _p / 2 = 29/2 + 30 = 44.5

任意の輪郭の長さと奇数の正方形間の自然数列の間隔は8の倍数です。mod8の奇数の正方形の剰余は1です。5以上の奇数の素数の正方形の値の差は常に24の倍数です（7 2-5 ² = 24）。 これは次のように表示できます。 2つの奇数の素数の二乗を考えて、それらの差を見つけます。 3つの隣接する数字2n-1、2n、2n + 1のうち、1つは常に3の倍数です。 私たちの場合、極値は仮説により素数であるため、これは数n = 3tです。

•LF1 ² =（2n-1） ² = 4n 2-4n + 1 = 1 + 4n（n-1）= 1 + 8 C _p ² 、

•22 =（2n + 1） ² = 4n ² + 4n + 1 = 1 + 4n（n + 1）= 1 + 82 _{n + 1} 、

•LF2 ² -LF1 ² = 8（C ² _{n + 1} -C _n ² ）= 4n（n + 1-n + 1）= 8n = 8・3t = 24t。

数Nが3の倍数である場合、区間モデルでは、3つの半回路が並んで形成されます。 言い換えれば、数値が正しい場合、半円は小さい輪郭からのものです。 N = 357 = 119•3の場合、k _n / 2 = 44.5。 半円数の値は、式（k _p / 2 –1）/ 3 =（44/5-1）/ 3 = 14.5によって決定されます。 したがって、小さい輪郭の数は14.5•2 = 29で、次の輪郭の数は30です。実際、29/2 +30 = 44.5 = k _p / 2です。 数Nが5の倍数（5つのハーフループで形成）の場合、数（k _p / 2-6）/ 5。



実施例6 （ 間隔の特性と3の倍数のナンバリングモデルの関係 ）

左の数値N（x1、xo）= 183および右の数値N（x1、xo）= 189について、因数分解し、数値の限界輪郭の数と長さを決定しますk _p （Nl）= k _p （183）=（183 + 185）/ 8 = 46、およびk _p （Np）= k _p （189）=（187 + 189）/ 8 =47。次に、番号付けモデルk _p （183）/ 2 =（k + 1）の制限ハーフループの数の方程式を作成します。 / 2 + k、そこからk _p = 3k + 1およびk =（k _p -1）/ 3 = 45/3 = 15。

•N = 183右偶数Hzの間隔の大きな境界（16）=（2・16） ² = 32 ² = 1024

•小さい左境界はGl（15）=（2•15-1） ² = 29 ² = 841です。

数値の因数分解N = 183 = 32 2-29 ² =（32 + 29）（32-29）= 61•3。

N（x1、x）= 3tの形式の正しい数と区間モデルの等高線の数の合計との関係は次のとおりです。

回路番号の半分に間隔の次の回路の番号を加えたものは、調査対象の数の制限回路の数k _p （Np）/ 2に等しくなります。

正しい数N（x1、x®）= 189の場合、制限半導体の値k _p （189）/ 2 =（k – 1）/ 2 + k、

whence k _p = 47 = 3k-1 and k =（k _p + 1）/ 3 = 48/3 =16。N= 189の間隔の小さい境界は15 Hz回路にあります（15）=（2•15） ² = 30 ² = 900および（16）=（2•16 + 1） ² = 33 ² = 1089。

数値の因数分解N = 189 =（33 + 30）（33-30）= 63•3

同様の計算は、5、7、9などの左右の倍数に対しても実行できます。



使用されたソースのリスト

[1] Hall M. Combinatorics。 -M。：ミール、1970 .-- 424 p。

[2] Andrews G.パーティション理論。 -M。：Science GRFML、1982年。 -256秒