Generalized Cullen and Woodall numbers

Cullen numbers are given by the expression n.2ⁿ + 1 and Woodall numbers by n.2ⁿ - 1. An obvious generalization is to replace the base "2" with another integer a. There doesn't seem to be a standard name for these numbers in the mathematical literature, so I've named them Generalized Cullen and Woodall numbers. More concisely, GC(a,n) represents n.aⁿ + 1 and GW(a,n) represents n.aⁿ - 1. Sometimes an even more abbreviated name turns out to be useful, and anywhere on these pages you see a,n+ it should be read as GC(a,n) and a,n- should be read as GW(a,n). The last notation is shamelessly stolen from the Cunningham project.

Over ten years ago, Joe McLean and I factored all the GC and GW numbers with bases up to 10 and indexes to 100. Of course, some of the smaller factors were already known before we rediscovered them, and we had the assistance of Arjen Lenstra with the hardest factorization, but it was substantially our own efforts. Since then, our attentions turned elsewhere, not least to the Cullen and Woodall numbers themselves.

I have now returned to the task of extending the GC and GW tables. I've added base 10, 11 and 12, again by analogy with the Cunningham tables. As the 2+ and 2- tables contain factors for indexes up to 1000, that was chosen as the cut-off for the other tables as well. Several thousand small factors were discovered before the tables were made publicly available in September 2000.

Mark Rodenkirch and Jo Yeong Uk each sent me a batch of algebraic factorizations into two composite cofactors. Some of these have now been further factored and the remaining factorizations from their contributions may be found here, together with my description of several classes of algebraic factorizations. I would like to learn of any classes that I may have missed and which would be useful to factor integers from the tables below. I am aware of several more classes, but they are not applicable to the ranges of a and n considered here.

Anyone who wishes to contribute to the factorization of Generalized Cullen and Woodall numbers is welcome to download the tables below. Alternatively, you may wish to download the entire list of composite cofactors. This list contains 12896 numbers, one per line, and is a little under 3 megabytes in gzipped format. For those wishing to factor with the SNFS algorithm, this table contains the a and n values sorted by SNFS-difficulty (defined here as log₁₀ (n.aⁿ) ) for those unfactored GC and GW numbers which have SNFS-difficulty under 200. There are 257 entries in this table.

Resulting factorizations should be reported to me and I'll record contributions in the current progress file. Earlier contributions for the periods 2000 Sep-Dec, 2001 Jan-Mar, Apr-Jun, Jul-Sep, Oct-Dec, 2002 Jan-Mar, Apr-Jun, Jul-Sep, Oct-Dec, 2003 Jan-Mar, Apr-Jun, Jul-Sep, Oct-Dec, 2004 Jan-Mar, Apr-Jun, Jul-Sep, Oct-Dec, 2005 Jan-Mar, Apr-Jun, Jul-Sep, Oct-Dec, 2006 Jan-Mar, Apr-Jun Jul-Sep, Oct-Dec and 2007 Jan-Mar, Apr-Jun Jul-Sep, Oct-Dec and 2008 Jan-Mar are also available.

All these tables will be updated at sporadic intervals. The last update took place on 10th May 2008. On 9th October 2005, I found a 50-digit factor of 4,325-.c119 with the P-1 algorithm, using GMP-ECM 6.0.1. This factor was then the 5th largest ever discovered by P-1. A run is in progress to cover all of the composites with P-1 to B1=1G.

Most Wanted Numbers:  There are no composites in any of these tables with fewer than 125 digits. On the other hand, there are 132 with at least 1000 digits. Rather than give a small list of MWNs, I suggest that a worthwhile approach would be to use ECM to reduce this total significantly, to use GNFS and/or SNFS to factor the smallest composites, or to run SNFS on the ones easiest by that algorithm. There are 27 entries which have SNFS difficulty under 170 digits and 34 composites under 130 digits.

Update: Despite the lines above, recent ECM runs may have left a few runts — composites with fewer than 125 digits. If any are to be found there, completing them would be good!

Thanks to everyone who has contributed factors to these tables. There are now a total of 16109 factors reported since September 2000. The numbers found by each contributor are as follows:

Back to home, Cullen and Woodall, or factorization pages.