Numbers b^n +/- (b-1)

Numbers bⁿ ±(b-1)

Updated July 4, 2006

Internal links:

General information
Factorization:
Primes and PRP's

General information

This page summarizes efforts to factorize or to prove primality of integers in the above mentioned form (b>2). In a sense, they are generalization of Meresenne numbers or the "other edge" of the Cunningham project. These numbers are quite smooth in a base b, since they can be written as:
bⁿ+(b-1)=10...0c bⁿ-(b-1)=cc...c1,
where c is a digit b-1 (in the base b).
Only a small part of software is written myself: pre-sieving, trial factoring for small primes, checking, and some management tools. Mainly, I use the well-known and widely-used software: PrimeFormGW, NewPGen, ECM-GMP, Primo, and ECPP. Some factorization have been done using Msieve, ppsiqs or GGNFS. If you are involved in factorization, you know this software. If not - please visit one of many prime pages, e.g. this maintained by Chris Caldwell.
Also some primility tests have been done with ECPP, Primo, and pfgw. Of course, at first PRP tests are perfomed.
Below you will find two sections: Factorization and Primes and PRP's. Each of them has three parts: Recent updates, Milestones and progress, and Links. Note that recent updates are only described there - full detalis may be found in appropriate files (see Links).

General rules

The aim is to factorize integers bⁿ±(b-1) with bⁿ no greater than 2¹⁰²⁴ (it means that, e.g. 4⁵¹²+3 is included). If there is known algebraic/Aurifeuillian factorization then this limit is applied to a larger part (e.g. to (9^3k-8)/(9^k-2) - the M part of 9ⁿ-8). Here is a table with these limits:

base	3	4	5	5-LM	5+LM	6	7	8	9	9M	10	10LM	11	12	13	14	15	16	17	17-LM	17-QRS	17-QRST
n max	646	512	441	882	880	396	364	341	323	483	308	616	296	285	276	268	262	256	250	500	500	1000

After each run of any factorization program composite cofactors with less than 256 bits (approx. 1.158*10⁷⁷) are factorized with Msieve or PPSIQS, so at any moment only composites larger than 2²⁵⁶ are in tables. [This remark concerns mainly GMP-ECM at early stages.]

Recent updates

In this place only general changes (e.g. adding a new series) will be announced. A table with recent factorizations is provided in a separate file. Results are included in this file if one of four conditions is satisfied:

A given number is completely factorized;
A factor of one of the most wanted number (with no known factors) has been found (changes in the first five holes will not be included);
A smaller factor has at least 25 digits (about 2⁸⁰) and factorization has not been done by the ECM;
In the case of any ECM program the lower limit is 30 (decimal) digits (about 100 bits) or B1 equal to at least 25e4.

These rules apply to published tables; it is assumed that the first results are published after GMP-ECM runs with B1=3e3 (15-digit factors), though a limit B1=11e3 is rather prefered (20 decimal digits or 64-bit factors). To eliminate as many as possible small factors number of curves is two or even three times larger than the minimal ones (i.e. up to 231 curves for B1=11e3) and, of course, P±1 tests are perfomed.
Updates in factorizations lead to updates in Composite cofactors; updates in the 100 largest ECM/QS/NFS factors and the Most wanted and holes are announced separately. See also Links & files.

July 2, 2006: 4997 (38.27% of 13056) numbers left; 127 (2.54% of them) composites without known factors.
June 29, 2006: I was absent for some days. Today's changes and results are in fact obtained during last five days.
June 23, 2006: All cofactors less than 2³⁵² were factorized (at this moment, such numbers may appear as results of new decompositions; they will be sent to Msieve as soon as possible);
June 22, 2006: 8000 numbers (61.27% out of 13056) were completely factorized.
June 21, 2006: Numbers 8ⁿ+7 were tested with B1=5e4;
June 20, 2006: Numbers 7ⁿ+6 were tested with B1=5e4;
June 18, 2006: Msieve started factorization of cofactors less than 2³⁶⁰ (approx. 2.35*10¹⁰⁸).
June 18, 2006: Numbers 5ⁿ-4 (n odd) were tested with B1=25e4;
June 18, 2006: 150 numbers without known factors;
June 17, 2006: Numbers 5ⁿ+4 (n not equal 4k) were tested with B1=25e4;
June 16, 2006: Numbers 10ⁿ+9 were tested with B1=5e4;
June 15, 2006: Numbers 11ⁿ-10 were tested with B1=5e4;
June 13, 2006: Numbers 12ⁿ+12 were tested with B1=5e4;
June 12, 2006: Numbers 12ⁿ-11 were tested with B1=5e4;
June 10, 2006: Numbers 15ⁿ-14 were tested with B1=5e4;
June 9, 2006: Numbers 13ⁿ-12 were tested with B1=5e4;
June 8, 2006: More than 60% numbers (7834 out of 13056) were completely factorized.
June 5, 2006: All cofactors less than 2³³⁶ were factorized.
June 4, 2006: Numbers 16ⁿ-15 were tested with B1=5e4;

Milestones and progress

Used programs and current bounds:

GMP-ECM 6.0.1: B1=5e4 (B1=11e3 done for all numbers);
Msieve 1.06: 2³⁶⁰, i.e. about 2.349*10¹⁰⁸;
GGNFS 0.77.1: numbers C120-C135 and the 'most wanted' below 10¹⁵⁰;

These are short notes only. For details (reservation) ask Wojtek Florek.

Series	Number of integers	Left to factorize		B1 done	Notes
Series	Number of integers	total	without known factors	B1 done	Notes
3ⁿ-2	646	217	7	1e6	Extension to n=646 in progress with B1=1e6
3ⁿ+2	646	211	3	1e6	Extension to n=646 in progress with B1=1e6
4ⁿ-3	512	182	8	25e4	Some numbers were tested with B1=1e6
4ⁿ+3	512	179	4	25e4	Some numbers were tested with B1=1e6
5ⁿ-4 (n odd)	221	81	5	25e4
5ⁿ-4 (n even, the L part)	441	157	2	25e4	In fact it is the series 5^k-2 for n=2k;
5ⁿ-4 (n even, the M part)	441	176	1	25e4	In fact it is the series 5^k+2 for n=2k;
5ⁿ+4 (not equal 4k)	331	122	0	25e4
5ⁿ+4 (n=4k, the L part)	220	86	1	5e4	The L part of 5^4k+4 is given as 5^2k+2-2*5^k; B1=25e4 in progress
5ⁿ+4 (n=4k, the M part)	220	80	0	5e4	The M part of 5^4k+4 is given as 5^2k+2+2*5^k; B1=25e4 in progress
6ⁿ-5	396	153	5	5e4	B1=25e4 in progress
6ⁿ+5	396	139	5	5e4	B1=25e4 in progress
7ⁿ-6	364	156	5	11e3	B1=5e4 in progress
7ⁿ+6	364	159	3	5e4
8ⁿ-7	341	125	1	11e3	B1=5e4 in progress
8ⁿ+7	341	157	3	11e3
9ⁿ-8 (n not equal 3k)	331	66	2	1e6
9ⁿ-8 (n=3k, the M part)	162	39	0	11e3	The M part of 9^3k-8 is given as 9^2k+2*9^k+4
9ⁿ+8 (n not equal 3k)	331	99	2	11e3
9ⁿ+8 (n=3k, the M part)	162	68	2	5e4	The M part of 9^3k+8 is given as 9^2k-2*9^k+4
10ⁿ-9 (n odd)	154	53	3	11e3
10ⁿ-9 (n even, the L part)	308	106	4	11e3	In fact it is the series 10^k-3 for n=2k
10ⁿ-9 (n even, the M part)	308	117	5	5e4	In fact it is the series 10^k+3 for n=2k; B1=25e4 in progress
10ⁿ+9	308	118	4	5e4
11ⁿ-10	296	124	2	5e4
11ⁿ+10	296	130	5	5e4
12ⁿ-11	285	123	5	5e4
12ⁿ+11	285	131	2	5e4
13ⁿ-12	276	119	5	5e4
13ⁿ+12	276	116	4	5e4
14ⁿ-13	268	123	0	5e4
14ⁿ+13	268	119	5	5e4
15ⁿ-14	262	108	5	5e4
15ⁿ+14	262	116	3	5e4
16ⁿ-15	256	115	0	5e4
16ⁿ+15	256	102	4	5e4
17ⁿ-16 (n odd)	125	51	3	5e4	B1=25e4 in progress
17ⁿ-16 (n=4k+2, the L part)	125	55	3	5e4	In fact it is the series 17^k-4 for n=4k+2
17ⁿ-16 (n=4k+2, the M part)	125	56	0	5e4	In fact it is the series 17^k+4 for n=4k+2
17ⁿ-16 (n=4k, the Q part)	188	54	0	5e4	In fact it is the series 17^k-2 for n=4k;
17ⁿ-16 (n=4k, the R part)	188	54	0	5e4	In fact it is the series 17^k+2 for n=4k
17ⁿ-16 (n=4k, the S part)	188	79	3	5e4	In fact it is the series 17^2k+4 for n=4k and 17^2k+2-2*17^k for n=8k
17ⁿ-16 (n=8k, the T part)	125	48	3	5e4	This part is equal to 17^2k+2+2*17^k for n=8k;
17ⁿ+16	250	107	1	5e4
TOTAL	13056	4975	125

This info is a bit out of date and "out of scope".

The largest prime number (included in factorization tables): 5⁴⁹⁴+4 (346 digits).
The largest prime factor found within this project: P415 - a factor of 7⁴⁹⁸-6. [Out of scope with new limits.]

Links & files

Links to text files containing some results:

General results
1. Recent factorizations (last month);
2. 100 largest prime factors found by ECM-GMP (the record: 43-digit factor of 3⁴⁰¹+2, the smallest: P34); July 3, 2006;
3. 100 factorizations done by Quadratic Sieve programs (the record: C113 by Msieve, the smallest: C102); July 4, 2006;
4. 100 factorizations done by Number Field Sieve programs (the record: C156, the smallest: C103); July 2, 2006;
5. Most wanted and (the first five) holes; (125 numbers with no known factors); July 4, 2006;
6. Composite numbers from all tables (4975 entries; 1.055MB); July 4, 2006.
Some results have been taken from M. Kamada's pages: 10^n+9 pages and 10^n-9 pages.
Links to results for specific bases b are collected in the following table. Its columns are:
1. A type of a series denoted as bs: b± denotes a series bⁿ±(b-1);
2. Factorization results; files fct_bp.txt or fct_bm.txt (b from the previous column; p="+", m="-", of course);
3. Prime cofactors from the previous table larger than 10³⁰; files prf_bp.txt or prf_bm.txt;
4. Composite cofactors composite cofactors from the table fct_bs.txt; files ccf_bp.txt or ccf_bm.txt.

Series	Factorization	Prime cofactors	Composite cofactors
3-	fct_3m	prf_3m	ccf_3m
3+	fct_3p	prf_3p	ccf_3p
4-	fct_4m	prf_4m	ccf_4m
4+	fct_4p	prf_4p	ccf_4p
5-	fct_5m	prf_5m	ccf_5m
5-LM	fct_5mLM	prf_5mLM	ccf_5mLM
5+	fct_5p	prf_5p	ccf_5p
5+LM	fct_5pLM	prf_5pLM	ccf_5pLM
6-	fct_6m	prf_6m	ccf_6m
6+	fct_6p	prf_6p	ccf_6p
7-	fct_7m	prf_7m	ccf_7m
7+	fct_7p	prf_7p	ccf_7p
8-	fct_8m	prf_8m	ccf_8m
8+	fct_8p	prf_8p	ccf_8p
9-	fct_9m	prf_9m	ccf_9m
9-M	fct_9mM	prf_9mM	ccf_9mM
9+	fct_9p	prf_9p	ccf_9p
9+M	fct_9pM	prf_9pM	ccf_9pM
10-	fct_10m	prf_10m	ccf_10m
10-LM	fct_10mLM	prf_10mLM	ccf_10mLM
10+	fct_10.	prf_10p	ccf_10p
11-	fct_11m	prf_11m	ccf_11m
11+	fct_11p	prf_11p	ccf_11p
12-	fct_12m	prf_12m	ccf_12m
12+	fct_12p	prf_12p	ccf_12p
13-	fct_13m	prf_13m	ccf_13m
13+	fct_13p	prf_13p	ccf_13p
14-	fct_14m	prf_14m	ccf_14m
14+	fct_14p	prf_14p	ccf_14p
15-	fct_15m	prf_15m	ccf_15m
15+	fct_15p	prf_15p	ccf_15p
16-	fct_16m	prf_16m	ccf_16m
16+	fct_16p	prf_16p	ccf_16p
17-	fct_17m	prf_17m	ccf_17m
17-LM	fct_17mLM	prf_17mLM	ccf_17mLM
17-QRS and 17-QRST	fct_17mQRS	prf_17mQRS	ccf_17mQRS
17+	fct_17p	prf_17p	ccf_17p

Primes and PRP's

Recent updates
Milestones and progress
Links & files
Factorization
Main menu

New verison of this part will ready soon (I hope).
All data concernig primes and PRP's in the form bⁿ±(b-1) have been moved to a file prp1.html (updated Dec 29, 2005). In this place only very important changes will be announced (e.g. adding a new series, very large primes and PRP's etc.).

Recent updates

Milestones and progress

November 28, 2005: PFGW12 showed that 5⁸⁷⁶⁰⁶+4 is a 61234-digit PRP's. As for today it is 85th PRP's in the list of PRP Records.

The largest prime (certified and verified; found by WsF) of this form (not included in factorization tables) is: 4⁸²³⁰-2 (4955 digits).
The largest prime (certified and verified; found by others) of this form (not included in factorization tables) is: 4⁷⁰⁵⁷-3 (4249 digits).

Links & files

Tables of primes and PRP's.

URL of this page http://perta.fizyka.amu.edu.pl/pnq/index.html
Updated July 4, 2006 by Wojciech Florek