Friday, 3 April 2020

Recursive Prime Generating Sequences

If we multiply any number by 2 and add 1, the result is an odd number that may or may not be prime. For example, 2 * 3 + 1 = 7 which is prime but 2 * 3 * 4 + 1 = 25 is not prime. So starting with 2 and multiplying by the next number 3 yields a prime but multiplying by the next number 4 gives a composite number. So let's ignore the 4 and just work with 2 and 3. Now 2 * 3 * 5 + 1 = 31 which is prime. We now have 2, 3 and 5. Continuing on, we find that 2 * 3 * 5 * 6 + 1 = 181 which is prime. Now we have 2, 3, 5 and 6. However, 2 * 3 * 5 * 6 * 7 + 1 = 1261 = 13 * 97 and this is composite. If we continue this process up to 1000, including in our list only those numbers that multiply together to give a prime when 1 is added, we arrive at the following list:
2, 3, 5, 6, 9, 12, 16, 22, 25, 29, 31, 35, 47, 57, 61, 66, 79, 81, 108, 114, 148, 163, 172, 185, 198, 203, 205, 236, 265, 275, 282, 294, 312, 344, 359, 377, 397, 398, 411, 427, 431, 493, 512, 589, 647, 648, 660, 708, 719, 765, 887, 911, 916, 935
Figure 1 shows the SageMath algorithm to produce the list which forms part of OEIS A046966:

Figure 1: permalink

The primes resulting from this multiplication of numbers get large quickly as the following progression shows (OEIS A046972):
2, 3, 7, 31, 181, 1621, 19441, 311041, 6842881, 171072001, 4961088001, 153793728001, 5382780480001, 252990682560001, 14420468905920001, 879648603261120001, 58056807815233920001, 4586487817403479680001
Mathematically if S = {2, 3, 5, 6, 9, 12, 16, ... }, then the resulting primes can be represented as \( 1+\displaystyle \prod_{i=1}^n k_i \) where \(k_i \in \) S and \(k_1=2\), \(k_2=3\), \(k_3=5\) etc.

If we impose the condition that only primes will be used to generate primes, then a different set of numbers arise. Here are the first members of the set, made of primes below 1000: 2, 3, 5, 7, 11, 19, 29, 37, 47, 67, 103, 179, 191, 223, 271, 293, 317, 577, 643, 673, 809, 863 and 877. These numbers form a part of OEIS A039726. Figure 2 shows the modified SageMath code used to generate these numbers:

Figure 2: permalink

Mathematically if T = {2, 3, 5, 7, 11, 19, 29, ... } then the resulting primes can be represented as \( 1+\displaystyle \prod_{i=1}^n p_i \) where \(p_i  \in \) T and \(p_1=2\), \(p_2=3\), \(p_3=5\) etc.

Again the primes arising from this multiplication of primes get large quickly (OEIS A087864):
3, 7, 31, 211, 2311, 43891, 1272811, 47093971, 2213416591, 148298911531, 15274787887591, 2734187031878611, 522229723088814511, 116457228248805635731, 31559908855426327282831
These prime generating sequences provide an easy way to get a sequence of very large primes easily. I stumbled upon OEIS A039726 because 25933 is a member of that sequence and 25933 is the number of days old that I am today on my 71st birthday. Here is the full sequence of primes up to and including 25933:
2, 3, 5, 7, 11, 19, 29, 37, 47, 67, 103, 179, 191, 223, 271, 293, 317, 577, 643, 673, 809, 863, 877, 1049, 1093, 1129, 1151, 1381, 1613, 1637, 2089, 2131, 2311, 2957, 3623, 3833, 4253, 4271, 4423, 4673, 5939, 7717, 8167, 9133, 9533, 9539, 9679, 11059, 11743, 11969, 14759, 15859, 15971, 16139, 17431, 17713, 17761, 19309, 19373, 20747, 20983, 23741, 25261, 25933
 The prime resulting from multiplying 25933 by all the previous primes in the sequence is:

39245917564948194983835869291566473410857839336973406163917903204229432402730189405597557200354010052143063430004924215607042377998480357473041097452582168381147410469490307765855029111404711092751691679691

No comments:

Post a Comment