Incubator escapee wiki

Cunningham Project

Article Discussion

Template:Short description The Cunningham Project is a collaborative effort started in 1925 to factor numbers of the form bn ± 1 for b = 2, 3, 5, 6, 7, 10, 11, 12 and large n. The project is named after Allan Joseph Champneys Cunningham, who published the first version of the table together with Herbert J. Woodall.<ref>Template:Cite book</ref> There are three printed versions of the table, the most recent published in 2002,<ref>Template:Cite book</ref> as well as an online version by Samuel Wagstaff.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>

The current limits of the exponents are:

Base 2 3 5 6 7 10 11 12
Limit 1500 900 600 550 500 450 400 400
Aurifeuillean (LM) limit 3000 1800 1200 1100 1000 900 800 800

Factors of Cunningham numberEdit

Two types of factors can be derived from a Cunningham number without having to use a factorization algorithm: algebraic factors of binomial numbers (e.g. difference of two squares and sum of two cubes), which depend on the exponent, and aurifeuillean factors, which depend on both the base and the exponent.

Algebraic factorsEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} From elementary algebra,

<math>(b^{kn}-1) = (b^n-1) \sum_{r=0}^{k-1} b^{rn}</math>

for all k, and

<math>(b^{kn}+1) = (b^n+1) \sum_{r=0}^{k-1} (-1)^r \cdot b^{rn}</math>

for odd k. In addition, Template:Math. Thus, when m divides n, Template:Math and Template:Math are factors of Template:Math if the quotient of n over m is even; only the first number is a factor if the quotient is odd. Template:Math is a factor of Template:Math, if m divides n and the quotient is odd.

In fact,

<math>b^n-1 = \prod_{d \mid n} \Phi_d(b)</math>

and

<math>b^n+1 = \prod_{d \mid 2n,\, d \nmid n} \Phi_d(b)</math>

See this page for more information.

Aurifeuillean factorsEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} When the number is of a particular form (the exact expression varies with the base), aurifeuillean factorization may be used, which gives a product of two or three numbers. The following equations give aurifeuillean factors for the Cunningham project bases as a product of F, L and M:<ref>{{#invoke:citation/CS1|citation |CitationClass=web }} At the end of tables 2LM, 3+, 5-, 6+, 7+, 10+, 11+ and 12+ there are formulae detailing the aurifeuillean factorizations.</ref>

Let b = s2Template:Timesk with squarefree k, if one of the conditions holds, then <math>\Phi_n(b)</math> have aurifeuillean factorization.

(i) <math>k\equiv 1 \pmod 4</math> and <math>n\equiv k \pmod{2k};</math>
(ii) <math>k\equiv 2, 3 \pmod 4</math> and <math>n\equiv 2k \pmod{4k}.</math>

Template:Table alignment

b Number F L M Other definitions
2 24k+2 + 1 1 22Template:Itco+1 − 2Template:Itco+1 + 1 22Template:Itco+1 + 2Template:Itco+1 + 1
3 36k+3 + 1 32Template:Itco+1 + 1 32Template:Itco+1 − 3Template:Itco+1 + 1 32Template:Itco+1 + 3Template:Itco+1 + 1
5 510k+5 − 1 52Template:Itco+1 − 1 Template:Itco2 − 5Template:Itco+1T + 52Template:Itco+1 Template:Itco2 + 5Template:Itco+1T + 52Template:Itco+1 T = 52Template:Itco+1 + 1
6 612k+6 + 1 64k+2 + 1 Template:Itco2 − 6Template:Itco+1T + 62Template:Itco+1 Template:Itco2 + 6Template:Itco+1T + 62Template:Itco+1 T = 62Template:Itco+1 + 1
7 714k+7 + 1 72Template:Itco+1 + 1 A − B A + B A = 76k+3 + 3(74k+2) + 3(72Template:Itco+1) + 1
B = 75k+3 + 73k+2 + 7Template:Itco+1
10 1020Template:Itco+10 + 1 104k+2 + 1 A − B A + B A = 108k+4 + 5(106k+3) + 7(104k+2) + 5(102Template:Itco+1) + 1
B = 107k+4 + 2(105k+3) + 2(103k+2) + 10Template:Itco+1
11 1122Template:Itco+11 + 1 112Template:Itco+1 + 1 A − B A + B A = 1110k+5 + 5(118k+4) − 116k+3 − 114k+2 + 5(112Template:Itco+1) + 1
B = 119k+5 + 117k+4 − 115k+3 + 113k+2 + 11Template:Itco+1
12 126k+3 + 1 122Template:Itco+1 + 1 122Template:Itco+1 − 6(12k) + 1 122Template:Itco+1 + 6(12k) + 1

Other factorsEdit

Once the algebraic and aurifeuillean factors are removed, the other factors of Template:Math are always of the form Template:Math, since the factors of Template:Math are all factors of <math>\Phi_n(b)</math>, and the factors of Template:Math are all factors of <math>\Phi_{2n}(b)</math>. When n is prime, both algebraic and aurifeuillean factors are not possible, except the trivial factors (Template:Math for Template:Math and Template:Math for Template:Math). For Mersenne numbers, the trivial factors are not possible for Template:Nowrap, so all factors are of the form Template:Math. In general, all factors of Template:Math are of the form Template:Math where Template:Math and n is prime, except when n divides Template:Math, in which case Template:Math is divisible by n itself.

Cunningham numbers of the form Template:Math can only be prime if b = 2 and n is prime, assuming that n ≥ 2; these are the Mersenne numbers. Numbers of the form Template:Math can only be prime if b is even and n is a power of 2, again assuming Template:Math these are the generalized Fermat numbers, which are Fermat numbers when b = 2. Any factor of a Fermat number Template:Math is of the form Template:Math.

NotationEdit

bn − 1 is denoted as b,n−. Similarly, bn + 1 is denoted as b,n+. When dealing with numbers of the form required for aurifeuillean factorization, b,nL and b,nM are used to denote L and M in the products above.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> References to b,n− and b,n+ are to the number with all algebraic and aurifeuillean factors removed. For example, Mersenne numbers are of the form 2,n− and Fermat numbers are of the form 2,2n+; the number Aurifeuille factored in 1871 was the product of 2,58L and 2,58M.

See alsoEdit

ReferencesEdit

Template:Reflist

External linksEdit

Retrieved from "https://zalansite.site/mediawiki/index.php?title=Cunningham_Project&oldid=867640"