Factorisation Tables

 

My primary interest in computational number theory for many years has been searching for certain types of prime, and more recently for probable primes as well. However, I have always retained an interest in factorisation, ever since reading articles about the early attempts at using computers to find factors of Mersenne numbers, most of which were published in the Mathematics of Computation. I even managed, at one time, to produce a published article myself, co-written with Paul Leyland, about our factoring of number of the form n*xn ± 1, with x running from 2 to 10. These numbers are now referred to as generalised Cunningham-Woodall numbers, and Paul, amongst others, has extended the tables for these substantially since those days.

 

There are many other co-ordinated factoring projects ongoing at present. Principal amongst these is the Cunningham project, which aims to extend the complete factorisation of Mersenne numbers. Other tables being worked on include factorisations of factorials, multifactorials and primorials. However, there are several number forms that are not the focus of any project as far as I am aware, but are of interest to me, and these I present here.

 

The format of the factorisation tables included here is as follows:

 

They are all standard text documents.

Header lines describe the form of the number, and include any restrictions or abbreviations. For instance, it will sometimes be the case that n will be restricted to odd values. It might also be the case that certain small factors are not included in the tables because their existence is guaranteed, or will cause unnecessary clutter .

There are two columns, consisting of n, and the factorisation of f(n), whatever this may be as defined in the header lines.

The factorisation consists of a set of fields separated by full-stops. These fields are either primes, primes to a power (identified by ^ ), or a short piece of text.

Text items can be of the form:

 

 “primexxx” if a large co-prime has been identified, with xxx being the decimal length

“Primexxx” if the whole of f(n) (after possible removal of default small divisors) is prime

“Cxxx” if the co-factor of f(n) is composite of decimal length xxx

 

Additionally, in cases where the entire factorisation is given explicitly, the largest prime factor may be followed by “(Pxx)” to indicate its size, or by “(prime)” if the whole of f(n) is prime.

 

One point to note is that there are quite a lot of tables listed below, and I am only one person with a couple of PCs available. I would be delighted if anyone else could contribute. All such contributions would be gratefully received and fully credited. However, I would not want to take any major processing effort away from any major projects.

 

 

Firstly, and vaguely connected to the Cunningham-Woodall numbers are numbers of the form 2n ± n. Although some work has been done elsewhere in locating primes and probable primes of this form, there is no, as far as I can tell, organised factorisation project. Large primes and probable primes of this form are described in a related article.

 

Next, as a companion to the primorials, are the compositorials, that is, numbers of the form (n! / n#) ± 1. My tables run to n = 1000 for no particular reason, although little work has been done at the top end of this range.

 

The next form is more unusual, that of the factoprimorial. These take the form n! ± n# ± 1.  Primality and probable primality of these has been considered by various researchers, but there is no other extant work. The reasoning behind these numbers is that, similar to factorials and primorials, there is an in-built sieve, increasing the chances of primality. Again, these tables also run up to n = 1000. Primes and probable primes of this form are listed in the same related article.

 

Lastly, I consider numbers of the form n!m ± d, for gcd (d,m) > 1, d £ m, known as multifactorials, with exponent m and offset d. Again, these numbers have a built-in sieve that makes them a lucrative source of large probable primes. I restrict m from 2 to 6, but include the cases d = 1 for completeness. One of the downsides of these numbers is that as m increases, the rate of increase in digit length decreases, meaning that there are a lot more numbers of a certain length that require to be factored.

 

The tools I use include Yuji Kida’s implementations of ECM & MPQS for Ultrabasic, a simple Pollard’s (p-1)-method implementation by myself using Ultrabasic, GMP-ECM from Paul Zimmerman (currently version 6.3), and PPSIQS (version 1.0) from Tomabechi Satoshi. GMP-ECM is executed in an iterative mode using DOS batch programming. A list of files, each file containing a single number to be factored, is fed into the batch program that executes GMP-ECM once for each file in the list and then repeats until terminated. Files of numbers are usually between 6 and 12, though for lower B1 values, larger sets of files are often used.

 

As I have said, any help in filling the many gaps, or extending the tables, would be appreciated. I would also be interested to hear of any other types of regularly rising number forms that may be worth adding to the above list.

 

Statistical Report

 

History

 

13/10/2007 – tables first published on-line, although work has been done off and on for many years.

 

15/04/2008 – first comprehensive review of tables.  This includes a more consistent presentation allowing the development of a validation program in Ultrabasic. This results in extensive error-correcting. I also extend some of the tables slightly so that the ranges being searched are broadly of the same scope. I also develop a couple of convenient DOS scripts to allow use of GMP-ECM over large sets of numbers rather than being restricted to one number at a time. I take this opportunity to produce the first statistical report. For this purpose I restrict the searches to reasonable ranges on the factoprimorial and compositorial tables. At this point there are 1182 large composites in the search range, the smallest with a decimal expansion of 83 digits, the largest with a decimal digit count of 153.

 

10/10/2008 – As well as completing a period of intense factoring, using GMP-ECM with an initial B1 value up to 450000 on all tables, I have taken the opportunity to add two more forms, namely 2n + n2 and 2n – n2, which appeal because of their symmetry.  These numbers seem to offer less chance of providing large primes, with a surprisingly common feature being collapse into large numbers of factors. This may well be worth investigating independently. Even with an increase in the overall search base, the number of cofactors with less than 150 decimal digits has decreased to 1068.

 

14/05/2009 – GMP-ECM run up to a B1 value of 550000 for all tables, and complete factorisation using PPSIQS of all numbers with less than 86 digits. There are now 937 cofactors remaining.

 

02/10/2009 − GMP-ECM run up to a B1 value of 600000 for all tables, and complete factorisation using PPSIQS of all numbers with less than 87 digits. There are now 889 cofactors remaining.

 

09/08/2010 − GMP-ECM run up to a B1 value of 750000 for all tables, and complete factorisation using PPSIQS of all numbers with less than 89 digits. There are now 817 cofactors remaining. Very few factors are now being discovered using ECM, so I will be aiming for longer running times.

 

02/12/2010 − GMP-ECM run up to a B1 value of 800000 for all tables, with more iterations. Complete factorisation using PPSIQS of all numbers with less than 90 digits and some with 90 digits. There are now 744 cofactors remaining. Since very few factors are being discovered using ECM, I will be increasing the number of iterations.

 

01/05/2013 - Begin first table extension in several years, of numbers of the form 2n±n and 2n±n2, extended from n = 460 to n = 500.

 

18/05/2013 - First 99-digit number 247!5−1 factorised using NFS (see next update for details).

 

28/05/2013 – After an overdue gap in reporting, I have now performed GMP-ECM with a B1 value of 1000000 for all entries with greater than 100 digits, use of PPSIQS to factor all numbers up to 90 digits. I have now begun using YAFU to aid with large factorisations, which uses SIQS or NFS algorithms as appropriate, for a large number of factors between 92 and 99 digits, including my first NFS factorisations. There are now 682 cofactors remaining, incorporating 75 new cofactors from extended tables, but this figure is dropping quickly due to YAFU.

 

29/07/2013 - Begin additional extension of all exponent-6 multifactorials, extended from n = 380 to n = 400.

 

21/11/2013 - On this date, the last remaining C92 was factored using PPSIQS.

 

24/12/2013 - Last 98- & 99-digit cofactors factorised using NFS. Heavy use of ECM against larger cofactors. All new cofactors, after ECM successes, of less than 100 digits also factored. With the extended tables now at the same level as the rest, totals are:

 

C100-C109 - 167

C110-C119 - 141

C120-C129 - 106

C130-C139 - 56

C140-C149 - 12

 

This combines to leave 482 cofactors outstanding. These figures do not include the table extensions.

 

20/01/2015 - GMP-ECM still being run for larger cofactors with B1 value of 2000000,  while extensive use of YAFU-NFS has been used to remove smaller number. Currently no cofactor with less than 104 digits remaining.

 

C101-C109 - 79

C110-C119 -  144 (resulting from factors found in larger cofactors)

C120-C129 - 106

C130-C139 - 67

C140-C149 - 22

 

This leaves 418 cofactors, including all current table extensions. It

 

 

Factorisation table for 2n + n for n initially up to 430, extended to 460, further to 500, complete up to 406, cofactors remaining 23

 

Factorisation table for 2n - n for n initially up to 440, extended to 460, further to 500, complete up to 340, cofactors remaining 16

 

 

Factorisation table for 2n + q for n initially up to 460, extended to 500, complete up to 392, cofactors remaining 17

 

Factorisation table for 2n - q for n initially up to 460, extended to 500, complete up to 408, cofactors remaining 18

 

 

 

Factorisation table of (n!/n#) + 1 for n up to 1000, reduced to 120, complete up to 97, cofactors remaining 3

 

Factorisation table of (n!/n#) - 1 for n up to 1000, reduced to 120, complete up to 99, cofactors remaining 3

 

 

 

Factorisation table of n! + n# + 1 for n up to 1000, reduced to 100, complete up to 79, cofactors remaining 3

 

Factorisation table of n! + n# - 1 for n up to 1000, reduced to 100, complete up to 83, cofactors remaining 3

 

Factorisation table of n! - n# + 1 for n up to 1000, reduced to 100, complete up to 80, cofactors remaining 8

 

Factorisation table of n! - n# - 1 for n up to 1000, reduced to 100, complete up to 82, cofactors remaining 6

 

 

 

Factorisation table of n!2 + 1 for n up to 156, extended to 160, complete up to 129, cofactors remaining 6

 

Factorisation table of n!2 - 1 for n up to 150, extended to 160, complete up to 140, cofactors remaining 4

 

Factorisation table of n!2 + 2 for n up to 150, extended to 160, complete up to 133, cofactors remaining 7

 

Factorisation table of n!2 - 2 for n up to 150, extended to 160, complete up to 127, cofactors remaining 5

 

Factorisation table of n!2 + 4 for n up to 150, extended to 160, complete up to 136, cofactors remaining 4

 

Factorisation table of n!2 − 4 for n up to 150, extended to 160, complete up to 146, cofactors remaining 8

 

Factorisation table of n!2 + 8 for n up to 150, extended to 160, complete up to 144, cofactors remaining 6

 

Factorisation table of n!2 − 8 for n up to 150, extended to 160, complete up to 133, cofactors remaining 4

 

Factorisation table of n!2 + 2n for n up to 150, extended to 165, complete up to 130, cofactors remaining 5

 

Factorisation table of n!2 − 2n for n up to 150, extended to 165, complete up to 152, cofactors remaining 2

 

 

 

 

Factorisation table of n!3 + 1 for n up to 215, extended to 220, complete up to 191, cofactors remaining 5

 

Factorisation table of n!3 - 1 for n up to 215, extended to 220, complete up to 194, cofactors remaining 4

 

Factorisation table of n!3 + 3 for n up to 215, extended to 220, complete up to 191, cofactors remaining 7

 

Factorisation table of n!3 - 3 for n up to 215, extended to 220, complete up to 181, cofactors remaining 9

 

 

Factorisation table of n!4 + 1 for n up to 275, complete up to 220, cofactors remaining 7

 

Factorisation table of n!4 - 1 for n up to 275, complete up to 234, cofactors remaining 8

 

Factorisation table of n!4 + 2 for n up to 275, complete up to 239, cofactors remaining 6

 

Factorisation table of n!4 - 2 for n up to 275, complete up to 229, cofactors remaining 8

 

Factorisation table of n!4 + 4 for n up to 275, complete up to 237, cofactors remaining 8

 

Factorisation table of n!4 - 4 for n up to 275, complete up to 239, cofactors remaining 4

 

 

Factorisation table of n!5 + 1 for n up to 325, extended to 340, complete up to 278, cofactors remaining 16

 

Factorisation table of n!5 - 1 for n up to 325, extended to 340, complete up to 267, cofactors remaining 16

 

Factorisation table of n!5 + 5 for n up to 325, extended to 340, complete up to 280, cofactors remaining 6

 

Factorisation table of n!5 - 5 for n up to 325, extended to 340, complete up to 271, cofactors remaining 12

 

 

Factorisation table of n!6 + 1 for n up to 300, extended to 380, complete up to 313, cofactors remaining 11

 

Factorisation table of n!6 - 1 for n up to 300, extended to 380, complete up to 328, cofactors remaining 10

 

Factorisation table of n!6 + 2 for n up to 350, extended to 380, complete up to 316, cofactors remaining 15

 

Factorisation table of n!6 - 2 for n up to 302, extended to 380, complete up to 322, cofactors remaining 13

 

Factorisation table of n!6 + 3 for n up to 300, extended to 380, complete up to 306, cofactors remaining 11

 

Factorisation table of n!6 - 3 for n up to 315, extended to 380, complete up to 309, cofactors remaining 13

 

Factorisation table of n!6 + 4 for n up to 300, extended to 380, complete up to 313, cofactors remaining 17

 

Factorisation table of n!6 - 4 for n up to 332, extended to 380, complete up to 333, cofactors remaining 15

 

Factorisation table of n!6 + 6 for n up to 335, extended to 380, complete up to 323, cofactors remaining 17

 

Factorisation table of n!6 - 6 for n up to 325, extended to 380, complete up to 320, cofactors remaining 20

 

Last updated: 20/01/2015