Temporal logic: Difference between revisions

Revision as of 06:32, 16 November 2013

In mathematics, a Cunningham chain is a certain sequence of prime numbers. Cunningham chains are named after mathematician A. J. C. Cunningham. They are also called chains of nearly doubled primes.

A Cunningham chain of the first kind of length n is a sequence of prime numbers (p₁, ..., p_n) such that for all 1 ≤ i < n, p_i+1 = 2p_i + 1. (Hence each term of such a chain except the last one is a Sophie Germain prime, and each term except the first is a safe prime).

It follows that

\begin{aligned} p_{2} & = 2 p_{1} + 1, \\ p_{3} & = 4 p_{1} + 3, \\ p_{4} & = 8 p_{1} + 7, \\ ⋮ \\ p_{i} & = 2^{i - 1} p_{1} + (2^{i - 1} - 1) . \end{aligned}

Or, by setting $a = \frac{p_{1} + 1}{2}$ (the number $a$ is not part of the sequence and need not be a prime number), we have $p_{i} = 2^{i} a - 1$

Similarly, a Cunningham chain of the second kind of length n is a sequence of prime numbers (p₁,...,p_n) such that for all 1 ≤ i < n, p_i+1 = 2p_i − 1.

It follows that the general term is

p_{i} = 2^{i - 1} p_{1} - (2^{i - 1} - 1)

Now, by setting $a = \frac{p_{1} - 1}{2}$ , we have $p_{i} = 2^{i} a + 1$

Cunningham chains are also sometimes generalized to sequences of prime numbers (p₁, ..., p_n) such that for all 1 ≤ i ≤ n, p_i+1 = ap_i + b for fixed coprime integers a, b; the resulting chains are called generalized Cunningham chains.

A Cunningham chain is called complete if it cannot be further extended, i.e., if the previous or next term in the chain would not be a prime number anymore.

Examples of complete Cunningham chains of the first kind include these:

2, 5, 11, 23, 47 (The next number would be 95, but that is not prime.)

3, 7 (The next number would be 15, but that is not prime.)

29, 59 (The next number would be 119, but that is not prime.)

41, 83, 167 (The next number would be 335, but that is not prime.)

Examples of complete Cunningham chains of the second kind include these:

2, 3, 5 (The next number would be 9, but that is not prime.)

7, 13 (The next number would be 25, but that is not prime.)

19, 37, 73 (The next number would be 145, but that is not prime.)

31, 61 (The next number would be 121, but that is not prime.)

Cunningham chains are now considered useful in cryptographic systems since "they provide two concurrent suitable settings for the ElGamal cryptosystem ... [which] can be implemented in any field where the discrete logarithm problem is difficult."^[1]

Largest known Cunningham chains

It follows from Dickson's conjecture and the broader Schinzel's hypothesis H, both widely believed to be true, that for every k there are infinitely many Cunningham chains of length k. There are, however, no known direct methods of generating such chains.

Largest known Cunningham chain of length k (as of 14 December 2013^[2])
k	Kind	p₁ (starting prime)	Digits	Year	Discoverer
1		2^57885161 − 1	17425170	2013	Curtis Cooper, GIMPS
2	1st	18543637900515×2⁶⁶⁶⁶⁶⁷ − 1	200701	2012	Philipp Bliedung, PrimeGrid
2	2nd	648309×2¹⁴⁸³¹⁰ + 1	44652	2010	Tom Wu
3	1st	914546877×2³⁴⁷⁷² − 1	10477	2010	Tom Wu
3	2nd	82659189×2²⁶⁹⁹⁷ + 1	8135	2010	Tom Wu
4	1st	1249097877×6599# − 1	2835	2011	Michael Angel
4	2nd	630698711×4933# + 1	2105	2010	Michael Angel
5	1st	4250172704×2749# − 1	1183	2012	Dirk Augustin
5	2nd	80670856865×2677# + 1	1140	2011	Michael Angel
6	1st	37488065464×1483# − 1	633	2010	Dirk Augustin
6	2nd	37783362904×1097# + 1	475	2006	Dirk Augustin
7	1st	162597166369×827# − 1	356	2010	Dirk Augustin
7	2nd	668302064×593# + 786153598231	251	2008	Thomas Wolter & Jens Kruse Andersen
8	1st	2×65728407627×431# − 1	186	2005	Dirk Augustin
8	2nd	1148424905221×509# + 1	224	2010	Dirk Augustin
9	1st	65728407627×431# − 1	185	2005	Dirk Augustin
9	2nd	182887101390961871050645934589918687746535370612015546956692154622371784133412186×223# + 1	167	2013	Primecoin (block 79349)
10	1st	44598464649019035883154084128331646888059795218766083584048621139159337786287845212160000×149# − 1	146	2013	Primecoin (block 182690)
10	2nd	2361221366027763072635481564211745987513418780208430432809344944242307595601310582×139# + 1	137	2013	Primecoin (block 125775)
11	1st	73853903764168979088206401473739410396455001112581722569026969860983656346568919×151# − 1	140	2013	Primecoin (block 95569)
11	2nd	8026337833619599372491948674562462668692014872229571339857384053514279156849912832×109# + 1	127	2014	Primecoin (block 365304)
12	1st	61592551716229060392971860549140211602858978086524024531871935735163762961673908480×71# − 1	110	2013	Primecoin (block 239833)
12	2nd	160433998429454286861864982184342218645773889300991352796925862298096263175269000×73# + 1	109	2013	Primecoin (block 323183)
13	1st	106680560818292299253267832484567360951928953599522278361651385665522443588804123392×61# − 1	107	2014	Primecoin (block 368051)
13	2nd	457905006824220038355933583213167637693837605663532362031057034656375497233892960×37# + 1	94	2014	Primecoin (block 375981)
14	1st	9510321949318457733566099	25	2004	Jens Kruse Andersen
14	2nd	335898524600734221050749906451371	33	2008	Jens Kruse Andersen
15	1st	662311489517467124375039	24	2008	Jaroslaw Wroblewski
15	2nd	28320350134887132315879689643841	32	2008	Jaroslaw Wroblewski
16	1st	91304653283578934559359	23	2008	Jaroslaw Wroblewski
16	2nd	2368823992523350998418445521	28	2008	Jaroslaw Wroblewski
17	1st	2759832934171386593519	22	2008	Jaroslaw Wroblewski
17	2nd	1302312696655394336638441	25	2008	Jaroslaw Wroblewski

q# denotes the primorial 2×3×5×7×...×q.

Template:As of, the longest known Cunningham chain of either kind is of length 17. The first known was of the 1st kind starting at 2759832934171386593519, discovered by Jaroslaw Wroblewski in 2008 where he also found some of the 2nd kind.^[2]

Congruences of Cunningham chains

Let the odd prime $p_{1}$ be the first prime of a Cunningham chain of the first kind. The first prime is odd, thus $p_{1} \equiv 1 (\mod 2)$ . Since each successive prime in the chain is $p_{i + 1} = 2 p_{i} + 1$ it follows that $p_{i} \equiv 2^{i} - 1 (\mod 2^{i})$ . Thus, $p_{2} \equiv 3 (\mod 4)$ , $p_{3} \equiv 7 (\mod 8)$ , and so forth.

The above property can be informally observed by considering the primes of a chain in base 2. (Note that, as with all bases, multiplying by the number of the base "shifts" the digits to the left.) When we consider $p_{i + 1} = 2 p_{i} + 1$ in base 2, we see that, by multiplying $p_{i}$ by 2, the least significant digit of $p_{i}$ becomes the secondmost least significant digit of $p_{i + 1}$ . Because $p_{i}$ is odd—that is, the least significant digit is 1 in base 2--we know that the secondmost least significant digit of $p_{i + 1}$ is also 1. And, finally, we can see that $p_{i + 1}$ will be odd due to the addition of 1 to $2 p_{i}$ . In this way, successive primes in a Cunningham chain are essentially shifted left in binary with ones filling in the least significant digits. For example, here is a complete length 6 chain which starts at 141361469:

Binary	Decimal
1000011011010000000100111101	141361469
10000110110100000001001111011	282722939
100001101101000000010011110111	565445879
1000011011010000000100111101111	1130891759
10000110110100000001001111011111	2261783519
100001101101000000010011110111111	4523567039

A similar result holds for Cunningham chains of the second kind. From the observation that $p_{1} \equiv 1 (\mod 2)$ and the relation $p_{i + 1} = 2 p_{i} - 1$ it follows that $p_{i} \equiv 1 (\mod 2^{i})$ . In binary notation, the primes in a Cunningham chain of the second kind end with a pattern "0...01", where, for each $i$ , the number of zeros in the pattern for $p_{i + 1}$ is one more than the number of zeros for $p_{i}$ . As with Cunningham chains of the first kind, the bits left of the pattern shift left by one position with each successive prime.

Similarly, because $p_{i} = 2^{i - 1} p_{1} + (2^{i - 1} - 1)$ it follows that $p_{i} \equiv 2^{i - 1} - 1 (\mod p_{1})$ . But, by Fermat's little theorem, $2^{p_{1} - 1} \equiv 1 (\mod p_{1})$ , so $p_{1}$ divides $p_{p_{1}}$ (i.e. with $i = p_{1}$ ). Thus, no Cunningham chain can be of infinite length.^[3]

References

↑ Joe Buhler, Algorithmic Number Theory: Third International Symposium, ANTS-III. New York: Springer (1998): 290
↑ ^2.0 ^2.1 Dirk Augustin, Cunningham Chain records. Retrieved on 2013-12-14.
↑ One of the biggest reasons investing in a Singapore new launch is an effective things is as a result of it is doable to be lent massive quantities of money at very low interest rates that you should utilize to purchase it. Then, if property values continue to go up, then you'll get a really high return on funding (ROI). Simply make sure you purchase one of the higher properties, reminiscent of the ones at Fernvale the Riverbank or any Singapore landed property Get Earnings by means of Renting

In its statement, the singapore property listing - website link, government claimed that the majority citizens buying their first residence won't be hurt by the new measures. Some concessions can even be prolonged to chose teams of consumers, similar to married couples with a minimum of one Singaporean partner who are purchasing their second property so long as they intend to promote their first residential property. Lower the LTV limit on housing loans granted by monetary establishments regulated by MAS from 70% to 60% for property purchasers who are individuals with a number of outstanding housing loans on the time of the brand new housing purchase. Singapore Property Measures - 30 August 2010 The most popular seek for the number of bedrooms in Singapore is 4, followed by 2 and three. Lush Acres EC @ Sengkang

Discover out more about real estate funding in the area, together with info on international funding incentives and property possession. Many Singaporeans have been investing in property across the causeway in recent years, attracted by comparatively low prices. However, those who need to exit their investments quickly are likely to face significant challenges when trying to sell their property – and could finally be stuck with a property they can't sell. Career improvement programmes, in-house valuation, auctions and administrative help, venture advertising and marketing, skilled talks and traisning are continuously planned for the sales associates to help them obtain better outcomes for his or her shoppers while at Knight Frank Singapore. No change Present Rules

Extending the tax exemption would help. The exemption, which may be as a lot as $2 million per family, covers individuals who negotiate a principal reduction on their existing mortgage, sell their house short (i.e., for lower than the excellent loans), or take part in a foreclosure course of. An extension of theexemption would seem like a common-sense means to assist stabilize the housing market, but the political turmoil around the fiscal-cliff negotiations means widespread sense could not win out. Home Minority Chief Nancy Pelosi (D-Calif.) believes that the mortgage relief provision will be on the table during the grand-cut price talks, in response to communications director Nadeam Elshami. Buying or promoting of blue mild bulbs is unlawful.

A vendor's stamp duty has been launched on industrial property for the primary time, at rates ranging from 5 per cent to 15 per cent. The Authorities might be trying to reassure the market that they aren't in opposition to foreigners and PRs investing in Singapore's property market. They imposed these measures because of extenuating components available in the market." The sale of new dual-key EC models will even be restricted to multi-generational households only. The models have two separate entrances, permitting grandparents, for example, to dwell separately. The vendor's stamp obligation takes effect right this moment and applies to industrial property and plots which might be offered inside three years of the date of buy. JLL named Best Performing Property Brand for second year running

The data offered is for normal info purposes only and isn't supposed to be personalised investment or monetary advice. Motley Fool Singapore contributor Stanley Lim would not personal shares in any corporations talked about. Singapore private home costs increased by 1.eight% within the fourth quarter of 2012, up from 0.6% within the earlier quarter. Resale prices of government-built HDB residences which are usually bought by Singaporeans, elevated by 2.5%, quarter on quarter, the quickest acquire in five quarters. And industrial property, prices are actually double the levels of three years ago. No withholding tax in the event you sell your property. All your local information regarding vital HDB policies, condominium launches, land growth, commercial property and more

There are various methods to go about discovering the precise property. Some local newspapers (together with the Straits Instances ) have categorised property sections and many local property brokers have websites. Now there are some specifics to consider when buying a 'new launch' rental. Intended use of the unit Every sale begins with 10 p.c low cost for finish of season sale; changes to 20 % discount storewide; follows by additional reduction of fiftyand ends with last discount of 70 % or extra. Typically there is even a warehouse sale or transferring out sale with huge mark-down of costs for stock clearance. Deborah Regulation from Expat Realtor shares her property market update, plus prime rental residences and houses at the moment available to lease Esparina EC @ Sengkang

External links

The Prime Glossary: Cunningham chain
PrimeLinks++: Cunningham chain
Sequence A005602 in OEIS: the first term of the lowest complete Cunningham chains of the first kind of length n, for 1 ≤ n ≤ 14
Sequence A005603 in OEIS: the first term of the lowest complete Cunningham chains of the second kind with length n, for 1 ≤ n ≤ 15

Template:Prime number classes

[1] Joe Buhler, Algorithmic Number Theory: Third International Symposium, ANTS-III. New York: Springer (1998): 290

[records-2] 2.0 ^2.1 Dirk Augustin, Cunningham Chain records. Retrieved on 2013-12-14.

[3] One of the biggest reasons investing in a Singapore new launch is an effective things is as a result of it is doable to be lent massive quantities of money at very low interest rates that you should utilize to purchase it. Then, if property values continue to go up, then you'll get a really high return on funding (ROI). Simply make sure you purchase one of the higher properties, reminiscent of the ones at Fernvale the Riverbank or any Singapore landed property Get Earnings by means of Renting

In its statement, the singapore property listing - website link, government claimed that the majority citizens buying their first residence won't be hurt by the new measures. Some concessions can even be prolonged to chose teams of consumers, similar to married couples with a minimum of one Singaporean partner who are purchasing their second property so long as they intend to promote their first residential property. Lower the LTV limit on housing loans granted by monetary establishments regulated by MAS from 70% to 60% for property purchasers who are individuals with a number of outstanding housing loans on the time of the brand new housing purchase. Singapore Property Measures - 30 August 2010 The most popular seek for the number of bedrooms in Singapore is 4, followed by 2 and three. Lush Acres EC @ Sengkang

Discover out more about real estate funding in the area, together with info on international funding incentives and property possession. Many Singaporeans have been investing in property across the causeway in recent years, attracted by comparatively low prices. However, those who need to exit their investments quickly are likely to face significant challenges when trying to sell their property – and could finally be stuck with a property they can't sell. Career improvement programmes, in-house valuation, auctions and administrative help, venture advertising and marketing, skilled talks and traisning are continuously planned for the sales associates to help them obtain better outcomes for his or her shoppers while at Knight Frank Singapore. No change Present Rules

Extending the tax exemption would help. The exemption, which may be as a lot as $2 million per family, covers individuals who negotiate a principal reduction on their existing mortgage, sell their house short (i.e., for lower than the excellent loans), or take part in a foreclosure course of. An extension of theexemption would seem like a common-sense means to assist stabilize the housing market, but the political turmoil around the fiscal-cliff negotiations means widespread sense could not win out. Home Minority Chief Nancy Pelosi (D-Calif.) believes that the mortgage relief provision will be on the table during the grand-cut price talks, in response to communications director Nadeam Elshami. Buying or promoting of blue mild bulbs is unlawful.

A vendor's stamp duty has been launched on industrial property for the primary time, at rates ranging from 5 per cent to 15 per cent. The Authorities might be trying to reassure the market that they aren't in opposition to foreigners and PRs investing in Singapore's property market. They imposed these measures because of extenuating components available in the market." The sale of new dual-key EC models will even be restricted to multi-generational households only. The models have two separate entrances, permitting grandparents, for example, to dwell separately. The vendor's stamp obligation takes effect right this moment and applies to industrial property and plots which might be offered inside three years of the date of buy. JLL named Best Performing Property Brand for second year running

The data offered is for normal info purposes only and isn't supposed to be personalised investment or monetary advice. Motley Fool Singapore contributor Stanley Lim would not personal shares in any corporations talked about. Singapore private home costs increased by 1.eight% within the fourth quarter of 2012, up from 0.6% within the earlier quarter. Resale prices of government-built HDB residences which are usually bought by Singaporeans, elevated by 2.5%, quarter on quarter, the quickest acquire in five quarters. And industrial property, prices are actually double the levels of three years ago. No withholding tax in the event you sell your property. All your local information regarding vital HDB policies, condominium launches, land growth, commercial property and more

There are various methods to go about discovering the precise property. Some local newspapers (together with the Straits Instances ) have categorised property sections and many local property brokers have websites. Now there are some specifics to consider when buying a 'new launch' rental. Intended use of the unit Every sale begins with 10 p.c low cost for finish of season sale; changes to 20 % discount storewide; follows by additional reduction of fiftyand ends with last discount of 70 % or extra. Typically there is even a warehouse sale or transferring out sale with huge mark-down of costs for stock clearance. Deborah Regulation from Expat Realtor shares her property market update, plus prime rental residences and houses at the moment available to lease Esparina EC @ Sengkang

[1]

[2]

[3]

@@ Line 1: / Line 1: @@
-Prior to invest loads of money on things like controls per memory cards, appear on-line for a secondhand variations. Occasionally a store will probably getting out of used-game hardware, which could be very economical.  If you have any concerns pertaining to wherever and how to use clash of clans hack cydia ([http://prometeu.net mouse click the next site]), you can get hold of us at the web page. Make sure you look for any web-based seller's feedback prior to the purchase so a few seconds . whether you are having what you covered.<br><br>To help conclude, clash of clans hack tool no feedback survey must not be let to get in the way of the bigger question: what makes we listed here? Putting this particular away its of great skilled dallas pest control. It replenishes the self, provides financial security and even always chips in.<br><br>To take pleasure from unlimited points, resources, silver coins or gems, you must definitely download the clash of clans get into tool by clicking in the button. Depending regarding the operating system that you are using, you will requirement to run the downloaded file for as administrator. Supply you with the log in ID and judge the device. Correct after this, you are would be wise to enter the number of gems or coins that you prefer to get.<br><br>Programs are fun, nonetheless informative also be costly. The costs of games and [http://Www.Wired.com/search?query=consoles consoles] can cost more than many people might choose those to be, but this may often be eliminated.<br><br>And additionally the game is a fabulous mobile edition, it completes not [http://Www.dailymail.co.uk/home/search.html?sel=site&searchPhrase=lack+substance lack substance] as many mobile games. So, defragging the process registry will boost the system overall performance to a fantastic extent. I usually get to any place from 4000 to five thousand m - Points in a day ($4 to $5 for Amazon. Apple mackintosh showed off the extremely anticipated i - Business phone 5 for the first time in San Francisco on Wednesday morning (September 12, 2012). Hard work a huge demand to have some i - Telephone call 4 application not just simply promoting business but also helps users to secure extra money.<br><br>By borer on a boondocks anteroom you possibly can now appearance added advice that's about that play, scout, entente troops, or attack. Of course, these accomplishments will rely on what normally appearance of the fights you might be through.<br><br>Now you have read this composition, you need to the easier time locating and loving video games in your daily life. Notwithstanding your favored platform, from your cellphone to any own computer, playing as well as a enjoying video gaming allows for you to take the benefit of the worries of ones own busy week get specifics.
+In [[mathematics]], a '''Cunningham chain''' is a certain sequence of [[prime number]]s. Cunningham chains are named after [[mathematician]] [[Allan Joseph Champneys Cunningham|A. J. C. Cunningham]]. They are also called '''chains of nearly doubled primes'''.
+A '''Cunningham chain of the first kind''' of length ''n'' is a sequence of prime numbers (''p''<sub>1</sub>,&nbsp;...,&nbsp;''p''<sub>''n''</sub>) such that for all 1&nbsp;&le;&nbsp;''i''&nbsp;<&nbsp;''n'', ''p''<sub>''i''+1</sub>&nbsp;=&nbsp;2''p''<sub>''i''</sub>&nbsp;+&nbsp;1. (Hence each term of such a chain except the last one is a [[Sophie Germain prime]], and each term except the first is a [[safe prime]]).
+It follows that
+: <math>
+\begin{align}
+p_2 & = 2p_1+1, \\
+p_3 & = 4p_1+3, \\
+p_4 & = 8p_1+7, \\
+& {}\  \vdots \\
+p_i & = 2^{i-1}p_1 + (2^{i-1}-1).
+\end{align}
+</math>
+Or, by setting <math> a = \frac{p_1 + 1}{2} </math> (the number <math> a </math> is not part of the sequence and need not be a prime number), we have <math> p_i = 2^{i} a - 1 </math>
+Similarly, a '''Cunningham chain of the second kind''' of length ''n'' is a sequence of prime numbers (''p''<sub>1</sub>,...,''p''<sub>''n''</sub>) such that for all 1&nbsp;≤&nbsp;''i''&nbsp;<&nbsp;''n'', ''p''<sub>''i''+1</sub>&nbsp;=&nbsp;2''p''<sub>''i''</sub>&nbsp;&minus;&nbsp;1.
+It follows that the general term is
+: <math> p_i = 2^{i-1}p_1 - (2^{i-1}-1) \, </math>
+Now, by setting <math> a = \frac{p_1 - 1}{2} </math>, we have <math> p_i = 2^{i} a + 1 </math>
+Cunningham chains are also sometimes generalized to sequences of prime numbers (''p''<sub>1</sub>,&nbsp;...,&nbsp;''p''<sub>''n''</sub>) such that for all 1&nbsp;≤&nbsp;''i''&nbsp;≤&nbsp;''n'', ''p''<sub>''i''+1</sub> =&nbsp;''ap''<sub>''i''</sub>&nbsp;+&nbsp;''b'' for fixed [[coprime]] [[integer]]s ''a'',&nbsp;''b''; the resulting chains are called '''generalized Cunningham chains'''.
+A Cunningham chain is called '''complete''' if it cannot be further extended, i.e., if the previous or next term in the chain would not be a prime number anymore.
+Examples of complete Cunningham chains of the first kind include these:
+: 2, 5, 11, 23, 47 (The next number would be 95, but that is not prime.)
+: 3, 7 (The next number would be 15, but that is not prime.)
+: 29, 59 (The next number would be 119, but that is not prime.)
+: 41, 83, 167 (The next number would be 335, but that is not prime.)
+Examples of complete Cunningham chains of the second kind include these:
+: 2, 3, 5 (The next number would be 9, but that is not prime.)
+: 7, 13 (The next number would be 25, but that is not prime.)
+: 19, 37, 73 (The next number would be 145, but that is not prime.)
+: 31, 61 (The next number would be 121, but that is not prime.)
+Cunningham chains are now considered useful in cryptographic systems since "they provide two concurrent suitable settings for the ElGamal cryptosystem ... [which] can be implemented in any field where the discrete logarithm problem is difficult."<ref>Joe Buhler, ''Algorithmic Number Theory: Third International Symposium, ANTS-III''. New York: Springer (1998): 290</ref>
+== Largest known Cunningham chains ==
+It follows from [[Dickson's conjecture]] and the broader [[Schinzel's hypothesis H]], both widely believed to be true, that for every ''k'' there are infinitely many Cunningham chains of length ''k''.  There are, however, no known direct methods of generating such chains.
+{| class="wikitable"
+|+ Largest known Cunningham chain of length ''k'' (as of 14 December 2013<ref name="records">Dirk Augustin, [http://users.cybercity.dk/~dsl522332/math/Cunningham_Chain_records.htm ''Cunningham Chain records'']. Retrieved on 2013-12-14.</ref>)
+|-
+! ''k'' !! Kind !! ''p''<sub>1</sub> (starting prime) !! Digits !! Year !! Discoverer
+|-
+| 1 ||     || 2<sup>57885161</sup> − 1 || align="right" | 17425170 || 2013 || [[Curtis Cooper (mathematician)|Curtis Cooper]], [[Great Internet Mersenne Prime Search|GIMPS]]
+|-
+| rowspan="2" | 2 || 1st || 18543637900515×2<sup>666667</sup> − 1 || align="right" | 200701 || 2012 || Philipp Bliedung, [[PrimeGrid]]
+|-
+| 2nd || 648309×2<sup>148310</sup> + 1 || align="right" | 44652 || 2010 || Tom Wu
+|-
+| rowspan="2" | 3 || 1st || 914546877×2<sup>34772</sup> − 1 || align="right" | 10477 || 2010 || Tom Wu
+|-
+| 2nd || 82659189×2<sup>26997</sup> + 1 || align="right" | 8135 || 2010 || Tom Wu
+|-
+| rowspan="2" | 4 || 1st || 1249097877×6599# − 1 || align="right" | 2835 || 2011 || Michael Angel
+|-
+| 2nd || 630698711×4933# + 1 || align="right" | 2105 || 2010 || Michael Angel
+|-
+| rowspan="2" | 5 || 1st || 4250172704×2749# − 1 || align="right" | 1183 || 2012 || Dirk Augustin
+|-
+| 2nd || 80670856865×2677# + 1 || align="right" | 1140 || 2011 || Michael Angel
+|-
+| rowspan="2" | 6 || 1st || 37488065464×1483# − 1 || align="right" | 633 || 2010 || Dirk Augustin
+|-
+| 2nd || 37783362904×1097# + 1 || align="right" | 475 || 2006 || Dirk Augustin
+|-
+| rowspan="2" | 7 || 1st || 162597166369×827# − 1 || align="right" | 356 || 2010 || Dirk Augustin
+|-
+| 2nd || 668302064×593# + 786153598231 || align="right" | 251 || 2008 || Thomas Wolter & Jens Kruse Andersen
+|-
+| rowspan="2" | 8 || 1st || 2×65728407627×431# − 1 || align="right" | 186 || 2005 || Dirk Augustin
+|-
+| 2nd || 1148424905221×509# + 1 || align="right" | 224 || 2010 || Dirk Augustin
+|-
+| rowspan="2" | 9 || 1st || 65728407627×431# − 1 || align="right" | 185 <!-- Do not replace this with anything less than 185 digits. Primecoin has a CC9 2nd kind record but this CC9 1st kind record is the overall CC9 record as of August 2013 --> || 2005 || Dirk Augustin
+|-
+| 2nd || 182887101390961871050645934589918687746535370612015546956692154622371784133412186×223# + 1 || align="right" | 167 || 2013 || [[Primecoin]] ([http://primecoin.21stcenturymoneytalk.org/index.php?block_height=79349 block 79349])
+|-
+| rowspan="2" | 10 || 1st || 44598464649019035883154084128331646888059795218766083584048621139159337786287845212160000×149# − 1 || align="right" | 146 || 2013 || Primecoin ([http://primecoin.21stcenturymoneytalk.org/index.php?block_height=182690 block 182690])
+|-
+| 2nd || 2361221366027763072635481564211745987513418780208430432809344944242307595601310582×139# + 1 || align="right" | 137 || 2013 || Primecoin ([http://primecoin.21stcenturymoneytalk.org/index.php?block_height=125775 block 125775])
+|-
+| rowspan="2" | 11 || 1st || 73853903764168979088206401473739410396455001112581722569026969860983656346568919×151# − 1 || align="right" | 140 || 2013 || Primecoin ([http://primecoin.21stcenturymoneytalk.org/index.php?block_height=95569 block 95569])
+|-
+| 2nd || 8026337833619599372491948674562462668692014872229571339857384053514279156849912832×109# + 1 || align="right" | 127 || 2014 || Primecoin ([http://primecoin.21stcenturymoneytalk.org/index.php?block_height=365304 block 365304])
+|-
+| rowspan="2" | 12 || 1st || 61592551716229060392971860549140211602858978086524024531871935735163762961673908480×71# − 1 || align="right" | 110 || 2013 || Primecoin ([http://primecoin.21stcenturymoneytalk.org/index.php?block_height=239833 block 239833])
+|-
+| 2nd || 160433998429454286861864982184342218645773889300991352796925862298096263175269000×73# + 1 || align="right" | 109 || 2013 || Primecoin ([http://primecoin.21stcenturymoneytalk.org/index.php?block_height=323183 block 323183])
+|-
+| rowspan="2" | 13 || 1st || 106680560818292299253267832484567360951928953599522278361651385665522443588804123392×61# − 1 || align="right" | 107 || 2014 || Primecoin ([http://primecoin.21stcenturymoneytalk.org/index.php?block_height=368051 block 368051])
+|-
+| 2nd || 457905006824220038355933583213167637693837605663532362031057034656375497233892960×37# + 1 || align="right" | 94 || 2014 || Primecoin ([http://primecoin.21stcenturymoneytalk.org/index.php?block_height=375981 block 375981])
+|-
+| rowspan="2" | 14 || 1st || 9510321949318457733566099 || align="right" | 25 || 2004 || Jens Kruse Andersen
+|-
+| 2nd || 335898524600734221050749906451371 || align="right" | 33 || 2008 || Jens Kruse Andersen
+|-
+| rowspan="2" | 15 || 1st || 662311489517467124375039 || align="right" | 24 || 2008 || Jaroslaw Wroblewski
+|-
+| 2nd || 28320350134887132315879689643841 || align="right" | 32 || 2008 || Jaroslaw Wroblewski
+|-
+| rowspan="2" | 16 || 1st || 91304653283578934559359 || align="right" | 23 || 2008 || Jaroslaw Wroblewski
+|-
+| 2nd || 2368823992523350998418445521 || align="right" | 28 || 2008 || Jaroslaw Wroblewski
+|-
+| rowspan="2" | 17 || 1st || 2759832934171386593519 || align="right" | 22 || 2008 || Jaroslaw Wroblewski
+|-
+| 2nd || 1302312696655394336638441 || align="right" | 25 || 2008 || Jaroslaw Wroblewski
+|}
+''q''# denotes the [[primorial]] 2×3×5×7×...×''q''.
+{{As of|2013}}, the longest known Cunningham chain of either kind is of length 17. The first known was of the 1st kind starting at 2759832934171386593519, discovered by Jaroslaw Wroblewski in 2008 where he also found some of the 2nd kind.<ref name="records"/>
+== Congruences of Cunningham chains ==
+Let the odd prime <math>p_1</math> be the first prime of a Cunningham chain of the first kind. The first prime is odd, thus <math>p_1 \equiv 1 \pmod{2}</math>. Since each successive prime in the chain is <math>p_{i+1} = 2p_i + 1</math> it follows that <math>p_i \equiv 2^i - 1 \pmod{2^i}</math>. Thus, <math>p_2 \equiv 3 \pmod{4}</math>, <math>p_3 \equiv 7 \pmod{8}</math>, and so forth.
+The above property can be informally observed by considering the primes of a chain in base 2. (Note that, as with all bases, multiplying by the number of the base "shifts" the digits to the left.) When we consider <math>p_{i+1} = 2p_i + 1</math> in base 2, we see that, by multiplying <math>p_i</math> by 2, the least significant digit of <math>p_i</math> becomes the secondmost least significant digit of <math>p_{i+1}</math>. Because <math>p_i</math> is odd—that is, the least significant digit is 1 in base 2--we know that the secondmost least significant digit of <math>p_{i+1}</math> is also 1. And, finally, we can see that <math>p_{i+1}</math> will be odd due to the addition of 1 to <math>2p_i</math>. In this way, successive primes in a Cunningham chain are essentially shifted left in binary with ones filling in the least significant digits. For example, here is a complete length 6 chain which starts at 141361469:
+{| border="1" align="center" class="wikitable"
+! Binary || Decimal
+|- align="right"
+| 1000011011010000000100111101 || 141361469
+|- align="right"
+| 10000110110100000001001111011 || 282722939
+|- align="right"
+| 100001101101000000010011110111 || 565445879
+|- align="right"
+| 1000011011010000000100111101111 || 1130891759
+|- align="right"
+| 10000110110100000001001111011111 || 2261783519
+|- align="right"
+| 100001101101000000010011110111111 || 4523567039
+|}
+A similar result holds for Cunningham chains of the second kind.  From the observation that <math>p_1 \equiv 1 \pmod{2}</math> and the relation <math>p_{i+1} = 2 p_i - 1</math> it follows that <math>p_i \equiv 1 \pmod{2^i}</math>.  In binary notation, the primes in a Cunningham chain of the second kind end with a pattern "0...01", where, for each <math>i</math>, the number of zeros in the pattern for <math>p_{i+1}</math> is one more than the number of zeros for <math>p_i</math>.  As with Cunningham chains of the first kind, the bits left of the pattern shift left by one position with each successive prime.
+Similarly, because <math> p_i = 2^{i-1}p_1 + (2^{i-1}-1) \, </math> it follows that <math>p_i \equiv 2^{i-1} - 1 \pmod{p_1}</math>. But, by [[Fermat's little theorem]], <math>2^{p_1-1} \equiv 1 \pmod{p_1}</math>, so <math>p_1</math> divides <math>p_{p_1}</math> (i.e. with <math> i = p_1 </math>). Thus, no Cunningham chain can be of infinite length.<ref>{{cite journal|last=Löh|first=Günter|title=Long chains of nearly doubled primes|journal=Mathematics of Computation|year=1989|month=October|volume=53|issue=188|pages=751–759|doi=10.1090/S0025-5718-1989-0979939-8|url=http://www.ams.org/journals/mcom/1989-53-188/S0025-5718-1989-0979939-8/}}</ref>
+==References==
+<references/>
+== See also ==
+* [[Primecoin]], which uses Cunningham chains as a proof-of-work system
+== External links ==
+* [http://primes.utm.edu/glossary/page.php?sort=CunninghamChain The Prime Glossary: Cunningham chain]
+* [http://primes.utm.edu/links/theory/special_forms/Cunningham_chains/ PrimeLinks++: Cunningham chain]
+* [http://oeis.org/A005602 Sequence A005602] in [[OEIS]]: the first term of the lowest complete Cunningham chains of the first kind of length&nbsp;''n'',&nbsp;for&nbsp;1&nbsp;≤&nbsp;''n''&nbsp;≤&nbsp;14
+* [http://oeis.org/A005603 Sequence A005603] in [[OEIS]]: the first term of the lowest complete Cunningham chains of the second kind with length&nbsp;''n'',&nbsp;for&nbsp;1&nbsp;≤&nbsp;''n''&nbsp;≤&nbsp;15
+{{Prime number classes}}
+[[Category:Prime numbers]]

Temporal logic: Difference between revisions

Revision as of 06:32, 16 November 2013

Contents

Largest known Cunningham chains

Congruences of Cunningham chains

References

See also

External links

Navigation menu