この頁では、いろいろな数についての素因数分解の結果を掲載している。
このプロジェクトは、1991年に開始し、NEC PC9801VX2 + 80386 (8MHz ボード) を使って
各種の数の100桁以下の数について完全分解することを目標としてスタートした。
使用したプログラムは、UBASICに添付されている素因数分解プログラム RHOX, ECMX, MPQSX である。
当初のターゲットは、primorial(素数の積)±1、n!±1、primorial±nextprime、Fibonacci数、Lucas数、
Cullen/Woodal(Riesel)数(n・2n±1)、Wolstenholme数1/2、An/!n/Kn (階乗の和)、Euler数、Bernoulli数
であった。
1997年にWebで公開して以来、多くの人が本プロジェクトに参加するようになった。
苫米地氏の factor.exe (ECM + PPMPQS)、Paul Zimmerman の GMP-ECM 等の新しいツールを用いて、
1998年8月27日には、100桁以下の全ての数の分解が完了した。
その後、100桁以上の数に対する結果が多くの人から寄せられてきたため、改めて、対象桁数を150桁前後に再設定し、
また新たな対象として、Wolstenholme数3/4、j(tau) (楕円モジュラー関数のフーリエ展開の係数)、分割数
を追加した。
現在、我々は250桁以下の完全分解を目標としているが、それ以前に、100桁以下の未解決数も数多く残っている。
より多くの人が協力してくれることを願う。
Old log : 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 素因数分解結果レポート (1999/08/04 まで)
0. カニンガムプロジェクト
for b = 2, 3, 5, 6, 7, 10, 11, 12, up to high powers n (Samuel S. Wagstaff, Paul Leyland) for b = 13, 14, ... , 99 (perfect powers excluded) n satifies the constraint bn < 10255 (Richard Brent) |
The Cunningham Project (Samuel S. Wagstaff) Factor Tables (Richard Brent) Computational Number Theory (CNT) (Paul Leyland) ECMNET (Paul Zimmerman) NFSNET (Jeff Gilchrist) Mersenne Prime Fermat factoring status (Wilfrid Keller) Factors for 2^n+1 and 2^n-1 for large n (Arjen Bot) Repunit primes and factors (Torbjon Granlund) Factorizations of Repunits Numbers (Yousuke Koide) Factorizations of near-repdigit numbers (M.Kamada) aba (Hisanori Mishima) | ||||||||||||||
1. #Pn (Primorial) ±1
|
"Primorial" とは、n番目の素数までの積、即ち、
#Pn = p1 * p2 * ... * pnを意味する。 この名称は、"prime (素数)" と "factorial (階乗)" の合成語である。 #Pn + 1 は、「素数は無数にある」という定理の証明で使われる数である。 しかし、この数自体が素数かどうかは別問題である。 最新の結果は、以下のサイト、 ftp://sable.ox.ac.uk/pub/math/で管理されている。 | ||||||||||||||
2. n!±1
|
これらの数も、自明な素因子を持たない。 ただし、nが素数のときに限り、(n-1)!+1はnで割り切れる。 (Wilson の定理) 最新の結果は、Paul Leyland のサイト、 ftp://ftp.cam.uk.eu.microsoft.com/pub/math/factors/及び、Andrew Walker のサイト、 n!+- Factoring Statusで管理されている。結果は以下のとおり。
| ||||||||||||||
3. Compositorial +/- 1 |
"Compositorial" とは、n以下の合成数の積を表す。 nの階乗に対し、Primorialがn以下の素数の積なので、相補的な関係にある。 以下のように記述されることがある。 n! / #Nnこの場合、#Nn はn以下の全ての素数の積を表す。 "Compositorial" という名称は、"composite" と "factorial" からの造語である。 これらの初期の結果は、Dr. Robert G. Wilson, V から寄せられた。 | ||||||||||||||
4. #Pn ± NextPrime | #Pn ± NextPrime は、以下のように定義する。
#Pn = p1 * p2 * ... * pn ± pn+1これらの数も、1.#Pn ± 1 と同じ理由から、自明な素因数を持たない。 つまり、 2 * 3 * 5 * 7 ± 1 を 2, 3, 5, 7 で割ると ±1 が余るように、 2 * 3 * 5 * 7 ± 11 を 2, 3, 5, 7 で割ると ±11 mod 2, 3, 5, 7 が余る。 その他の数論的な性質は特に知られていない。 | ||||||||||||||
5. n!±Next n
|
n!±1が素数であるかどうかが自明でないのと同じ理由で、 これらの数が素数か否かも自明ではない。 | ||||||||||||||
6. Compositorial±Next Composite | 以下の表を元に考えるなら、Compositorial±Next Composite を考察対象に入れるのは、極めて自然な発想である。
| ||||||||||||||
7. Fibonacci数
|
Fibonacci数は以下のように定義される。
F0= 0詳細についてはこちらを参照のこと。 最新の結果は、Blair Kelly が n = 0 〜 9999 までの結果を管理しており、 以下のサイト、 Fibonacci and Lucas Factorizationsで公開されている。結果は以下のとおり。 Fn (n = 0 to 1000) | ||||||||||||||
8. Lucas数
|
Lucas数は以下のように定義される。
L0= 2詳細についてはこちらを参照のこと。 最新の結果は、Blair Kelly が n = 0 〜 9999 までの結果を管理しており、 以下のサイト、 Fibonacci and Lucas Factorizationsで公開されている。結果は以下のとおり。 Ln (n = 0 to 1000) | ||||||||||||||
9. Cullen数
|
Cullen数は以下のように定義される。
Cn = n・2n+ 1最新の結果は、以下のサイトで管理されている。 ftp://ftp.cam.uk.eu.microsoft.com/pub/math/factors/結果は以下のとおり。 Cn (n = 1〜1000) | ||||||||||||||
10. Woodal(Riesel)数
|
Woodal(Riesel)数は以下のように定義される。
Rn = n・2n- 1最新の結果は、以下のサイトで管理されている。 ftp://ftp.cam.uk.eu.microsoft.com/pub/math/factors/結果は以下のとおり。 Rn (n = 1〜1000) | ||||||||||||||
11. Wolstenholme数
|
Wolstenholme の定理
この定理にちなみ、Σ(1/ni) の分子の値を「Wolstenholme数」と命名した。 「素数の逆数の部分和の分子」とは、 1/2 + 1/3 + 1/5 + 1/7 + ... の分子を意味する。 「log2 の部分和の分子」とは、 1 - 1/2 + 1/3 - ... の分子を意味する。 「Moeb(n)/n の部分和の分子」とは、 1/1 + (-1/2) + (-1/3) + 0/4 + (-1/5) + 1/6 + ... の分子を意味する。 「1/i の 1 から m までの和(ただし、gcd(i,m)=1)の分子」は、 Silverman の『はじめての数論』の練習問題に出てくる。 | ||||||||||||||
12. An, !n, Kn (階乗の和)
|
これらの数は、Richard Guy『数論における未解決問題集』 の問題 B43, B44 で扱われている。定義は以下のとおり。 An = n! - (n-1)! + (n-2)! -+ …… -(-1)n | ||||||||||||||
13. Euler数
|
Euler数の定義は以下のとおり。
計算方法の詳細についてはこちらを参照のこと。 1998/11/25 に、Dr. Samuel S. Wagstaff Jr. より、 「1995/02/15 の時点で既に結果を得ていた」とのメールがあった。 | ||||||||||||||
14. Bernoulli数
|
Bernoulli数の定義は以下のとおり。
1998/11/25 に、Dr. Samuel S. Wagstaff Jr. より、 「1996/01/10 の時点で既に結果を得ていた」とのメールがあった。 | ||||||||||||||
15. 楕円モジュラー関数 j(τ) のフーリエ展開の係数 |
j(τ) は楕円モジュラー関数。
| ||||||||||||||
16. 分割数
|
ある数を、正の整数の和として表す個数を分割数と呼ぶ。 100桁以上のいくつかの数は、RSA Factoring Challenge の対象となっている。 | ||||||||||||||
17. 円分数 |
n と x を自然数としたとき、円分多項式 Φn(X) の X = x における値 N = Φn(x) を「円分数」と呼ぶ。 円分数の素因数分解プロジェクトは、1984年、 森本光生教授 (上智大 (現 国際基督教大))により始められた。 φ(n) ≦ 100, 2 ≦ x ≦ 1000の範囲の完全分解を目標としている。 円分数の計算方法はこちら。 関連リンク Factorization of Cyclotomic Numbers | ||||||||||||||
18. 各種定数の10進展開
|
Pi = 3.14159265358979323846 ... e = 2.71828182845904523536 ... Euler gamma = 0.57721566490153286060 ... | ||||||||||||||
19. Smarandache 連続数
|
"Smarandache consecutive sequences" とは、連続するn個の自然数のことである。 例えば、Sm(11)=1234567891011, and RSm(11)=1110987654321. 素因数分解の最新状況は、下記のWebサイトで管理されている。 SMARANDACHE FACTORS AND REVERSE FACTORS下記のような、Smrandache 表記のヴァリエーションを考えることができる。
素数の Smarandache notation の結果は、Robert G. Wilson, V. による。 |
12章 素因数分解 アルゴリズム |
数学者の密室 目次 |
Appendix 2. 参考文献 |
---|---|---|
Chapter 12. Factorization Algorithms (English version) |
"Mathematician's Secret Room" overview (English version) | Appendix 2. Bibliography (Japanese version) |