WIFC (World Integer Factorization Center)

(Old title : Appendix 1. Factorization results) [Japanese]

since August 04, 1997 Counter - 2,000

Abstract

These are factorization results of various kind of numbers.

I started this project (factorize various numbers under 100 digits) on 1991 using 80286 PC with 80386 (8 MHz) board. Used tools were UBASIC's factorization program (RHO, ECMX, MPQSX). Target numbers are, primorial±1 (products of prime), factorial±1 (n!±1), primorial±next prime, Fibonacci and Lucas numbers, Cullen and Woodall numbers, Wolstenholme numbers 1, 2 (numerator of Σ(1/ni)), An, !n, Kn (sums of factorials), Euler and Bernoulli numbers.

I opened these results on my personal Web site on 1997. Many people joined to this project. By using new tools such that S.Tomabechi's "factor (ECM + PPMPQS)", Paul Zimmermann's ECM, under 100 digits numbers are completely factored on 27 Aug. 1998.

After finished to factor under 100 digits, several members reported further results over 100 digits, so I extended the search range up to 150 or certain digits, and added the new series of numbers, Wolstenholme numbers 3, 4 (numerator of Σ(1/ni)), fourier coefficients of j (τ) (elliptic modular function), partition numbers.

Now we are trying up to around 250 digits numbers.
I wish many contributors will join in.

Progress report

Factorization Results

0. The Cunningham Project

  • Cunningham Project : bn±1
    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 satisfies the constraint bn < 10255
    (Richard Brent)

  • Mersenne number : 2n-1

  • Fermat number : 22n+1

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

  • aba : aba...aba = ((10a+b)*10(2n+1)-(a+10b))/99
Related to
  A3 Mersenne primes. Repunits. Fermat numbers. Primes of shape k.2^n+1
Richard K. Guy, "Unsolved Problems in Number Theory" Third Edition

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

Related to
  A2 Primes connected with factorials

"Primorial" is the product of primes from 2 to n-th prime, i.e.
#Pn = p1 * p2 * ... * pn
named from "prime" and "factorial".
The number #Pn + 1 appears in the proof of the theorem that
there are infinite amounts of prime numbers.
But it is not apparent that these numbers are prime or not.

As for primarity testing, the results are maintained at Chris K. Caldwell's site,

Primorial and Factorial Primes
2. n!±1

 Related to
  A2 Primes connected with factorials

It is not obvious that these numbers can be factorized or not.
(n-1)!+1 can be divided by n if and only if n is prime.
(Wilson's Theorem).

The results up to 400 are maintained at Paul Leyland's site,

N!+1
N!-1

The current results up to 1000 are maintained at Andrew Walker's site,

N!±1 Factoring Status

As for primarity testing, the results are maintained at Chris K. Caldwell's site,

Primorial and Factorial Primes
3. Compositorial±1

"Compositorial" is the product of all composite numbers under n.
It is a kind of complement of Primorial.
Sometimes it is described as,

n! / #Nn

in this notation #Nn means the products of all primes under n.
It is named from "composite" and "factorial".

These initial results are owe to Robert G. Wilson, V.

4. #Pn±NextPrime

 #Pn±NextPrime is defined as,
p1 * p2 * ... * pn±pn+1
These numbers does not also have explicit factors
by the same reason to "1. #Pn (Primorial)±1".
That is,
if 2 * 3 * 5 * 7 + 1 (resp. - 1) is divided
by 2, 3, 5, 7,
1 (resp. -1) remains.
and
if 2 * 3 * 5 * 7 + 11 (resp. - 11) is divided
by 2, 3, 5, 7,
11 (resp. -11) remains.
The other number theoretic properties are unknown.
5. n!±Next n

 According to the same reason with the uncertainty of primarity of n!±1,
it is also not obvious that these numbers can be factorized or not.
6. Compositorial±Next Composite

It is natural to consider these numbers under the following table,

± 1± next term
All numbersn!±1n!±(n+1)
All primes#Pn±1#Pn±next prime
All compositesCompositorial±1Compositorial±next composite

7. Fibonacci Numbers

 Fibonacci number is defined as follows,
F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2 (if n≥2)
For more details go here (Japanese version).

Blair Kelly is maintaining the results of from n=0 to 9999
in the web site Fibonacci and Lucas Factorizations

Fn (n = 0 to 1000)
Fn (n = 3 to 9999:odd)
8. Lucas Numbers

 Lucas number is defined as follows,
L0 = 2
L1 = 1
Ln = Ln-1 + Ln-2 (if n≥2)
Fibonacci numbers and Lucas numbers are simultaneously defined
as Lucas sequences.
For more details go here (Japanese version).

Blair Kelly is maintaining the results of from n=0 to 9999
in the web site Fibonacci and Lucas Factorizations

Ln (n = 0 to 1000)
Ln (n = 2 to 9999)
9. Cullen Numbers

 Related to
  B20 Cullen and Woodall numbers

Cullen number is defined as

Cn = n.2n + 1

The current results are maintained at Paul Leyland's sites,

Cullen and Woodall numbers

The results of generalized form of Cullen numbers GC(a,n) = n.an + 1,
(a=3, 4, 5, 6, 7, 8, 9, 10, 11, 12) are also maintained at Paul Leyland's sites,

Generalized Cullen and Woodall numbers
10. Woodall (Riesel) Numbers

 Related to
  B20 Cullen and Woodall numbers

Woodall (Riesel) number is defined as

Rn = n.2n - 1

The current results are maintained at Paul Leyland's sites,

Cullen and Woodall numbers

The results of generalized form of Woodall numbers GW(a,n) = n.an - 1,
(a=3, 4, 5, 6, 7, 8, 9, 10, 11, 12) are also maintained at Paul Leyland's sites,

Generalized Cullen and Woodall numbers
11. Wolstenholme Numbers

Wol 1

Wol 2

Wol 3

Wol 4

Numerator of sum of 1/p

Numerator of partial sum of log2

Numerator of Σ (μ(n)/n)

Numerator of Σ(1/i) 1 to m,
where gcd(i,m)=1

Wolstenholme's theorem
  1. The numerator of

    1 + 1/2 + 1/3 + ... + 1/(p-1)
    is divisible by p2 if and only if p is a prime,
    and the numerator of

    1 + 1/22+ 1/32+ ... + 1/(p-1)2
    is divisible by p if and only if p is a prime.

  2. The numerator of

    1 + 1/23+ 1/33+ ... + 1/(p-1)3
    is divisible by p2 if and only if p is prime and p>5.

  3. The numerator of

    1 + 1/24+ 1/34+ ... + 1/(p-1)4
    is divisible by p if and only of p is prime and p>7.

According to these theorems, the numerator of Σ(1/pi)
is named as "Wolstenholme numbers".

Numerator of sum of 1/p
= 1/2 + 1/3 + 1/5 + ...

Numerator of partial sum of log2
= 1 - 1/2 + 1/3 - ...

Numerator of Σ (μ(n)/n)
1/1 + (-1/2) + (-1/3) + 0/4 + (-1/5) + 1/6 + ...

Numerator of Σ (1/i) 1 to m, where gcd(i,m)=1
appears in "A Friendly Introduction to Number Theory", Silverman.

12. An, !n, Kn (Sums of factorials)

An

!n

Kn

Related to
  B43 Alternating sums of factorials
  B44 Sums of factorials

The definitions are
An = n! - (n-1)! + (n-2)! - ... -(-1)n
!n = 0! + 1! + 2! + ... + (n-1)!
Kn = 1! + 2! + ... + n!
13. Euler Numbers

 Related to
  B45 Euler numbers

The definition is
En : sec z = ∞
Σ
n=1		 En
----
n!		 zn
These numbers are mentioned in
Richard Guy ,"Unsolved Problems in Number Thoery" B45.
How to compute is given here (Japanese version).

Nov. 25, 1998, I got an E-mail from Dr. Samuel S. Wagstaff, Jr.
telling me that he already had these results (Feb. 15, 1995).

Related link

Factors of Bernoulli and Euler numbers
(Samuel S. Wagstaff)
14. Bernoulli Numbers

 The definition is
Bn : z
-------
ez-1		 = ∞
Σ
n=1		 Bn
----
n!		 zn
How to compute are mentioned at here (Japanese version).

Nov. 25, 1998, I got an E-mail from Dr. Samuel S. Wagstaff, Jr.
telling me that he already had these results (January 10, 1996).

Related link

Factors of Bernoulli and Euler numbers
(Samuel S. Wagstaff)
15. Fourier Coefficients of j (τ)

 j (τ) is Elliptic modular function.
j (τ) =
E4(z)3
----------
Δ(z)
where
E4(z) = 1 + 240 *
∞
Σ
n=1
   s3(n) e2πinz
s3 (n) is the sum of the cube of the divisors of n, i.e.,
s3 (n) = Σd3
d|n
d≥1

Δ(z) = q
∞
Π
n=1
 ( 1 - qn) 24
where
q = e 2πiz
16. Partition Numbers

 A representation of n as a sum of positive integers is called partition.
Partition Number is the number of partitions of n.

Some numbers over 100 digits are the target of
RSA Factoring Challenge.

17. Cyclotomic Numbers

 Let Φn(X) be cyclotomic polynomials,
the value of Φn(X) at X=x is called as Cyclotomic number.

The project of factoring cyclotomic numbers was started in 1984
by Professor Mitsuo Morimoto (Sophia University)
and Professor Yuji Kida (Kanazawa University).
Now they are in International Christian University
and in Rikkyo University, respectively.
Their final objective is to factor completely the numbers
in the ranges of φ(n) ≤ 100, 2 ≤ x ≤ 1000

How to compute is given here(Japanese version).

Related link

Factorization of Cyclotomic Numbers
(Prof. Mitsuo Morimoto : International Christian Univ.)
Factorization of Cyclotomic Numbers
(Prof. Aiichi Yamasaki : Kyoto Univ.)
18. Decimal expansion of Mathematical constants
  • π = 3.14159265358979323846 ...
  • e = 2.71828182845904523536 ...
  • Euler γ = 0.57721566490153286060 ...
19. Smarandache consecutive sequences

"Smarandache consecutive sequences"
is the nth member of the consecutive sequence,
e. g. Sm(11)=1234567891011, and RSm(11)=1110987654321.
Current factorization status is maintained in the following Web site.

SMARANDACHE FACTORS AND REVERSE FACTORS

We may consider any other variations of Smrandache notation, such as;

  • Odd number, Even number
  • Prime
  • Square, cube, nth power
  • Factorial, nth factorial

and reverse of all of those.
Dr. Robert G. Wilson, V. provided the results for prime version.

History

Powerful factorization tools programmed by Satoshi Tomabechi

Mint
(Multi-precision integer library)

Mint for Linux (588 KB)
(Dec. 27, 2001)
Mint for Windows (536 KB)
(Dec. 27, 2001)
 "Mint" is a library for computing multi-precision integer.
It is consisted of header files for representing multi digits numbers and
many number theoretic functions.
Especially, it includes the source files of PPSIQS and PPMPQS.
I'm convinced that this will help many programmers
who try to write effective factoring tools.
PPSIQS

Ver. 1.1 for Linux (188 KB)
(Dec. 17, 2001)
Ver. 1.1 for Windows (190 KB)
(Nov. 09, 2001) 		PPSIQS is the double large primes procedure variation of the self-intializing quadratic sieve.
In general, PPSIQS is faster than PPMPQS.

Reference
Scott Contini,"Factoring integers with the self-initializing quadratic sieve" ,
Masters thesis, University of Georgia, 1997
http://www.crypto-world.com
Performance report of PPSIQS
"PPSIQS Version 1.1 of Satoshi Tomabechi: Statistics for 60 Runs",
By Tom Hill (January 21, 2003)
PPMPQS

Ver. 2.8 for Linux (184 KB)
(Dec. 17, 2001)

Ver. 2.8 for Windows (185 KB)
(Jul. 14, 2001) 		If there remain composite numbers up to around 100 digits,
and you convince there are no factors which can be found by ECM,
then you should try to use this program.
The following documents are attached in the zip files.
Manual for Ver. 2.71
Average time of factorization using PPMPQS
factor Factorization program for general numbers.
It proceeds by rho (x2+1, x2-1, x2+3), p-1 and PPMPQS.
Usage is same as the following programs.
p-1 method p-1 method

Related links

Chapter 12
Factorization Algorithms		 "Mathematician's Secret Room" Appendix 2 Bibliography
Chapter 12 (Japanese) index (Japanese) Appendix 2 (Japanese)
E-mail : kc2h-msm@asahi-net.or.jp
Hisanori Mishima