Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3). |
Topics | Help • Register • News • History • How to • Sequences statistics • Template prototypes |
Difference between revisions of "Cunningham project"
(infobox projects) |
(update date & link for main tables) |
||
(6 intermediate revisions by 3 users not shown) | |||
Line 6: | Line 6: | ||
At this moment three editions of the book about the Cunningham project have been published. | At this moment three editions of the book about the Cunningham project have been published. | ||
− | Current limits of the exponents of the Cunningham tables are: | + | Current limits (as of 2024-05-23, see [https://homes.cerias.purdue.edu/~ssw/cun/pmain524.txt The Cunningham Project (main tables)]) of the exponents of the Cunningham tables are: |
− | {| | + | {| class="wikitable" |
− | + | ! Base | |
+ | | 2 || 3 || 5 || 6 || 7 || 10 || 11 || 12 | ||
|- | |- | ||
− | | | + | ! Limit |
+ | | 1500 || 900 || 600 || 550 || 500 || 450 || 400 || 400 | ||
|} | |} | ||
Line 29: | Line 31: | ||
==Aurifeuillian factorizations== | ==Aurifeuillian factorizations== | ||
− | Consider the identity | + | Consider the identity (<math>h = 2k-1</math>) |
− | :<math>2^{2h}+1 = L.M</math> where <math>L = 2^h-2^k+1,\ M = 2^h+2^k+ | + | :<math>2^{2h}+1 = L.M</math> where <math>L = 2^h-2^k+1,\ M = 2^h+2^k+1</math> |
This factorization was discovered for one value by Aurifeuille and the general form was subsequently given by Lucas. Here are the Aurifeuillian factorizations for the other bases. | This factorization was discovered for one value by Aurifeuille and the general form was subsequently given by Lucas. Here are the Aurifeuillian factorizations for the other bases. | ||
− | :<math>3^{3h} + 1 = (3^h + 1).L.M</math> where <math>L = 3^h - 3^k + 1 | + | :<math>3^{3h} + 1 = (3^h + 1).L.M</math> where |
− | :<math>5^{5h} - 1 = (5h - 1).L.M</math> where <math>L = T^2 - T.5^k + 5^h | + | ::<math>L = 3^h - 3^k + 1</math> |
− | :<math>6^{6h} + 1 = (6^{2h} + 1).L.M</math> where <math>L = T^2 - T.6^k + 6^h | + | ::<math>M = 3^h + 3^k + 1</math> |
− | :<math>7^{7h} + 1 = (7^h + 1).L.M</math> where <math>L = T^3 - B | + | <hr> |
− | :<math>10^{10h} + 1 = (10^{2h} + 1).L.M</math> where <math>L = A - B | + | :<math>5^{5h} - 1 = (5h - 1).L.M</math> where |
− | :<math>11^{11h} + 1 = (11^h + 1).L.M</math> where <math>L = A - B | + | ::<math>L = T^2 - T.5^k + 5^h</math> |
− | :<math>12^{3h} + 1 = (12^h + 1).L.M</math> where <math>L = 12^h - 2^h.3^k + 1 | + | ::<math>M = T^2 + T.5^k + 5^h</math> |
+ | :::<math>T = 5^h + 1</math> | ||
+ | <hr> | ||
+ | :<math>6^{6h} + 1 = (6^{2h} + 1).L.M</math> where | ||
+ | ::<math>L = T^2 - T.6^k + 6^h</math> | ||
+ | ::<math>M = T^2 + T.6^k + 6^h</math> | ||
+ | :::<math>T = 6^h + 1</math> | ||
+ | <hr> | ||
+ | :<math>7^{7h} + 1 = (7^h + 1).L.M</math> where | ||
+ | ::<math>L = T^3 - B</math> | ||
+ | ::<math>M = T^3 + B</math> | ||
+ | :::<math>T = 7^h + 1</math> | ||
+ | :::<math>B = 7^k(T^2 - 7^h)</math> | ||
+ | <hr> | ||
+ | :<math>10^{10h} + 1 = (10^{2h} + 1).L.M</math> where | ||
+ | ::<math>L = A - B</math> | ||
+ | ::<math>M = A + B</math> | ||
+ | :::<math>A = 10^{4h} + 5.10^{3h} + 7.10^{2h} + 5.10^h + 1</math> | ||
+ | :::<math>B = 10^k(10^{3h} + 2.10^{2h} + 2.10^h + 1)</math> | ||
+ | <hr> | ||
+ | :<math>11^{11h} + 1 = (11^h + 1).L.M</math> where | ||
+ | ::<math>L = A - B</math> | ||
+ | ::<math>M = A + B</math> | ||
+ | :::<math>A = 11^{5h} + 5.11^{4h} - 11^{3h} - 11^{2h} + 5.11^h + 1</math> | ||
+ | :::<math>B = 11^k(11^{4h} + 11^{3h} - 11^{2h} + 11^h + 1)</math> | ||
+ | <hr> | ||
+ | :<math>12^{3h} + 1 = (12^h + 1).L.M</math> where | ||
+ | ::<math>L = 12^h - 2^h.3^k + 1</math> | ||
+ | ::<math>M = 12^h + 2^h.3^k + 1</math> | ||
So, there exist an Aurifeuillian factorization for base <math>b</math> for any exponent of the form <math>b(2k-1)</math> for integral values of <math>k</math>. Note that the Aurifeuillian factorization of base 5 is on the negative side, while for the other bases 2, 3, 6, 7, 10, 11, 12 it is on the positive side. | So, there exist an Aurifeuillian factorization for base <math>b</math> for any exponent of the form <math>b(2k-1)</math> for integral values of <math>k</math>. Note that the Aurifeuillian factorization of base 5 is on the negative side, while for the other bases 2, 3, 6, 7, 10, 11, 12 it is on the positive side. | ||
Line 63: | Line 93: | ||
*[http://wwwmaths.anu.edu.au/~brent/factors.html Brent-Montgomery-te Riele table Web site] (extension to larger bases). | *[http://wwwmaths.anu.edu.au/~brent/factors.html Brent-Montgomery-te Riele table Web site] (extension to larger bases). | ||
*[http://www.mersenneforum.org/forumdisplay.php?f=51 Cunningham tables at MersenneForum] | *[http://www.mersenneforum.org/forumdisplay.php?f=51 Cunningham tables at MersenneForum] | ||
− | |||
*[[Wikipedia:Cunningham_project|Cunningham project]] | *[[Wikipedia:Cunningham_project|Cunningham project]] | ||
− | {{ | + | *[https://doi.org/10.1090/conm/022 Factorizations of b<sup>n</suP>±1, b=2, 3, 5, 6, 7, 10, 11, 12 Up to High Powers, second edition (includes PDF download link)] |
+ | *[https://www.mersenneforum.org/attachment.php?attachmentid=7727&d=1330555980 PDF of the third edition] | ||
+ | {{Navbox Projects}} | ||
[[Category:Cunningham project| ]] | [[Category:Cunningham project| ]] |
Latest revision as of 05:23, 7 June 2024
Contents
[hide]The aim of this project is to find the complete factorization of numbers of the form
The project started in 1925, when Allan Cunningham and Herbert Woodall published a book of tables about this subject. Many people contributed to it and it is considered the oldest continuously ongoing activity in computational number theory.
At this moment three editions of the book about the Cunningham project have been published.
Current limits (as of 2024-05-23, see The Cunningham Project (main tables)) of the exponents of the Cunningham tables are:
Base | 2 | 3 | 5 | 6 | 7 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|
Limit | 1500 | 900 | 600 | 550 | 500 | 450 | 400 | 400 |
Properties of Cunningham factors
In the Cunningham tables, we eliminate two types of factors before factoring the remaining cofactor. The first type is algebraic factor, which are derived from a lower exponent. The second type is aurifeuillian factor, in which the whole number can be split into two parts directly, for certain combination of values of
Algebraic factorizations
It is trivial from elementary algebra that
for any value of
only when
Also that,
.
Thus, it turns out that both
Aurifeuillian factorizations
Consider the identity (
where
This factorization was discovered for one value by Aurifeuille and the general form was subsequently given by Lucas. Here are the Aurifeuillian factorizations for the other bases.
where
where
where
where
where
where
where
So, there exist an Aurifeuillian factorization for base
Other factors
Once the algebraic and Aurifeuillian factors are removed, the other factors of
For Mersenne numbers of the form
Cunningham numbers of the form
Only the first five Fermat numbers, k = 0, 1, 2, 3, 4 corresponding to 3, 5, 17, 257 and 65537 are known to be prime. All Fermat numbers from k = 5 to k = 32 are known to be composite. Fermat numbers till k = 11 are fully factorized.
Does there exist any squares of primes that divide Mersenne numbers of the form
See also
External links
- Cunningham project Web site
- Brent-Montgomery-te Riele table Web site (extension to larger bases).
- Cunningham tables at MersenneForum
- Cunningham project
- Factorizations of bn±1, b=2, 3, 5, 6, 7, 10, 11, 12 Up to High Powers, second edition (includes PDF download link)
- PDF of the third edition
Ongoing |
|
Terminated |