Count Down Number Chains

It's hard to decide on a suitable name for this class of numbers but let's recall the process by which I discovered them. Yesterday I turned 27286 days old and it was the factorisation of this number that caught my attention. $$ \begin{align} 27286 &= 2 \times 7 \times 1949\\ &=14 \times 1949 \end{align}$$As can be seen, the factorisation involved the number 1949 which is my year of birth. Interesting enough but it was the number associated with my diurnal age today, 27287, that got me thinking:$$27287 = 13 \times 2099$$Naturally I wondered if there was a pattern here and indeed there was. To cut to the chase, I discovered the following pattern:$$ \begin{align} 27285 &= 15 \times 1855\\27286 &= 14 \times 1949 \\27287 &= 13 \times 2099\\27288 &= 12 \times 2274 \end{align}$$The sequence is contained within 27284 that factorises to 2 x 2 x 19 x 359 and 27289 that factorises to 29 x 941. The next question that occurred to me was how common is such a sequence. It turns out that it is not so common. In the range of up to 40,000, there are only seven such sequences:$$5445 , 5446 , 5447 , 5448\\10905 , 10906 , 10907 , 10908\\16365 , 16366 , 16367 , 16368\\21825 , 21826 , 21827 , 21828\\27285 , 27286 , 27287 , 27288\\32745 , 32746 , 32747 , 32748\\38205 , 38206 , 38207 , 38208$$There is only one number chain that starts with 16 and goes down to 12 (in the range up to 40,000) and that is as follows (permalink):$$ \begin{align} 21824 &=16 \times 1364\\21825 &= 15 \times 1455\\21826 &=14 \times 1559\\21827 &= 13 \times 1679\\21828 &= 12 \times 1819 \end{align}$$Interestingly, if we start with 12 and count down to 2, we get a number chain that is a remarkable ELEVEN terms long (in the range up to 40,000):$$ \begin{align} 27708 &= 12 \times 2309\\27709 &= 11 \times 2519\\27710 &= 10 \times 2771\\27711 &= 9 \times 3079\\27712 &= 8 \times 3464\\27713 &= 7 \times 3959\\27714 &= 6 \times 4619 \\27715 &= 5 \times 5543 \\    27716 &=4 \times 6929 \\ 27717 &= 3 \times 9239 \\ 27718 &= 2 \times 13859  \end{align}$$Extending the range to 100,000, we find that 55428 and 83148 also have this property, marking the start of run of eleven numbers that can be progressively divided by 12 down to 2:

55428 , 55429 , 55430 , 55431 , 55432 , 55433 , 55434 , 55435 , 55436 , 55437 , 55438

Table 1: permalink

83148 , 83149 , 83150 , 83151 , 83152 , 83153 , 83154 , 83155 , 83156 , 83157 , 83158

Table 2: permalink

The sequence 55428 , 55429 , 55430 , 55431 , 55432 , 55433 , 55434 , 55435 , 55436 , 55437 , 55438 has the added distinction that 55439 is prime. It's easy to get carried away by this eleven-fold progression but every second number is a multiple of 2, every third number is a multiple of 3, every fourth number is a multiple of 4, every fifth number is a multiple of 5 etc. So the factorisation is natural enough. However, for it to all come together in a group of eleven numbers is relatively rare as has been discovered.

A Special Class of Semiprimes

Let's recall that a semiprime is a number with two, not necessarily distinct, prime factors. The very first semiprime is 4 = 2 x 2 with only one distinct prime factor. The next is 6 = 2 x 3 with two distinct prime factors. Concatenation involves combining the two factors together so that 2 x 2 becomes 22 and 2 x 3 becomes 23. Concatenating the factors of a semiprime with only one distinct prime factor can never produce a prime because of the repetition of digits. Thus 22 is not prime. However, concatenating the factors of a semiprime with two distinct prime factors can produce a prime. 23 is an example. 

However, the factors need not be written is ascending order. We could just as well write 6 = 3 x 2 and in this case concatenating the digits produces 32 which is not a prime number. The first example of a semiprime whose factors can be concatenated either way to produce a prime is 21 because 21 = 3 x 7 giving 37 and 21 = 7 x 3 giving 73. So this is clear enough. Now let's turn our attention to the so-called emiprimes, a semiprime that remains a semiprime when its digits are reversed. The first example of a semiprime that is an emirpimes is 15 because 15 = 3 x 5 and 51 = 3 x 17.

What I want to find is a list of semiprimes with the following properties:

• the semiprime is also an emirpimes
• the semiprime has two distinct prime factors
• the concatenation of the prime factors of the semiprime in ascending order is a prime
• the concatenation of the prime factors of the semiprime in descending order is a prime
• the emirpimes has two distinct prime factors
• the concatenation of the prime factors of the emirpimes in ascending order is a prime
• the concatenation of the prime factors of the emirpimes in descending order is a prime

This is a demanding list of properties for any semiprime and not surprisingly very few satisfy. Here is a list of such numbers, with factorisation, up to 100,000 (Permalink):

3099 = 3 * 1033

9903 = 3 * 3301

10519 = 67 * 157

11707 = 23 * 509

13993 = 7 * 1999

16387 = 7 * 2341

18247 = 71 * 257

19039 = 79 * 241

30607 = 127 * 241

32667 = 3 * 10889

36367 = 41 * 887

38697 = 3 * 12899

39487 = 7 * 5641

39931 = 73 * 547

70603 = 13 * 5431

70711 = 31 * 2281

72247 = 7 * 10321

73099 = 13 * 5623

74227 = 199 * 373

74281 = 59 * 1259

74289 = 3 * 24763

76029 = 3 * 25343

76363 = 7 * 10909

76623 = 3 * 25541

78361 = 23 * 3407

78493 = 53 * 1481

78619 = 29 * 2711

79683 = 3 * 26561

91501 = 37 * 2473

91687 = 277 * 331

92067 = 3 * 30689

93091 = 127 * 733

98247 = 3 * 32749

99037 = 97 * 1021

That are 34 numbers in the range up to 100,00. Here is the list without factorisation of all the semprimes that satisfy up to ONE MILLION (there are 108 of them):

3099, 9903, 10519, 11707, 13993, 16387, 18247, 19039, 30607, 32667, 36367, 38697, 39487, 39931, 70603, 70711, 72247, 73099, 74227, 74281, 74289, 76029, 76363, 76623, 78361, 78493, 78619, 79683, 91501, 91687, 92067, 93091, 98247, 99037, 100437, 101317, 101899, 104529, 108181, 108789, 120553, 126771, 133243, 134797, 137671, 144523, 147061, 149449, 159427, 160741, 168117, 176731, 176767, 177621, 181801, 184033, 197097, 199879, 312817, 322489, 325441, 328459, 330397, 330481, 331783, 337297, 337897, 338977, 342331, 345493, 350569, 355021, 357393, 365863, 368563, 386197, 387133, 393753, 394543, 711861, 713101, 716779, 717469, 718213, 724951, 734001, 767671, 779833, 790791, 791683, 792733, 793033, 797431, 798733, 925401, 944941, 951679, 954823, 964699, 964717, 965053, 976159, 977617, 978991, 984223, 987801, 996469, 998101

Let's one of these, say 99037, to see that it satisfies. Firstly, we note that 73099 is in the list that we know that it's reversal is an emirpimes. Now its factorisation and concatenations lead to two numbers: 971021 and 102197. Testing confirms that both of these numbers are prime. The emirpimes, 73099 factorises to 13 * 5623 that leads to 135623 and 562313. Again, testing reveals both numbers are prime.

So, out of all the semiprimes in the range up to one million there are only 108 that have the properties listed above. So, we have a very special class of semiprimes indeed. It's interesting to note in the distribution that there are no numbers beginning with 2, 4, 5, 6 or 8 which is to be expected. If a semiprime begins with 2, 4, 5, 6 or 8 then its emirpimes will end in 2, 4, 5, 6 or 8 which means that one of the concatenations of its factors must end in 2 or 5, meaning that it can't be prime. Similarly there are no semiprimes that end in a 0, 2, 4, 5, 6 or 8. In short, all semiprimes that satisfy must start and end with 1, 3, 7 or 9.

Figure 1 shows a table of the frequency of the digital roots of such semiprimes (108 of them in the range up to one million):

Figure 1

Sum and Differences of Odd and Even Powers

Sometimes you need to go back to basics. I found that I was getting confused about the factorisation of general expressions like \(x^n+y^n \). 

SUM OF ODD AND EVEN POWERS

It turns out that if \(n\) is odd, then factorisation is possible according to the rule:$$a^{2n+1}+b^{2n+1}=(a+b)(a^{2n}-a^{2n-1}b+a^{2n-2}b^2- \dots - ab^{2n_1}+b^{2n} \text{ where }n \geq 1$$As an example, consider \(x^7+b^7 \) where$${x^7+b^7=\left(x^{6} - x^{5} y + x^{4} y^{2} - x^{3} y^{3} + x^{2} y^{4} - x y^{5} + y^{6}\right)} {\left(x + y\right)}$$I've seen it stated that \(x^n+y^n \) cannot be factored if \(n\) is even with \(x^2+y^2 \) and \(x^4+y^4\) cited as examples. See Figure 1.

Figure 1: source

This is certainly true for \(n=2\) and \(n=4\) and in fact in any power of 2 (8, 16, 32 etc.) but otherwise any composite number will contain an odd factor e.g. 6 = 2 x 3 and thus we can write \(x^6+y^6\) as \( (x^2)^3+(y^2)^3 \) and it is a sum of odd powers! In fact, it is a sum of two cubes:$$x^6+y^6={\left(x^{4} - x^{2} y^{2} + y^{4}\right)} {\left(x^{2} + y^{2}\right)}$$Now it might be thought that this is a special case, since any \(n\) that is a power of three can be written as a sum of two cubes. So let's consider \(x^{10}+y^{10}\). We jump over \(x^8+y^8\) because we know that it can't be factored. $$\ \begin{align} ( x^{10}+y^{10}&=(x^2)^5+(y^2)^5\\ &= {\left(x^{8} - x^{6} y^{2} + x^{4} y^{4} - x^{2} y^{6} + y^{8}\right)} {\left(x^{2} + y^{2}\right)} \end{align} $$In general, whatever \(m\) divides the even index to produce an odd number, then \(x^m+y^m\) will appear as a factor (this \(m\) must be a multiple of 2). For example, in the case of \(x^{48}+y^{48}\), \(x^{16}+y^{16}\) must be a factor.$$\begin{align} x^{48}+y^{48} &= (x^{16})^3+(y^{16})^3\\&={\left(x^{32} - x^{16} y^{16} + y^{32}\right)} {\left(x^{16} + y^{16}\right)} \end{align}$$DIFFERENCE OF ODD AND EVEN POWERS

In the case of \(x^n-y^n\), the factorisation is:$$x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+ \dots + xy^{n-2} + y^{n-1} \text{ for }n\geq 1$$If \(n \) is odd, then \(x-y\) is a factor and if \(n\) is even, then \(x-y\) and \(x+y\) are factors.$$\begin{align} x^7-y^7&={\left(x^{6} + x^{5} y + x^{4} y^{2} + x^{3} y^{3} + x^{2} y^{4} + x y^{5} + y^{6}\right)} {\left(x - y\right)}\\x^8-y^8&={\left(x^{4} + y^{4}\right)} {\left(x^{2} + y^{2}\right)} {\left(x + y\right)} {\left(x - y\right)} \end{align}$$IN CONCLUSION

• \(x^n- y^n \) can always be factored
• \(x^n+y^n\) can be factored provided \(n\) is not a power of 2.

Proth-like Numbers

Today's tweet for my numbered days was as follows:

It turns out that this number is part of a class of numbers of the form \(k \times 2^n-1 \) where \(k\) is any odd integer and \(n\) is a natural number. Here is a link to a website that shows values of \(k\) between 1 and 299 and lists some corresponding values of \(n\) that produce prime numbers. Note the site was updated on February 18th 2021.

This information can then be used to easily generate a very large prime number. For example, for \(k=7\) some initial values of \(n\) are:

1, 5, 9, 17, 21, 29, 45, 177, 18381, 22529, 24557, 26109, 34857, 41957, 67421, 70209, 169085, 173489, 177977, 363929, 372897

The prime number generated from \( k \times 2^n-1 \) when \(k=7\) and \(n=24557\) has 7394 decimal digits. In the case of \(k=1\), the primes generated are Mersenne primes and \( n \) itself must be a prime number. However, for larger values of \( k \), \( n \) does not need to be prime. Here is the list provided for \(k=1\) at the previously mentioned site:

2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951

Related to numbers of the form \(k \times 2^n-1 \) are the Proth numbers that are of the form \(k \times 2^n+1 \) and that I've written about in a blog post on January 18th 2020.

on Saturday, April 24th 2021