Showing posts with label Cunningham. Show all posts
Showing posts with label Cunningham. Show all posts

Friday, 6 February 2026

A Correction

After creating my post Number's Divisors to Sequence Algorithm, I was feeling satisfied. I'd gotten Gemini to create a neat little table for me. It showed the record lengths reached by numbers under the algorithm in the range up to one million but suffered from the fact that it was simply wrong. Here is the original table:

Number     | Length     | Status
-----------------------------------
2          | 5          | New Record!     
3          | 8          | New Record!     
6          | 10         | New Record!     
11         | 21         | New Record!     
22         | 23         | New Record!     
44         | 25         | New Record!     
50         | 28         | New Record!     
99         | 32         | New Record!     
125        | 33         | New Record!     
206        | 34         | New Record!     
350        | 37         | New Record!     
463        | 44         | New Record!     
487        | 46         | New Record!     
974        | 48         | New Record!     
1375       | 51         | New Record!     
1573       | 52         | New Record!     
1625       | 60         | New Record!     
5200       | 62         | New Record!     
14157      | 63         | New Record!     
16879      | 64         | New Record!     
18747      | 67         | New Record!     
39325      | 70         | New Record!     
89237      | 71         | New Record!     
151911     | 75         | New Record!     
563553     | 77         | New Record!     
803133     | 82         | New Record!  

Fortunately I spotted the problem when looking at the trajectory of the number associated with my diurnal age: 28068. It showed a length of 201, far in excess of the 82 associated with 803133. Furthermore, the algorithm only counted up to 201 and so the sequence was longer than that.

Naturally I confronted Gemini about the problem and here was its response:
The Reason for the DiscrepancyThe sequence for 28068 exhibits a behavior known as a Cunningham Chain.Your rule if is_prime: number = number * 2 + 1 matches the definition of a Cunningham Chain (where $p \to 2p+1$).If the sequence hits a "vein" of consecutive primes (e.g., a chain of 40 primes), the number grows by a factor of $2^{40}$ (approx. 1 trillion). My previous Python code had a safety brake: if number > \(10^12\): break. 28068 likely skyrockets past  one trillion ($10^{12}$) very quickly. My code hit this safety limit and stopped counting, reporting a truncated (incorrect) length.
Gemini proposed modifications to the code but these overtaxed the Jupyter notebook and it got stuck at a point shown in Figure 1.


Figure 1

Eventually I decided to get Gemini to write the code for just a single number as input and not a range. Even this proved too much for the Jupyter notebook. I don't know whether the sequence for 28068 goes on forever or not but I do know that the original algorithm that Gemini provided me with was flawed. It was only by chance that I found this out so caution is advised in accepting anything Gemini offers up. I've commented in the past on its coding limitations.

The failure of the algorithm to reach completion is attributed to Cunningham chains so I'd thought I'd better look back at that topic. It turns out that the longest known Cunningham chain of the first kind (\(2p+1\) is 17 primes long so why does Gemini mention chains of 40 primes when none are known? Nonetheless, it's likely that the \(2p+1\) rule that I'm applying to prime numbers does lead quickly to very large number. My choice of this rule was quite arbitrary. Given that \(4k+1\) and \(4k-1\) primes are pretty much in equal abundance, I could apply an alternative rule such as the following to a prime \(p\):
  • if \(p \pmod 4 \equiv 1\) then \(p \rightarrow 2 \times p +1 \)
  • if \(p \pmod 4 \equiv 3\) then \(p \rightarrow (p -1 )/2 \)
This should keep the progressive numbers from growing too large. I should do this with the factors as well (see earlier posts Number's Factors to Sequence Algorithm 1 and Number's Factors to Sequence Algorithm 2). Figure 2 shows the record breaking numbers under these new rules (up to one million).


Figure 2: permalink

In summary, the record breaking numbers are 1, 2, 4, 13, 17, 34, 50, 98, 294, 650, 722, 2166, 4751, 5313, 9502, 11979, 19773, 46137, 125229, 257049, 385573, 714025.

I also got Gemini to write the code for the input of a single number and the trajectory of the number as output. Let's use 28068 as an example. Figure 2 shows the output.


Figure 3: permalink

ADDENDUM on 16th of February 2026:

It appears that this latest program to determine the record lengths under the new algorithm is faulty. If 28077 is entered the program crashes because the numbers become too large. I confronted Gemini with this discovery and it pointed out that number size is capped at $10^{25}$) and some sequences explode so quickly that they exceed the number cap before they reach a record length. Gemini modified the product to detect numbers leading to these exploding sequences. There are quite a few. Figure 4 shows the 27 of them in the range from 28004 to 28449. This gives some idea of their frequency (27 out 445 or a little over 6%).


Figure 4: permalink

Sunday, 5 March 2023

The End of a Millennium

My diurnal age today is 26999 and thus the last of a millennium that began almost three years ago when I turned 26000 days old. The digits of the number have the rather special property that they add to 1:$$\frac{1}{2}+\frac{1}{6}+\frac{1}{9}+\frac{1}{9}+\frac{1}{9}=1$$This property qualifies it for membership in OEIS A091783:


 A091783

Numbers with digits in non-decreasing order such that sum of the reciprocals of the digits is 1.



Such numbers are, not surprisingly, few and far between and all exclude zero. The initial members are:

1, 22, 236, 244, 333, 2488, 2666, 3366, 3446, 4444, 26999, 28888, 33999, 34688, 36666, 44488, 44666, 55555, 366999, 368888, 446999, 448888, 466688, 666666, 3999999, 4688999, 4888888, 6666999, 6668888, 7777777, 66999999, 68888999, 88888888, 999999999 

Here is a permalink to a SageMath algorithm that will generate these numbers up to 40000. If we relax the condition that the digits must be in non-decreasing order but still exclude zero, then up to 40000, the qualifying numbers are:

1, 22, 236, 244, 263, 326, 333, 362, 424, 442, 623, 632, 2488, 2666, 2848, 2884, 3366, 3446, 3464, 3636, 3644, 3663, 4288, 4346, 4364, 4436, 4444, 4463, 4634, 4643, 4828, 4882, 6266, 6336, 6344, 6363, 6434, 6443, 6626, 6633, 6662, 8248, 8284, 8428, 8482, 8824, 8842, 26999, 28888, 29699, 29969, 29996, 33999, 34688, 34868, 34886, 36488, 36666, 36848, 36884, 38468, 38486, 38648, 38684, 38846, 38864, 39399, 39939, 39993

These numbers constitute OEIS  A037268:


 A037268

Sum of reciprocals of digits = 1.   
                                        


If we relax the condition that none of the digits of the number can be zero and simply ignore the zeros when finding the reciprocal sum, then the resultant numbers constitute OEIS  A214959:


 A214959

Numbers for which the sum of reciprocals of nonzero digits = 1.   
     
           

The initial members of the sequence are:

1, 10, 22, 100, 202, 220, 236, 244, 263, 326, 333, 362, 424, 442, 623, 632, 1000, 2002, 2020, 2036, 2044, 2063, 2200, 2306, 2360, 2404, 2440, 2488, 2603, 2630, 2666, 2848, 2884, 3026, 3033, 3062, 3206, 3260, 3303, 3330, 3366, 3446, 3464, 3602, 3620, 3636, 3644, 3663, 4024, 4042, 4204, 4240, 4288, 4346, 4364, 4402, 4420, 4436, 4444, 4463, 4634, 4643, 4828, 4882, 6023, 6032, 6203, 6230, 6266, 6302, 6320, 6336, 6344, 6363, 6434, 6443, 6626, 6633, 6662, 8248, 8284, 8428, 8482, 8824, 8842, 10000, 20002, 20020, 20036, 20044, 20063, 20200, 20306, 20360, 20404, 20440, 20488, 20603, 20630, 20666, 20848, 20884, 22000, 23006, 23060, 23600, 24004, 24040, 24088, 24400, 24808, 24880, 26003, 26030, 26066, 26300, 26606, 26660, 26999, 28048, 28084, 28408, 28480, 28804, 28840, 28888, 29699, 29969, 29996, 30026, 30033, 30062, 30206, 30260, 30303, 30330, 30366, 30446, 30464, 30602, 30620, 30636, 30644, 30663, 32006, 32060, 32600, 33003, 33030, 33066, 33300, 33606, 33660, 33999, 34046, 34064, 34406, 34460, 34604, 34640, 34688, 34868, 34886, 36002, 36020, 36036, 36044, 36063, 36200, 36306, 36360, 36404, 36440, 36488, 36603, 36630, 36666, 36848, 36884, 38468, 38486, 38648, 38684, 38846, 38864, 39399, 39939, 39993

We can generalise even more by relaxing the requirement that the sum of the reciprocals must be unity and instead require it to be simply be any integer. These numbers, with zero excluded, constitute OEIS A034708: 


 A034708

Numbers for which the sum of reciprocals of digits is an integer.   
                


Clearly, the more 1's that there are in the number, the larger the integer e.g. 11111 has a sum of reciprocals of digits equal to 5. The members of this sequence, of which there are 321 members up to 40000, are:

1, 11, 22, 111, 122, 212, 221, 236, 244, 263, 326, 333, 362, 424, 442, 623, 632, 1111, 1122, 1212, 1221, 1236, 1244, 1263, 1326, 1333, 1362, 1424, 1442, 1623, 1632, 2112, 2121, 2136, 2144, 2163, 2211, 2222, 2316, 2361, 2414, 2441, 2488, 2613, 2631, 2666, 2848, 2884, 3126, 3133, 3162, 3216, 3261, 3313, 3331, 3366, 3446, 3464, 3612, 3621, 3636, 3644, 3663, 4124, 4142, 4214, 4241, 4288, 4346, 4364, 4412, 4421, 4436, 4444, 4463, 4634, 4643, 4828, 4882, 6123, 6132, 6213, 6231, 6266, 6312, 6321, 6336, 6344, 6363, 6434, 6443, 6626, 6633, 6662, 8248, 8284, 8428, 8482, 8824, 8842, 11111, 11122, 11212, 11221, 11236, 11244, 11263, 11326, 11333, 11362, 11424, 11442, 11623, 11632, 12112, 12121, 12136, 12144, 12163, 12211, 12222, 12316, 12361, 12414, 12441, 12488, 12613, 12631, 12666, 12848, 12884, 13126, 13133, 13162, 13216, 13261, 13313, 13331, 13366, 13446, 13464, 13612, 13621, 13636, 13644, 13663, 14124, 14142, 14214, 14241, 14288, 14346, 14364, 14412, 14421, 14436, 14444, 14463, 14634, 14643, 14828, 14882, 16123, 16132, 16213, 16231, 16266, 16312, 16321, 16336, 16344, 16363, 16434, 16443, 16626, 16633, 16662, 18248, 18284, 18428, 18482, 18824, 18842, 21112, 21121, 21136, 21144, 21163, 21211, 21222, 21316, 21361, 21414, 21441, 21488, 21613, 21631, 21666, 21848, 21884, 22111, 22122, 22212, 22221, 22236, 22244, 22263, 22326, 22333, 22362, 22424, 22442, 22623, 22632, 23116, 23161, 23226, 23233, 23262, 23323, 23332, 23611, 23622, 24114, 24141, 24188, 24224, 24242, 24411, 24422, 24818, 24881, 26113, 26131, 26166, 26223, 26232, 26311, 26322, 26616, 26661, 26999, 28148, 28184, 28418, 28481, 28814, 28841, 28888, 29699, 29969, 29996, 31126, 31133, 31162, 31216, 31261, 31313, 31331, 31366, 31446, 31464, 31612, 31621, 31636, 31644, 31663, 32116, 32161, 32226, 32233, 32262, 32323, 32332, 32611, 32622, 33113, 33131, 33166, 33223, 33232, 33311, 33322, 33616, 33661, 33999, 34146, 34164, 34416, 34461, 34614, 34641, 34688, 34868, 34886, 36112, 36121, 36136, 36144, 36163, 36211, 36222, 36316, 36361, 36414, 36441, 36488, 36613, 36631, 36666, 36848, 36884, 38468, 38486, 38648, 38684, 38846, 38864, 39399, 39939, 39993

For example, \(36613 \rightarrow \dfrac{1}{3}+\dfrac{1}{6}+\dfrac{1}{6}+\dfrac{1}{1}+\dfrac{1}{3}=2\)

While the sum of reciprocals equaling unity is 26999's most distinctive property and qualifies it for membership in several OEIS sequences, it also enjoys the following interesting properties:

26999 is a Cunningham number since it can be written as \(30^3-1\). 

A number \(n\) is a Cunningham number if it can be written as \(C^{+}(b,k)=b^k+1\)  or  \(C^{-}(b,k)=b^k-1\)  for  \(b,k > 1\). The previous such number was \(26897=164^2+1\) and the next will be \(27001=30^3+1\).

26999 is a de Polignac number because none of the positive numbers \(26999 -2^k\) is a prime. These numbers (all composite) are:

1 --> 26997
2 --> 26995
3 --> 26991
4 --> 26983
5 --> 26967
6 --> 26935
7 --> 26871
8 --> 26743
9 --> 26487
10 --> 25975
11 --> 24951
12 --> 22903
13 --> 18807
14 --> 10615

26999 is a modest number because \(999|26999=26\). See my recent post titled Modest Numbers.

26999 is a Smith number  since the sum of its digits (35) coincides with the sum of the digits of its prime factors.

Wednesday, 21 December 2022

Linear Prime Chains

On Thursday, June 10th of 2019, I posted about Generalised Cunningham Chains while linking to earlier posts that discussed the topic of Cunningham chains. Today I was reminded of these chains because the number associated with my diurnal age has the following property:


 A124017

Numbers \(n\) for which \(2n-1\), \(4n-1\), \(8n-1\), \(16n-1\) and \(32n-1\) are primes.



The initial members of the sequence are:

45, 90, 26820, 26925, 30705, 31710, 33375, 63420, 63570, 71805, 83865, 93075, 103185, 127140, 134025, 148050, 170460, 202635, 211035, 223305, 269505, 297225, 303660, 329175, 335625, 362505, 387975, 405270, 405405, 406425, 409755, 463335

In the case of 26925, the sequence of primes generated is 53849, 107699, 215399, 430799 and 861599. At first I thought the sequence was a Cunningham chain of the second kind with a length of 5. This type of chain has the property that  \(p_{i+1} = 2p_{i} − 1\) for all \(1 \leq i \leq 5 \) but, as can be seen, it is the new number that is doubled and not the original one. In other words, a Cunningham chain of the second kind with a length of 6 and a starting prime of \(p\) would give a sequence of \(p, 2p-1, 4p-3, 8p-7, 16p-15, 32p-31\). Not the same sequence at all.

I was interested in pushing the number of primes further and test for \(64n-1\). Up to one million this yields the following sequence of numbers with their prime chains attached:

45 --> 89 179 359 719 1439 2879 
31710 --> 63419 126839 253679 507359 1014719 2029439 
63570 --> 127139 254279 508559 1017119 2034239 4068479 
202635 --> 405269 810539 1621079 3242159 6484319 12968639 
405405 --> 810809 1621619 3243239 6486479 12972959 25945919 
534600 --> 1069199 2138399 4276799 8553599 17107199 34214399 
561330 --> 1122659 2245319 4490639 8981279 17962559 35925119 
589305 --> 1178609 2357219 4714439 9428879 18857759 37715519 
666945 --> 1333889 2667779 5335559 10671119 21342239 42684479 
799350 --> 1598699 3197399 6394799 12789599 25579199 51158399 
903045 --> 1806089 3612179 7224359 14448719 28897439 57794879 
979125 --> 1958249 3916499 7832999 15665999 31331999 62663999 

How many numbers up to one million will generate primes up to \(128n-1\)? Well as it turns out, only one number. Beyond \(128n-1\), there are no chains in the range up to one million.

561330 --> 1122659 2245319 4490639 8981279 17962559 35925119 71850239 

Just as with generalised Cunningham chains, we can also generalise this particular prime chain sequence by changing the value of the subtrahend. Let's change it to 3 and look for prime chains starting with \(2n-3\) and ending with \(128n-3\). Here's the result and there are seven numbers instead of just one in the range up to one million:

3025 --> 6047 12097 24197 48397 96797 193597 387197 
238865 --> 477727 955457 1910917 3821837 7643677 15287357 30574717 
253880 --> 507757 1015517 2031037 4062077 8124157 16248317 32496637 
477730 --> 955457 1910917 3821837 7643677 15287357 30574717 61149437 
507760 --> 1015517 2031037 4062077 8124157 16248317 32496637 64993277 
680185 --> 1360367 2720737 5441477 10882957 21765917 43531837 87063677 
883180 --> 1766357 3532717 7065437 14130877 28261757 56523517 113047037 

We even get 2 numbers that generate a chain that goes up to \(256n-3\). They are:

238865 --> 477727 955457 1910917 3821837 7643677 15287357 30574717 61149437 
253880 --> 507757 1015517 2031037 4062077 8124157 16248317 32496637 64993277  

There are no numbers in the range that generate primes up to \(512n-1\). Let's try a subtrahend of 5 and see what numbers generate primes in the range from \(2n-5\) up to \(128n-5\). The results are:

 273 --> 541 1087 2179 4363 8731 17467 34939 
 933 --> 1861 3727 7459 14923 29851 59707 119419 
 54558 --> 109111 218227 436459 872923 1745851 3491707 6983419 
 59553 --> 119101 238207 476419 952843 1905691 3811387 7622779 
 65811 --> 131617 263239 526483 1052971 2105947 4211899 8423803 
447678 --> 895351 1790707 3581419 7162843 14325691 28651387 57302779 
887226 --> 1774447 3548899 7097803 14195611 28391227 56782459 113564923 

There are no numbers up to one million that generate primes up to \(256n-5\). What about a subtrahend of 7 and a range from \(2n-7\) to \(128n-7\)? The results are:

27360 --> 54713 109433 218873 437753 875513 1751033 3502073 
517875 --> 1035743 2071493 4142993 8285993 16571993 33143993 66287993 
524805 --> 1049603 2099213 4198433 8396873 16793753 33587513 67175033 
549915 --> 1099823 2199653 4399313 8798633 17597273 35194553 70389113 
749580 --> 1499153 2998313 5996633 11993273 23986553 47973113 95946233 

There are no numbers that generate chains up to \(256n-7\). I think that's enough for the subtrahends but what about the coefficients? We could generalise further by looking at even coefficients larger than 2. If we choose odd coefficients, then every odd number will produce an even number when an odd subtrahend is subtracted. Let's try \(4n-11\) in the range up to \(256n-11\). The results are:

187123 --> 748481 2993957 11975861 47903477 191613941 766455797 3065823221 12263292917 
363375 --> 1453489 5813989 23255989 93023989 372095989 1488383989 5953535989 23814143989 
426040 --> 1704149 6816629 27266549 109066229 436264949 1745059829 6980239349 27920957429 
723330 --> 2893309 11573269 46293109 185172469 740689909 2962759669 11851038709 47404154869 

The reason that 187123 is marked in red is that it is the only starting number that is prime. This of course is rather interesting. All the other long chains are generated by composite numbers. Here is a permalink that allows for experimentation with prime chains generated by a number \(n\) using the linear mapping of \(a \cdot n-b\) where \(a\) and \(b\) are integers.

For a post that has relevance to the content of this post, visit Prime Producing Linear Polynomials. After all, what I've been investigating in this post is simply a variety of prime producing linear polynomials of the general from \(y=ax+b\) where \(a,b\) and \(x\) are restricted to integer values.

Friday, 2 December 2022

Woodall Numbers

Today, having turned 26906 days old, I discovered that this number has a connection with so-called Woodall primes that are simply Woodall numbers that are prime. So what characterises a Woodall number? To quote from this source:

In number theory, a Woodall number \( W_n \) is any natural number of the form:$$W_{n}=n\cdot 2^{n}-1$$for some natural number \(n\). The first few Woodall numbers are: 1, 7, 23, 63, 159, 383, 895, … (sequence A003261 in the OEIS). Woodall numbers were first studied by Allan J. C. Cunningham and H. J. Woodall in 1917, inspired by James Cullen's earlier study of the similarly defined Cullen numbers. The previous source goes on to say that:

Woodall numbers that are also prime numbers are called Woodall primes; the first few exponents \(n\) for which the corresponding Woodall numbers \(W_n\) are prime are 2, 3, 6, 30, 75, 81, 115, 123, 249, 362, 384, ... (sequence A002234 in the OEIS); the Woodall primes themselves begin with 7, 23, 383, 32212254719, ... (sequence A050918 in the OEIS) ... almost all Woodall numbers are composite. It is an open problem whether there are infinitely many Woodall primes. As of October 2018, the largest known Woodall prime is \(17016602 × 2^{17016602} − 1\). It has 5,122,515 digits and was found by Diego Bertolotti in March 2018 in the distributed computing project PrimeGrid.

26906 however, to return to my diurnal age, arises in the context of so-called Generalized Woodall Numbers. These numbers are defined thus:

A generalized Woodall number base b is defined to be a number of the form \(n × b^n − 1\), where \(n + 2 > b\) if a prime can be written in this form, it is then called a generalized Woodall prime.

The number associated with my diurnal age turns out to be a member of OEIS A299378:


 A299378

Numbers \(k\) such that \(k \cdot 15^k - 1\) is prime.                              

                                     

Thus it can be seen that 26906 belongs to those exponents for which the generalized Woodall numbers \(k \cdot 15^k -1\), with \(b=15\),  are prime. These are quite rare with the initial exponents being:

2, 10, 14, 2312, 16718, 26906, 27512, 41260, 45432, 162454, 217606

Thus \(26906 \cdot 15^{26906} -1 \) is prime and is needless to say a very large prime. As of November 2021, the largest known generalized Woodall prime with base greater than 2 is \(2740879 \cdot 32^{2740879} − 1\).

Below is a list of numbers \(n\) for increasing values of \(b\) such that \(n \cdot b^n − 1\) is prime. The corresponding OEIS sequence is listed if it exists:

1 3, 4, 6, 8, 12, 14, 18, 20, 24, 30, 32, 38, 42, 44, 48, 54, 60, 62, 68, 72, 74, 80, 84, 90, 98, 102, 104, 108, 110, 114, 128, 132, 138, 140, 150, 152, 158, 164, 168, 174, 180, 182, 192, 194, 198, 200, 212, 224, 228, 230, 234, 240, 242, 252, 258, 264, 270, 272, 278, 282, 284, 294, ... (all primes plus 1) A008864

2 2, 3, 6, 30, 75, 81, 115, 123, 249, 362, 384, 462, 512, 751, 822, 5312, 7755, 9531, 12379, 15822, 18885, 22971, 23005, 98726, 143018, 151023, 667071, 1195203, 1268979, 1467763, 2013992, 2367906, 3752948, ... A002234

3 1, 2, 6, 10, 18, 40, 46, 86, 118, 170, 1172, 1698, 1810, 2268, 4338, 18362, 72662, 88392, 94110, 161538, 168660, 292340, 401208, 560750, 1035092, ... A006553

4 1, 2, 3, 5, 8, 14, 23, 63, 107, 132, 428, 530, 1137, 1973, 2000, 7064, 20747, 79574, 113570, 293912, ..., 1993191, ... A086661

5 8, 14, 42, 384, 564, 4256, 6368, 21132, 27180, 96584, 349656, 545082, ... A059676

6 1, 2, 3, 19, 20, 24, 34, 77, 107, 114, 122, 165, 530, 1999, 4359, 11842, 12059, 13802, 22855, 41679, 58185, 145359, 249987, ... A059675

7 2, 18, 68, 84, 3812, 14838, 51582, ... A242200

8 1, 2, 7, 12, 25, 44, 219, 252, 507, 1155, 2259, 2972, 4584, 12422, 13905, 75606, ... A242201

9 10, 58, 264, 1568, 4198, 24500, ... A242202

10 2, 3, 8, 11, 15, 39, 60, 72, 77, 117, 183, 252, 396, 1745, 2843, 4665, 5364, ... A059671

11 2, 8, 252, 1184, 1308, ... A299374

12 1, 6, 43, 175, 821, 910, 1157, 13748, 27032, 71761, 229918, ... A299375

13 2, 6, 563528, ... A299376

14 1, 3, 7, 98, 104, 128, 180, 834, 1633, 8000, 28538, 46605, 131941, 147684, 433734, ... A299377

15 2, 10, 14, 2312, 16718, 26906, 27512, 41260, 45432, 162454, 217606, ... A299378

16 167, 189, 639, ... A299379

17 2, 18, 20, 38, 68, 3122, 3488, 39500, ... A299380

18 1, 2, 6, 8, 10, 28, 30, 39, 45, 112, 348, 380, 458, 585, 17559, 38751, 43346, 46984, 92711, ... A299381

19 12, 410, 33890, 91850, 146478, 189620, 280524, ... A299382

20 1, 18, 44, 60, 80, 123, 429, 1166, 2065, 8774, 35340, 42968, 50312, 210129, ... A299383

21 2, 18, 200, 282, 294, 1174, 2492, 4348, ...

22 2, 5, 140, 158, 263, 795, 992, 341351, ...

23 29028, ...

24 1, 2, 5, 12, 124, 1483, 22075, 29673, 64593, ...

25 2, 68, 104, 450, ...

26 3, 8, 79, 132, 243, 373, 720, 1818, 11904, 134778, ...

27 10, 18, 20, 2420, 6638, 11368, 14040, 103444, ...

28 2, 5, 6, 12, 20, 47, 71, 624, 1149, 2399, 8048, 30650, 39161, ...

29 26850, 237438, 272970, ...

30 1, 63, 331, 366, 1461, 3493, 4002, 5940, 13572, 34992, 182461, 201038, ...

Let's take some examples for \(b=30\) from the above list. When \(n=1\), we have \(1 \cdot 30^1-1=29\) which is prime and when \(n=63\) we have \(63 \cdot 30^{63}-1\) being prime. This latter number is:

72107360226142762177814830874900999999999999999999999999999999999999999999999999999999999999999

Monday, 8 February 2021

Cunningham Numbers

I've come across Cunningham Chains before and written about them in several posts. However, I've not written about Cunningham Numbers before. These numbers always occur in pairs and the previous such pair was 25920 and 25922 that can be represented as \(161^2-1\) and \(161^2+1\) respectively. Today I turned 26243 days old and this is equal to \(162^2-1\) and the other member of the pair is 26245 equal to \(162^2+1\). So what defines such numbers. 

Here is a definition: Cunningham numbers are a simple type of binomial number, they are of the form$$b^n\pm1 \text{ where }b \text{ and } n \text{ are integers and }\\b \text{ is not a perfect power. They are denoted by }C^±(b,n)$$

Establishing whether or not a given Cunningham number is prime has been the main focus of research around this type of number. Two particularly famous families of Cunningham numbers in this respect are the Fermat numbers, which are those of the form \(C^+(2,2m) \), and the Mersenne numbers, which are of the form \( C^−(2,n) \).

Primes of the form \(C^±(b,n)\) are very rare. To quote from WolframAlphaMathWorld:

A necessary (but not sufficient) condition for \( C^+(2,n)=2^n+1\) to be prime is that \(n\) be of the form \(n=2^m\). Numbers of the form \(F_m=C^+(2,2^m)=2^{2^m}+1\) are called Fermat numbers, and the only known primes occur for:

  • \(C^+(2,1)=3\)
  • \(C^+(2,2)=5\) 
  • \(C^+(2,4)=17\) 
  • \(C^+(2,8)=257\)
  • \(C^+(2,16)=65537\)

In other words for \(m=0, 1, 2, 3, 4 \). The only other primes \(C^+(b, n)\) for nontrivial \(b \leq 11\) and \(2 \leq n\leq 1000\) are:

  • \(C^+(6,2)=37\) 
  • \(C^+(6,4)=1297\) 
  • \(C^+(10,2)=101\) 

\(C^+(2,n)=2^n+1\) is always divisible by 3 when \(n\) is odd. The Mersenne numbers \(M_n=C^-(2,n)=2^{n}-1\) are known to be prime only for 44 values, the first few of which are \(n=2, 3, 5, 7, 13, 17, 19, ... \) (OEIS A000043). Such numbers are known as Mersenne primes. There are no other primes \(C^-(b,n)\) for nontrivial \(b \leq 20\) and \(2\leq n\leq 1000\).

If primes are rare amongst the Cunningham numbers, then most are composite and thus factorable which leads us into the Cunningham Project:

The Cunningham project is a project, started in 1925, to factor numbers of the form \(b^n ± 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. There are three printed versions of the table, the most recent published in 2002, as well as an online version.

Figure 1 shows the current limits of the exponents:

Figure 1
Two types of factors can be derived from a Cunningham number without having to use a factorisation algorithm: algebraic factors, which depend on the exponent, and Aurifeuillian factors, which depend on both the base and the exponent.
Perhaps, I'll explore the topic of factorisation of Cunningham numbers in more detail at a later date. For the moment, it can be noted that:

Once the algebraic and Aurifeuillian factors are removed, the other factors of \(b^n ± 1\) are always of the form \(2kn + 1\), since they are all factors of \(\displaystyle \Phi _{n}(b) \). 
When \(n\) is prime, both algebraic and Aurifeuillian factors are not possible, except the trivial factors \(b − 1\) for \(b^n − 1\) and \(b + 1\) for \(b^n + 1\).
In general, all factors of $$ \frac{b^n − 1}{b − 1}$$ are of the form \(2kn + 1\), where \(b ≥ 2\) and \(n\) is prime, except when \(n\) divides \(b − 1\), in which case $$ \frac{b^n − 1}{b − 1}$$ is divisible by \(n\) itself.

Of course, for the pairs of Cunningham numbers mentioned earlier ((25920, 25922) and (26243, 26245)), the value of \(n\) is 2 and hence prime. This means that there are no algebraic or Aurifeuillian factors, only the trivial factors and factors to the form \(4k+1\). The factorisations are:

  • \(25920 =161^2-1=160 \times 162=2^6 \times 3^4 \times 5\) 
  • \(25922 =161^2+1=2 \times 13 \times 997\) 
  • \(26243 = 162^2-1=161 \times 163=7 \times 23 \times 163 \)
  • \(26245 = 162^2+1=5 \times 29 \times 181\)