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.

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