Appendix 1. 素因数分解結果

(英語ページの方に最新の情報が反映されています)

概要

この頁では、いろいろな数についての素因数分解の結果を掲載している。

このプロジェクトは、1991年に開始し、NEC PC9801VX2 + 80386 (8MHz ボード) を使って
各種の数の100桁以下の数について完全分解することを目標としてスタートした。
使用したプログラムは、UBASICに添付されている素因数分解プログラム RHOX, ECMX, MPQSX である。
当初のターゲットは、primorial(素数の積)±1、n!±1、primorial±nextprime、Fibonacci数、Lucas数、
Cullen／Woodal(Riesel)数(n・2ⁿ±1)、Wolstenholme数１／２、An/!n/Kn (階乗の和)、Euler数、Bernoulli数
であった。

1997年にWebで公開して以来、多くの人が本プロジェクトに参加するようになった。
苫米地氏の factor.exe (ECM + PPMPQS)、Paul Zimmerman の GMP-ECM 等の新しいツールを用いて、
1998年８月27日には、100桁以下の全ての数の分解が完了した。

その後、100桁以上の数に対する結果が多くの人から寄せられてきたため、改めて、対象桁数を150桁前後に再設定し、
また新たな対象として、Wolstenholme数３／４、j(tau) (楕円モジュラー関数のフーリエ展開の係数)、分割数
を追加した。

現在、我々は250桁以下の完全分解を目標としているが、それ以前に、100桁以下の未解決数も数多く残っている。
より多くの人が協力してくれることを願う。

Progress Report

What's new / history / errata(2009)

Old log : 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 素因数分解結果レポート (1999/08/04 まで)

英語版のページ

分解結果

0. カニンガムプロジェクト

カニンガムプロジェクト : bⁿ +- 1

ⁿ

²⁵⁵

メルセンヌ数 : 2ⁿ-1

フェルマー数 : 2^2ⁿ+1

Repunits : (10ⁿ-1)/9 = 111...111

aba : aba...aba

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

#Pn + 1 (n = 1～110) (未完)

#Pn - 1 (n = 1～110) (未完)

"Primorial" とは、ｎ番目の素数までの積、即ち、

#Pn = p₁ * p₂ * ... * p_n

を意味する。
この名称は、"prime (素数)" と "factorial (階乗)" の合成語である。

#Pn + 1 は、「素数は無数にある」という定理の証明で使われる数である。
しかし、この数自体が素数かどうかは別問題である。

最新の結果は、以下のサイト、

ftp://sable.ox.ac.uk/pub/math/
ftp://ftp.cam.uk.eu.microsoft.com/pub/math/factors/

で管理されている。

2. n!±1

n! + 1 (n = 1～100) (分解完了)

n! - 1 (n = 1～100) (分解完了)

これらの数も、自明な素因子を持たない。
ただし、ｎが素数のときに限り、(n-1)!+1はｎで割り切れる。
（Wilson の定理）
最新の結果は、Paul Leyland のサイト、

ftp://ftp.cam.uk.eu.microsoft.com/pub/math/factors/

及び、Andrew Walker のサイト、

n!+- Factoring Status

で管理されている。結果は以下のとおり。

n! + 1 (n = 2～400)

n! - 1 (n = 3～400)

3. Compositorial +/- 1

Compositorial + 1 (n = 4 to 150)
(未完)
Compositorial - 1 (n = 4 to 150)
(未完)

"Compositorial" とは、ｎ以下の合成数の積を表す。
ｎの階乗に対し、Primorialがｎ以下の素数の積なので、相補的な関係にある。
以下のように記述されることがある。

n! / #Nn

この場合、#Nn はｎ以下の全ての素数の積を表す。
"Compositorial" という名称は、"composite" と "factorial" からの造語である。

これらの初期の結果は、Dr. Robert G. Wilson, V から寄せられた。

4. #Pn ± NextPrime

#Pn + NextPrime (n = 1～100) (未完)
#Pn - NextPrime (n = 1～100) (未完)

#Pn ± NextPrime は、以下のように定義する。

#Pn = p₁ * p₂ * ... * p_n ± p_n+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! + (n+1) (n = 1～130) (未完)
n! - (n+1) (n = 1～130) (未完)

n!±１が素数であるかどうかが自明でないのと同じ理由で、
これらの数が素数か否かも自明ではない。

6. Compositorial±Next Composite

Compositorial + Next (n = 4 to 150)
(未完)
Compositorial - Next (n = 4 to 150)
(未完)

以下の表を元に考えるなら、Compositorial±Next Composite
を考察対象に入れるのは、極めて自然な発想である。

	±１	±(次の数)
全ての数	n!±1	n!±(n+1)
全ての素数	#Pn±1	#Pn±next prime
全ての合成数	Compositorial±1	Compositorial±next composite

7. Fibonacci数

Fn (n = 1～100) (分解完了)
Fn (n = 101～200) (分解完了)
Fn (n = 201～300) (分解完了)
Fn (n = 301～400) (分解完了)
Fn (n = 401～480) (分解完了)

Fibonacci数は以下のように定義される。

F₀= 0
F₁= 1
F_n= F_n-1+ F_n-2(n≧2)

詳細についてはこちらを参照のこと。

最新の結果は、Blair Kelly が n = 0 ～ 9999 までの結果を管理しており、
以下のサイト、

Fibonacci and Lucas Factorizations

で公開されている。結果は以下のとおり。

Fn (n = 0 to 1000)
Fn (n = 3 to 9999 : 奇数)

8. Lucas数

Ln (n = 1～100) (分解完了)
Ln (n = 101～200) (分解完了)
Ln (n = 201～300) (分解完了)
Ln (n = 301～400) (分解完了)
Ln (n = 401～478) (分解完了)

Lucas数は以下のように定義される。

L₀= 2
L₁= 1
L_n= L_n-1+ L_n-2(n≧2)

詳細についてはこちらを参照のこと。

最新の結果は、Blair Kelly が n = 0 ～ 9999 までの結果を管理しており、
以下のサイト、

Fibonacci and Lucas Factorizations

で公開されている。結果は以下のとおり。

Ln (n = 0 to 1000)
Ln (n = 2 to 9999)

9. Cullen数

Cn (n = 1～100) (分解完了)
Cn (n = 101～200) (分解完了)
Cn (n = 201～300) (分解完了)
Cn (n = 301～323) (分解完了)

Cullen数は以下のように定義される。

Cn = n・2ⁿ+ 1

最新の結果は、以下のサイトで管理されている。

ftp://ftp.cam.uk.eu.microsoft.com/pub/math/factors/

結果は以下のとおり。

Cn (n = 1～1000)

10. Woodal（Riesel）数

Rn (n = 1～100) (分解完了)
Rn (n = 101～200) (分解完了)
Rn (n = 201～300) (分解完了)
Rn (n = 301～323) (分解完了)

Woodal（Riesel）数は以下のように定義される。

Rn = n・2ⁿ- 1

最新の結果は、以下のサイトで管理されている。

ftp://ftp.cam.uk.eu.microsoft.com/pub/math/factors/

結果は以下のとおり。

Rn (n = 1～1000)

11. Wolstenholme数

W3n (n = 1～100) (分解完了)
W3n (n = 101～200) (未完)

W4n (n = 1～100) (未完)
W4n (n = 101～150) (未完)

素数の逆数の部分和の分子 (n = 1～100) (未完)

Moeb(n)/n の部分和の分子 (n = 1 to 100) (分解完了)
Moeb(n)/n の部分和の分子 (n = 101 to 200) (分解完了)
Moeb(n)/n の部分和の分子 (n = 201 to 300) (分解完了)
Moeb(n)/n の部分和の分子 (n = 301 to 400) (未完)
Moeb(n)/n の部分和の分子 (n = 401 to 500) (未完)
Moeb(n)/n の部分和の分子 (n = 501 to 600) (未完)

1/i の 1 から m までの和
（ただし、gcd(i,m)=1）の分子
(n = 1 to 100) (分解完了)
1/i の 1 から m までの和の分子
(n = 101 to 200) (分解完了)
1/i の 1 から m までの和の分子
(n = 201 to 300) (分解完了)
1/i の 1 から m までの和の分子
(n = 301 to 400) (未完)
1/i の 1 から m までの和の分子
(n = 401 to 500) (未完)
1/i の 1 から m までの和の分子
(n = 501 to 600) (未完)

Wolstenholme の定理

以下の数、
1 + 1/2 + 1/3 + …… + 1/(p-1)
の分子は、ｐが素数の時に限り、p² で割り切れる。
また、
1 + 1/2² + 1/3² + …… + 1/(p-1)²
の分子は、ｐが素数の時に限り、ｐで割り切れる。

以下の数、
1 + 1/2³ + 1/3³ + …… + 1/(p-1)³
の分子は、ｐが素数かつｐ＞５の時に限り、p² で割り切れる。

以下の数、
1 + 1/2⁴ + 1/3⁴ + …… + 1/(p-1)⁴
の分子は、ｐが素数かつｐ＞７の時に限り、ｐで割り切れる。

この定理にちなみ、Σ(1/nⁱ) の分子の値を「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 (階乗の和)

An (n = 1～100) (分解完了)
An (n = 101～150) (未完)

!n (n = 1～100) (分解完了)
!n (n = 101～150) (未完)

Kn (n = 1～100) (分解完了)
Kn (n = 101～150) (未完)

これらの数は、Richard Guy『数論における未解決問題集』
の問題 B43, B44 で扱われている。定義は以下のとおり。

An = n! - (n-1)! + (n-2)! -+ …… -(-1)ⁿ
!n = 0! + 1! + 2! + …… + (n-1)!
Kn = 1! + 2! + …… + n!

13． Euler数

計算方法 (UBASIC program)

En (n = 0～78) (分解完了)
En (n = 80～106) (未完)

En (n = 10～200) (link)

Euler数の定義は以下のとおり。

En :	sec z	=	∞ Σ n=1	En ---- n!	zⁿ

Richard Guy『数論における未解決問題集』の B45で扱われている。
計算方法の詳細についてはこちらを参照のこと。

1998/11/25 に、Dr. Samuel S. Wagstaff Jr. より、
「1995/02/15 の時点で既に結果を得ていた」とのメールがあった。

14． Bernoulli数

計算方法 (UBASIC program)

Bn (n = 2～114) (分解完了)
Bn (n = 116～154) (未完)

Bn (n = 20～300) (link)

Bernoulli数の定義は以下のとおり。

Bn :	z ------- e^z－１	=	∞ Σ n=1	Bn ---- n!	zⁿ

計算方法の詳細についてはこちらを参照のこと。

1998/11/25 に、Dr. Samuel S. Wagstaff Jr. より、
「1996/01/10 の時点で既に結果を得ていた」とのメールがあった。

15. 楕円モジュラー関数 j(τ)
のフーリエ展開の係数

計算方法 (UBASIC program)

j(τ) (n = -1～100) (分解完了)
j(τ) (n = 101～200) (分解完了)
j(τ) (n = 201～300) (分解完了)
j(τ) (n = 301～400) (分解完了)
j(τ) (n = 401～500) (分解完了)
j(τ) (n = 501～600) (分解完了)
j(τ) (n = 601～700) (未完)
j(τ) (n = 701～800) (未完)
j(τ) (n = 801～900) (未完)
j(τ) (n = 901～1000) (未完)

j(τ) は楕円モジュラー関数。

j(τ) =

E₄(z)³
----------
Δ(z)

ここで、

E₄(z) = 1 + 240 *	∞ Σ n=1	s₃ (n) e ^2πinz
s₃ (n) は、ｎの約数の３乗の和
s₃ (n) =	Σ d\|n, d>=1	d³
Δ(z) = e ^2πiz	∞ Π n=1	( 1 - e ^2πinz) ²⁴

16．分割数

Pn (n = 0～1000) (分解完了)
Pn (n = 1001～2000) (分解完了)
Pn (n = 2001～3000) (分解完了)
Pn (n = 3001～4000) (分解完了)
Pn (n = 4001～5000) (分解完了)
Pn (n = 5001～6000) (分解完了)
Pn (n = 6001～7000) (分解完了)
Pn (n = 7001～8000) (分解完了)
Pn (n = 8001～9000) (分解完了)
Pn (n = 9001～10000) (分解完了)

Pn (n = 10001～30000) (未完)

ある数を、正の整数の和として表す個数を分割数と呼ぶ。
100桁以上のいくつかの数は、RSA Factoring Challenge の対象となっている。

17．円分数

48≦φ(n)≦70

n と x を自然数としたとき、円分多項式 Φn(X) の X = x における値
N = Φn(x) を「円分数」と呼ぶ。

円分数の素因数分解プロジェクトは、1984年、

森本光生教授 (上智大 (現国際基督教大))
木田祐司教授 (金沢大 (現立教大))

により始められた。

φ(n) ≦ 100, 2 ≦ x ≦ 1000

の範囲の完全分解を目標としている。

円分数の計算方法はこちら。 関連リンク

Factorization of Cyclotomic Numbers
(森本光生教授 (国際基督教大))
Factorization of Cyclotomic Numbers
(山崎愛一教授 (京都大))

18．各種定数の10進展開

Pi = 3.14159265358979323846 ...
e = 2.71828182845904523536 ...
Euler gamma = 0.57721566490153286060 ...

19. Smarandache 連続数

連続自然数 (n = 2 to 200)
(未完 : mirror)
連続自然数の逆順 (n = 2 to 200)
(未完 : mirror)

連続素数 (n = 1 to 100)
(未完)
連続素数の逆順 (n = 1 to 100)
(未完)

"Smarandache consecutive sequences"
とは、連続するｎ個の自然数のことである。
例えば、Sm(11)=1234567891011, and RSm(11)=1110987654321.
素因数分解の最新状況は、下記のWebサイトで管理されている。

SMARANDACHE FACTORS AND REVERSE FACTORS

下記のような、Smrandache 表記のヴァリエーションを考えることができる。

奇数、偶数
(Smarandache偶数)=2^n.(Smarandache奇数)
ではないことに注意
素数
２乗、３乗、ｎ乗
階乗、ｎ乗の階乗 (=n(n-2)(n-4)...)

及び、これらの逆順のパターン。
素数の Smarandache notation の結果は、Robert G. Wilson, V. による。

History of updates

2002/02/26 : データの探査範囲を250桁前後まで拡張した。対象データは、
Wol1, Wol2, Wol3, Wol4, An, !n, Kn

2002/02/28 : 下記のデータを新たな探査対象として加えた。
n! +/- next n, Compositorial（合成数の積） +/- next composite, 素数の逆数の和の分子。

2003/05/12 : 下記のデータを新たな探査対象として加えた。
pi(円周率), e(自然対数の底), γ : Euler gamma(オイラーの定数)、Smarandache 連続数。

2003/06/15 : 下記のデータを新たな探査対象として加えた。
Smarandache 連続数（100まで）と逆順。log 2 の部分和の分子、Moeb(n)/n の部分和の分子。

2004/08/18 : 下記のデータを新たな探査対象として加えた。
1/i の 1 から m までの和（ただし、gcd(i,m)=1）の分子。

2004/08/24 : 下記のデータを新たな探査対象として加えた。
aba(a,b,n) = aba...aba = "ab" の n 回繰り返しに a を付加した数。

12章　素因数分解アルゴリズム	数学者の密室目次	Appendix 2. 参考文献
Chapter 12. Factorization Algorithms (English version)	"Mathematician's Secret Room" overview (English version)	Appendix 2. Bibliography (Japanese version)

E-mail : kc2h-msm@asahi-net.or.jp

三島　久典