PRIME + and NON-PRIME - Improved Format

As with the EVEN + and ODD - and EVEN - and ODD + recursive algorithms, I've taken the original 393 page data document and converted it to a 83 page PDF that is more reader friendly. Here some excerpts.

Figure 1

Figure 2

Figure 3

Table 1

Table 2

Table 3

Table 4

Dual Attractors

I've written about attractors, vortices, vorticals and captives in many earlier posts. In my nomenclature attractors can be prime/non-prime or odd/even:

• a prime/non-prime attractor has sums of prime digits and non-prime digits that are equal
• an odd/even attractor has sums of odd and even digits that are equal

An example of a prime/non-prime attractor would be 28330 where 2 + 3 + 3 = 8 + 0. Other numbers do not have this balance and under the recursion:

number --> number + sum of prime digits - sum of non-prime digits

some will be "attracted" to 28330, meaning that repeated application of the recursion will lead to the attractor. In the case of 28330, there are 19 such numbers (termed captives):

28327, 28331, 28332, 28333, 28334, 28335, 28336, 28337, 28338, 28339, 28340, 28341, 28342, 28343, 28344, 28345, 28346, 28348, 28349

An example of an odd/even attractor would be 29612 where 9 + 1 = 2 + 6 + 2. Other numbers again do not have this balance and under the recursion:

number --> number + sum of odd digits - sum of even digits

some will be "attracted" to 29612, meaning that repeated applications of the recursion will lead to the attractor. In the case of 29612, there are 20 such numbers (termed captives):

29517, 29537, 29559, 29571, 29583, 29585, 29587, 29590, 29591, 29592, 29594, 29596, 29598, 29605, 29610, 29611, 29613, 29614, 29616, 29618

Some attractors can be both prime/non-prime and odd/even and in the range up to 40000 there are 223 of them (permalink):

0, 112, 121, 211, 336, 358, 363, 385, 538, 583, 633, 835, 853, 1012, 1021, 1102, 1120, 1201, 1210, 2011, 2101, 2110, 3036, 3058, 3063, 3085, 3306, 3360, 3445, 3454, 3467, 3476, 3508, 3544, 3580, 3603, 3630, 3647, 3674, 3746, 3764, 3805, 3850, 4345, 4354, 4367, 4376, 4435, 4453, 4534, 4543, 4556, 4565, 4578, 4587, 4637, 4655, 4673, 4736, 4758, 4763, 4785, 4857, 4875, 5038, 5083, 5308, 5344, 5380, 5434, 5443, 5456, 5465, 5478, 5487, 5546, 5564, 5645, 5654, 5667, 5676, 5748, 5766, 5784, 5803, 5830, 5847, 5874, 6033, 6303, 6330, 6347, 6374, 6437, 6455, 6473, 6545, 6554, 6567, 6576, 6657, 6675, 6734, 6743, 6756, 6765, 6778, 6787, 6877, 7346, 7364, 7436, 7458, 7463, 7485, 7548, 7566, 7584, 7634, 7643, 7656, 7665, 7678, 7687, 7768, 7786, 7845, 7854, 7867, 7876, 8035, 8053, 8305, 8350, 8457, 8475, 8503, 8530, 8547, 8574, 8677, 8745, 8754, 8767, 8776, 10012, 10021, 10102, 10120, 10201, 10210, 11002, 11020, 11200, 12001, 12010, 12100, 20011, 20101, 20110, 21001, 21010, 21100, 30036, 30058, 30063, 30085, 30306, 30360, 30445, 30454, 30467, 30476, 30508, 30544, 30580, 30603, 30630, 30647, 30674, 30746, 30764, 30805, 30850, 33006, 33060, 33600, 34045, 34054, 34067, 34076, 34405, 34450, 34504, 34540, 34607, 34670, 34706, 34760, 35008, 35044, 35080, 35404, 35440, 35800, 36003, 36030, 36047, 36074, 36300, 36407, 36470, 36704, 36740, 37046, 37064, 37406, 37460, 37604, 37640, 38005, 38050, 38500

Let's take 37640 as an example:

• it is a prime attractor since prime digits 3 + 7 = 6 + 4 + 0 (non-prime digits)
  
  It has 14 captives: 37612, 37615, 37617, 37623, 37627, 37632, 37633, 37641, 37642, 37643, 37644, 37646, 37648, 37649
  
  
• it is an odd/even attractor since odd digits 3 + 7 = 6 + 4 + 0 (even digits)
  
  It has 11 captives: 37611, 37617, 37619, 37629, 37633, 37641, 37642, 37643, 37644, 37646, 37648

Of course the order of digits makes no difference and so many of these 223 numbers are just permutations of another's digits and 0's can be added anywhere because they do not affect the sum. Take 358 as an example. Permutations of its digits with or without 0 added include 385, 538, 583, 835, 853, 3058, 3085, 3508, 3580, 3805, 3850 etc.

In fact if we strip out the zeroes and put the digits in ascending order then the above list of 223 reduces to merely 112, 336, 358, 3445, 3467, 4556, 4578, 5667, 6778.

Recursive Sum of Prime Factors

On Saturday the 21st of August 2021, I posted about composite numbers that become prime after repeated iterations of f(\(x\)) = sum of prime factors of \(x\) considered with and without multiplicity. The post was titled Analysis of a Recursive Process. I was reminded of these types of numbers due to one of the properties of the number associated with my diurnal age today. The number is 27364 and it is a member OEIS A047827:

A047827

Numbers that become prime after exactly 8 iterations of f(\(x\)) = sum of prime factors of \(x\) where multiplicity is ignored.

It's good to revisit this important topic because this is only the second post that I've made about it over the years. There are only 18 such numbers in the range up to 40,000 and these are:

13682, 18002, 19137, 22934, 24014, 24787, 27364, 27849, 30062, 30993, 32577, 33477, 35410, 35798, 36004, 36398, 36706, 39206

In the case of 27364 the progression is shown in Figure 1 where "sopf" stands for "sum of prime factors" taken without regard to multiplicity.

Figure 1

It's interesting to look at the statistics regarding the number of iterations required by composite numbers to reach a prime number using the sum of prime factors. In my first post, my statistics extended only to 100,000 but in this post I'll extend the range to one million. What do we find? Here are links to two different algorithms for extracting this information (permalink1 and permalink2).

• 1 iteration:   107551
• 2 iterations: 125340
• 3 iterations:  221225
• 4 iterations:  237764
• 5 iterations:  144624
• 6 iterations:     62205
• 7 iterations:     18951
• 8 iterations:       3416
• 9 iterations:          397
• 10 iterations:          26
• 11 iterations:             2
• 12 iterations:             0

Presumably there will be numbers larger than one million for which 12 iterations are possible and I assume the sequence is infinite. However, SageMathCell struggles above the one million mark, so that's as far as I can go. However, the two numbers less than one million for which 11 iterations are possible are 334142 and 668284. The table below shows the stages for the larger number to give an idea of the progression:

     number   factorisation         prime factors       sopf 

 

  668284   2^2 * 167071    [2, 167071]     167073

  167073   3 * 55691       [3, 55691]      55694

  55694    2 * 27847       [2, 27847]      27849

  27849    3 * 9283        [3, 9283]       9286

  9286     2 * 4643        [2, 4643]       4645

  4645     5 * 929         [5, 929]        934

  934      2 * 467         [2, 467]        469

  469      7 * 67          [7, 67]         74

  74       2 * 37          [2, 37]         39

  39       3 * 13          [3, 13]         16

  16       2^4             [2]             2

So this post is focused on the iterations where the multiplicity of the prime factors is ignored. For iterations where multiplicity is counted refer back to my earlier post Analysis of a Recursive Process.

Factorions

Figure 1

On Chris Pickover's Twitter feed, I came across the factorion, a term he uses to describe numbers of the form 145 where 1! + 4! + 5! = 145. Figure 1 shows his tweet. He defines a factorion as a natural number that equals the sum of the factorials of its digits. There are only two of these: 145 and 40585. 

Drawing on an analogy to amicable numbers, Wikipedia introduces the term amicable factorions to describe a pair of numbers in which the factorial digit sum of one number equals the other number. The two such pairs of numbers are (871, 45361) and (872, 45362). 

871 --> 45361 --> 871

872 --> 45362 --> 872

Again, in keeping with the analogy to sociable numbers, Wikipedia introduces the term sociable factorians to describe numbers that eventually return to themselves after repeated applications of the factorial sum of digits. Examples are 169, 363601 and 1454 where:

169 --> 363601 --> 1454 --> 169

These three numbers can be said to have a cycle length of three and thus amicable factorions could be considered as sociable factorions with a cycle length of 2. Similarly factorians could be viewed as sociable factorions with a cycle length of 1.

Thus factorions of whatever ilk are few and far between. The list comprises only:

• 145 factorion
• 169 sociable factorion
• 871 amicable factorion
• 872 amicable factorion
• 1454 sociable factorion
• 40585 factorion
• 45361 amicable factorion
• 45362 amicable factorion
• 363601 sociable factorion

Thus the largest factorion, 363601, has six digits. A factorion could, theoretically, have seven digits because the smallest seven digit number is 1,000,000 and the largest factorial digit sum of a seven digit number is 7 x 9! = 2,540,160. However, factorions of eight digits and beyond are not possible because the smallest eight digit number is 10,000,000 and the largest factorial digit sum of an eight digit number is 8 x 9! = 2,903,040. Let's not forget that 0! = 1 by the way.

The Wikipedia articles looks at the topic using more mathematical terminology and considers number bases other than 10 but I'll keep this post simple (and I'm feeling lazy). Here is permalink to the SageMath algorithm that generates the above list. Below I've embedded the SageMath code:

Recursion involving the Divisor Function

Interesting results arise when we consider the following iterative process involving a starting number \(n\):$$ \begin{align} n&=\frac{n}{\sigma(n,0)} \text{    if } n \equiv 0  \! \! \! \mod \sigma(n,0)\\ n&=n+\sigma(n,0) \text{    if } n \not \equiv 0 \! \! \! \mod \sigma(n,0) \end{align}$$This has the effect of quickly reducing the size of the number when it is divisible by the number of its divisors and increasing the number slightly in the case where it is not divisible before trying again.

Let's consider what happens to the number 42 under this recursive process:

• 42 has 8 divisors [1, 2, 3, 6, 7, 14, 21, 42]
  42 isn't divisible by 8, so 42 --> 42 + 8 = 50
  
  
• 50 has 6 divisors [1, 2, 5, 10, 25, 50]
  50 isn't divisible by 6 so 50 --> 50 + 6 = 56
  
  
• 56 has 8 divisors [1, 2, 4, 7, 8, 14, 28, 56]
  8 does divide into 56 to give 7
  
  
• 7 has 2 divisors [1, 7]
  7 isn't divisible by 2 so 7 --> 7 + 2 = 9
  
  
• 9 has 3 divisors [1, 3, 9]
  3 does divide into 9 to give 3
  
  
• 3 has 2 divisors [1, 3]
  3 isn't divisible by 2 so 3 --> 3 + 2 = 5
  
  
• 5 has 2 divisors [1, 5]
  5 isn't divisible by 2 and so 5 --> 5 + 2 = 7

Thus the trajectory of 42 ends in a loop because 5 takes us back to 7. The trajectory is thus 42, 50, 56, 7, 9, 3, 5. All trajectories end in this loop as far as I can determine. In this case, the number of steps is 6 and the trajectory has 7 members when including the starting number.

As usual, it's interesting to look for those numbers that have trajectories of record length. What I found in the range up to 30,000 was the following (SageMathCell permalink):

1, 2, 3, 4, 6, 11, 27, 216, 224, 227, 425, 815, 1641, 13244, 19305, 19317 

These numbers corresponded to trajectories of the following lengths:

1, 2, 4, 5, 8, 16, 75, 77, 78, 105, 275, 282, 951, 952, 1393, 1396

Figure 1 shows these results in tabular format. 

Figure 1

What's surprising is that a relatively small number like 19317 can have a trajectory length of 1396. It's interesting to look at the trajectory of this number. Figure 2 is a plot of the trajectory lengths.

Figure 2

Looking at Figure 2, we see how there is steady buildup until a number (27252) that is divisible by its number of divisors (18) and then there is a precipitous drop to 1514 and the same process is repeated on a smaller scale for what looks like two more times. 

We can see the same process at work a little more clearly for 27 that has a record length of 75. See Figure 3.

Figure 3

Here is the full trajectory of 27 that ends in the 7, 9, 3, 5 loop:

27, 31, 33, 37, 39, 43, 45, 51, 55, 59, 61, 63, 69, 73, 75, 81, 86, 90, 102, 110, 118, 122, 126, 138, 146, 150, 162, 172, 178, 182, 190, 198, 210, 226, 230, 238, 246, 254, 258, 266, 274, 278, 282, 290, 298, 302, 306, 318, 326, 330, 346, 350, 362, 366, 374, 382, 386, 390, 406, 414, 426, 434, 442, 450, 25, 28, 34, 38, 42, 50, 56, 7, 9, 3, 5

Analysis of a Recursive Process

Today I turned 26438 days old and one of the properties of this number is that it's a member of OEIS A048128:

A048128

Becomes prime or 4 after exactly 6 iterations of f(x) = sum of prime factors of x.

Approximately 10.7% of the numbers in the range up to 26438 satisfy this criterion. The sum of the prime factors is calculated with multiplicity. I was encouraged to investigate how this percentage changed as the number of iterations decreased and increased from six. I decided to increase the range up to 100,000. In this range, the percentage increases to 12.63%. Here is a permalink to the algorithm that I developed in SageMathCell to calculate these percentages.

The results for the various iterations were as follows:

• 0:   09.59%
• 1:   12.29%
• 2:   15.21%
• 3:   15.24%
• 4:   13.44%
• 5:   15.31%
• 6:   12.63%
• 7:   04.89%
• 8:   01.18%
• 9:   00.21%
• 10: 0.020%
• 11: 0.020%

No number between 1 and 100,000 survives 12 iterations. Only two numbers survive 11 iterations and these are 27933 and 55694. Let's look at the trajectory of these two numbers. 

• 27933, 9314, 4659, 1556, 393, 134, 69, 26, 15, 8, 6, 5
• 55694, 27849, 9286, 4645, 934, 469, 74, 39, 16, 8, 6, 5

As can be seen, both end in the prime number 5. The key to 55694's longevity is its repeated factorisation into biprimes with one small and one large factor. These are the factorisations:

• 55694 = 2 * 27847
• 27849 = 3 * 9283
• 9286 = 2 * 4643
• 4645 = 5 * 929
• 934 = 2 * 467
• 469 = 7 * 67
• 74 = 2 * 37
• 39 = 3 * 13
• 16 = 2 * 2 * 2 * 2
• 8 = 2 * 2 * 2
• 6 = 2 * 3
• 5 is prime

Here is a permalink to an algorithm that will calculate the trajectory of any number under this recursive process. Figure 1 shows a graph of the trajectory of 55694.

Figure 1

How do things change when we consider only the prime factor without multiplicity? Here are the results:

• 0:   09.59%
• 1:   11.81%
• 2:   14.78%
• 3:   26.51%
• 4:   21.27%
• 5:   11.08%
• 6:   3.955%
• 7:   0.899%
• 8:   0.093%
• 9:   0.006%
• 10: 0.000%
• 11: 0.000%

Because the sum of the prime factors without multiplicity is always equal to or smaller than the sum with multiplicity, the numbers will in general reach 4 or a prime more quickly.

Odds and Evens

Today, having turned 26372 days old, I set out finding something interesting about this number. There wasn't anything that caught my attention until I stumbled upon the information shown in Figure 1.

Figure 1

The site link that is displayed refuses to load but the purple print piqued my curiosity:

Add to n its odd digits and subtract its even ones

I realised that 26372 is special in this regard because its odd digits (3 and 7) add to 10 and its even digits (2, 6 and 2) also add to 10. The number is unaffected by this process of addition and subtraction. It might be termed stable under this process. What about other numbers that aren't stable? How many repetitions of the process are needed on average for a number to become a stable number? Are there some numbers that never become stable? What proportion of numbers are stable? That's what I set out to investigate in a SageMath program that examined the first 100,000 integers. Here is a permalink to that program. 

The output reveals that 88985, 88987 and 91055 produce record runs of 81 steps before reaching a stable number. The average run or trajectory length is 8.58. Figure 1 shows a plot of all trajectory lengths for numbers from 1 to 100000.

Figure 1: permalink

So how many numbers are stable in that range. Here is a permalink to another SageMath program that determines this. The answer turns out to 3725 or 3.725% of the numbers between 1 and 100,000. In the range from 1 to 1000, the numbers are:

112, 121, 134, 143, 156, 165, 178, 187, 211, 314, 336, 341, 358, 363, 385, 413, 431, 516, 538, 561, 583, 615, 633, 651, 718, 781, 817, 835, 853, 871

These numbers form OEIS  A036301 but there is no further analysis done.

A036301

Numbers whose sum of even digits and sum of odd digits are equal.

Of the 3725 numbers between 1 and 100000 that are member of OEIS A036301, 301 are prime. Here is a permalink to a program that will verify this.

I wrote another program that displays the "trajectory" or path of a number on its journey from instability to stability or looping. Here is a permalink to this program. Applied to 88985, it can be seen that the trajectory is:

88985, 88975, 88980, 88965, 88957, 88962, 88947, 88943, 88935, 88936, 88926, 88911, 88906, 88893, 88881, 88850, 88831, 88811, 88789, 88781, 88765, 88755, 88756, 88746, 88727, 88723, 88715, 88712, 88702, 88691, 88679, 88673, 88661, 88634, 88611, 88591, 88590, 88588, 88561, 88545, 88535, 88532, 88522, 88507, 88503, 88495, 88489, 88470, 88457, 88449, 88434, 88413, 88397, 88400, 88380, 88359, 88360, 88341, 88325, 88315, 88308, 88287, 88268, 88236, 88215, 88203, 88188, 88157, 88154, 88140, 88121, 88105, 88095, 88093, 88089, 88074, 88061, 88040, 88020, 88002, 87984, 87980, 87980

After 81 steps, the stable number 87980 is reached. The table in Figure 2 shows that the numbers near 88985 and 88987 have mostly near-record trajectory lengths.

Figure 2

However, Figure 3 shows that 91055 is very much a singleton.

Figure 3

If the range is extended to 200,000, a new record of 91 is reached with 158893. The trajectory is:

158893, 158895, 158899, 158907, 158921, 158927, 158939, 158958, 158962, 158961, 158963, 158967, 158975, 158994, 159006, 159015, 159036, 159048, 159051, 159072, 159092, 159114, 159127, 159148, 159152, 159171, 159195, 159225, 159241, 159251, 159270, 159290, 159312, 159329, 159354, 159373, 159401, 159413, 159428, 159429, 159447, 159461, 159467, 159479, 159506, 159520, 159538, 159553, 159581, 159594, 159619, 159638, 159642, 159645, 159655, 159674, 159686, 159681, 159683, 159687, 159695, 159718, 159733, 159761, 159778, 159799, 159839, 159858, 159862, 159861, 159863, 159867, 159875, 159894, 159906, 159924, 159942, 159960, 159978, 160001, 159997, 160037, 160042, 160031, 160030, 160028, 160013, 160012, 160006, 159995, 160033, 160034, 160028

Interestingly, a stable number is not reached but instead a loop arises: 160028, 160013, 160012, 160006, 159995, 160033, 160034, 160028. So some numbers attain "stability" (such as 88985) while others enter a loop (such as 158893). 

Figure 4 is a plot of all trajectory lengths from 1 to 200,000:

Figure 4

Note that the average trajectory length has increased from 8.58 to 10.6 which makes sense. As numbers get bigger, it should take them longer to settle on a stable number or to enter a loop. It's difficult to explore beyond 200,000 because SageMathCell times out. 

I developed another algorithm to check on the relative proportions of numbers that end up as stable numbers versus ending in a loop. Here is a permalink. The results are as follows:

• total of numbers ending in a stable number is 58977 up to 100000 or 59.0 percent
• total of numbers ending in loop is 37298 up to 100000 or 37.3 percent
• total number of stable numbers up to 100000 is 3725 or 3.73 percent

Figure 5 shows a graphical representation:

Figure 5

One general point to note about this odd-even recursive process is that there are five odd digits (1, 3, 5, 7 and 9) totalling 25 and four even digits (2, 4, 6 and 8) totalling 20. The process thus favours the progressive numbers getting larger rather than smaller. 

Some stable numbers attract unstable numbers far more strongly than others. Figure 6 shows a table listing the top "attractors". As can be seen, 87980 might be termed the Great Attractor with 881 unstable numbers being attracted to it. Here is a permalink to the program that created the information.

Figure 6: Google Sheet Link

Looking at all the data in the spreadsheet, 134 stands out because even though it is a small number, it attracts 74 unstable numbers.

Overall, it's clear than in terms of this odd-even recursive process there are three types of numbers:

• numbers that remain unchanged by the process e.g. 112. 
• numbers that are changed by the process and in the end become unchangeable numbers e.g. 114 becomes 112 in only one step of the process.
• numbers that are changed by the process and in the end become trapped in a loop e.g. 5 which has a trajectory of 10, 11, 13, 17, 23, 24, 18, 11 and so becomes caught in a loop and never becomes an unchangeable.

We might call the first type of number immutable and the two other types mutable but differentiated by a prefix i-mutable and v-mutable where v stands for vortex (that these types of numbers are drawn into). So 112 could be described as an immutable number, 114 as i-mutable and 5 as v-mutable. These differentiators are speculative and might change but they do serve to clearly identify each type of number.

Another nomenclature that I considered was that of attractor and captive. It's as if the gravitational pull of an attractor (an immutable number in my previous nomenclature) pulls the i-mutable numbers to them and so in a sense they are captives of the attractor. The v-mutable numbers are also attracted by the vortices comprised of a series to two or more looping chains of numbers, each member of which might be termed a vortical. This could be explained as follows:

• 112 is an attractor
• 114 is a captive of the attractor 112
• 5 is a captive of the vortex {10, 11, 13, 17, 23, 24, 18}
• 10, 11, 13, 17, 23, 24 and 18 are vorticals comprising the vortex

In the past, my first response to a number was to consider whether it was prime or composite whereas now I'll be inclined to also consider whether it's mutable or immutable and, if the former, whether it is i-mutable or v-mutable OR I might just settle on attractor, captive and vortical.

Solving Linear Recurrences

This article follows on from my previous post of June 10th 2020 titled Fibonacci-like Sequences. I owe a debt of gratitude to Niloufar Shafiei who has posted an excellent PDF about solving linear recurrence relations. He treats both linear homogeneous recurrences and linear non-homogeneous recurrences but it is only the former that I'll concern myself with in this post.

With a linear recurrence, each term of a sequence is a linear function of earlier

terms in the sequence. An example would be:$$a_n=a_{n-1}+a_{n-2}+1$$However, this is not homogenous, because the last term, 1, does not involve an earlier term of the sequence. An example of a linear homogenous recurrence would be:$$a_n=a_{n-1}+2a_{n-2} \text{ with }a_0=1 \text{ and }a_1=5$$This corresponds to the quadratic:$$x^2=x+2 \text{ so that }x^2-x-2 = (x-2)(x+1)$$This equals 0 when \(x=2\) or \(x=-1\).

The PDF referred to earlier shows that the \(n\)-th term can be written in a form that is a linear combination of the two solutions:$$ \alpha_1(2^n)+\alpha_2(-1)^n \text{ where } \alpha_1 \text{ and } \alpha_2 \text{ are constants to be determined}$$The values of \(\alpha_1 \text{ and } \alpha_2 \) can be determined from the initial conditions. When we substitute for \(n=0\) and \(n=1\), this means that:$$\alpha_1+\alpha_2=1 \text{ and } 2 \alpha_1-\alpha_2=5$$Solving this pair of equations, we find \( \alpha_1=2\) and \( \alpha_2=-1\) and thus \(a_n\) can be written as:$$a_n=2^{n+1}-(-1)^n \text{ for } n \ge 0$$The dominant term of course is \(2^n\) and so:$$\lim_{n -> \infty}\frac{a_{n+1}}{a_n}=2$$The first ten terms of this sequence are (SageMathCell permalink):

1, 5, 7, 17, 31, 65, 127, 257, 511, 1025, 2047, 4097

If the quadratic associated with the recurrence relation has a repeated root, then a slightly different approach is required. For example, let's consider the recurrence:$$a_n=6a_{n-1}-9a_{n-2} \text{ with } a_0=1 \text{ and } a_1=9$$The quadratic that arises is:$$x^2=6x-9 \text{ or } x^2-6x+9=(x-3)^2$$The repeated root here is \(x=3\) and Niloufar Shafiei in his PDF shows that in this case, the solution is:$$\alpha_1(3)^n+\alpha_2 n(3)^n \text{ or } 3^n(\alpha_1+\alpha_2n)$$Again, we get two equation in two unknowns and in this case, after applying the initial conditions, the solution is \(\alpha_1=1\) and \(\alpha_2=2\). Thus \(a_n\) can be written as:$$a_n=3^n(1+2n) \text{ for } n \ge 0$$The dominant term is \(3^n\) and so:$$\lim_{n -> \infty}\frac{a_{n+1}}{a_n}=3$$The first ten elements of the sequence are (SageMathCell permalink):

1, 9, 45, 189, 729, 2673, 9477, 32805, 111537, 373977, 1240029, 4074381

So this is the essential idea. Niloufar Shafiei in his PDF has plenty more examples that are easy to understand and well-presented. There is a lot more to delve into regarding recurrence equations and I'm sure I'll be writing more about them in the future.

Bell Numbers

Figure 1: book cover

I came across an interesting book titled Combinatorics and Number Theory of Counting Sequences by István Mezö and, while most of the content looks intimidating, the author starts off very simply. He certainly gets around as the brief biographical details in Figure 2 reveal. He has a website on Google Sites and interestingly he also has something to say about surreal numbers which I haven't heard anything of since reading Donald Knuth's eponymous book. Well, I started reading it but didn't finish. Maybe this guy can rekindle my interest.

Figure 2: brief biography of author

The first topic he introduces is Bell Numbers, that I've certainly heard about, but never understood. The problem with my current approach to number theory (whereby I look at the mathematical significance of my diurnal age) is that it's rather discursive. I come into contact with a broad range of concepts but don't pursue them in any great depth.

If I could work my way further into this book, I might be able to remedy that. Anyway, I now understand Bell Numbers and I'll try to present what I've found out about them here and hopefully include some practical applications that a little research may throw up. The Bell numbers arise from a simple enough problem. Suppose we have a group of six people that we shall label 1, 2, 3, 4, 5, 6. These six people can make up the set A = {1, 2, 3, 4, 5, 6}. We ask the question: in how many ways can we arrange these six people into groups with no person able to be in more than one group? A group can consist of between one and six members.

Figure 3: I downloaded and collected this group of six characters using SketchUp

The author starts off by looking at small sets. One person can be placed in only one group obviously but two people can be placed into groups in two different ways, either together 1, 2 or separately 1|2. For three people, there are five possibilities:

1, 2, 3 or 1|2, 3 or 2|1, 3 or 3|1, 2 or 1|2|3

These are the first three Bell numbers named after Eric Temple Bell (1883-1960), Scottish mathematician, writer and early science fiction author. Thus:$$B_1=1 \text{ and } B_2=2 \text{ and } B_3=5$$I'll quote directly from the book here and he explains how to derive a general recursive formula for the Bell numbers:

As n grows, it is becoming harder and harder to calculate the Bell numbers by simply listing the partitions, so we must find a simpler way. To do this, we consider the following method. Let us fix an n-set A, and we pick out an arbitrary element a from that of n. If we consider all the partitions of A, there will be n possible cases: the element a is in a block of k elements, where k can be 1, 2, . . . , n. The first possibility, when k = 1, results in the block {a}. When a is in a two-element block, say, in {a, b}, then we have to choose the element b beside a. This can be done in \(n − 1 =  \binom{n-1}{1} \) ways. If a is contained in a block of three elements, then we have to choose two elements beside a on \( \binom{n-2}{2} \) ways. And so on, until arriving k = n: if a is contained in an n-block (i.e., the partition contains one block and this is the whole A), then we have to choose n−1 elements beside a. This is possible just in \( \binom{n-1}{n-1}= 1 \) way. After n−1 fixing the size k of the block of a, we can focus on the remaining elements not in the block of a. We see that the remaining n−k elements can be partitioned arbitrarily and the total number of these partitions is \(B_{n−k} \) by the definition of the Bell numbers. Hence, for any single k there are \( \binom{n-1}{n-k} B_{n-k}\) cases. We can sum up the possible values of k, because these cases are pairwise disjoint. Hence we have:

$$B_n=1 \, . B_{n-1}+\binom{n-1}{1} \,.B_{n-2}+\binom{n-2}{2} \, . B_{n-3} + \dots + \binom{n-1}{n-1} \, . 1$$For consistency in the previous formula, we can replace the initial 1 with \( \binom{n-1}{0}\) and the final 1 with \(B_0=1\). This produces:$$B_n=\binom{n-1}{0} \, . B_{n-1}+\binom{n-1}{1} \,.B_{n-2}+\binom{n-2}{2} \, . B_{n-3} + \dots + \binom{n-1}{n-1} \, . B_0$$This can be written more succinctly as:$$B_n=\sum_{k=0}^{n-1} \binom{n-1}{k} \, .B_{n-k-1}$$Using the fact that \( \binom{n}{k}=\binom{n}{n-k} \) and \( \binom{n-1}{k}=\binom{n-1}{n-1-k} \), we can then write:$$B_n=\sum_{k=0}^{n-1} \binom{n-1}{n-1-k} \, .B_{n-1-k}=\sum_{k=0}^{n-1} \binom{n-1}{k} \, .B_{k}$$The recursive formula on the right enables us to find other Bell numbers. We already know that \(B_0=1, B_1=1, B_2=2 \text{ and } B_3=5 \) and so:$$B_4=\sum_{k=0}^{4-1} \binom{4-1}{k} \, .B_k=\binom{3}{0} \, . B_0+ \binom{3}{1} \, . B_1+\binom{3}{2} \, . B_2+\binom{3}{3} \, . B_3= 15$$Continuing this process, we get \(B_5=52\) and \(B_6=203\) and thus:

Question: in how many ways can we arrange these six people into groups with no person able to be in more than one group?

Answer: 203.

There is however, an easier way to generate the Bell numbers if we don't want to concern ourselves with theoretical justification. It involves use of the so-called Bell triangle, explained by Wikipedia in full but just shown below as it's pretty self-explanatory:

Here are the first five rows of the triangle constructed by these rules: 

 1
 1   2
 2   3   5
 5   7  10  15
15  20  27  37  52 

The Bell numbers appear on both the left and right sides of the triangle.

Mezö's approach to deriving the Bell numbers, as outlined above, involves the use of Stirling numbers of the second kind. These are simply the components of the summation that were obtained from the different values of k. The symbol used is:$$\begin{Bmatrix}
           n \\         
           k \\
          \end{Bmatrix}$$It represents how many groups of k can be formed from n elements. For example, take the case of n=4 and k=2. Suppose A = {a, b, c, d}, then we have the following seven possibilities:

1|2,3,4   2|1,3,4   3|1,2,4   4|1,2,3   1,2|3,4   1,3|2,4   1,4|2,3

$$\text{Thus }\begin{Bmatrix}
           4 \\         
           2 \\
          \end{Bmatrix}=7 \text{ and likewise }\begin{Bmatrix}
           4 \\         
           1 \\
          \end{Bmatrix}=1 \, , \begin{Bmatrix}
           4 \\         
           3 \\
          \end{Bmatrix}=6 \text{ and }\begin{Bmatrix}
           4 \\         
           4 \\
          \end{Bmatrix}=1$$ $$ \text{Thus we can say that } B_n=\begin{Bmatrix}
           n \\         
           1\\
          \end{Bmatrix}+\begin{Bmatrix}
           n \\         
           2 \\
          \end{Bmatrix}+ \cdots +\begin{Bmatrix}
           n \\         
           n \\
          \end{Bmatrix}$$That's as far as I'll pursue the Stirling numbers here but I'd like to now look at some of the practical applications for Bell numbers. Wikipedia provides two examples:

Factorisations

If a number N is a square-free positive integer (meaning that it is the product of some number n of distinct prime numbers), then Bn gives the number of different multiplicative partitions of N. These are factorisations of N into numbers greater than one, treating two factorisations as the same if they have the same factors in a different order. For instance, 30 is the product of the three primes 2, 3, and 5, and has B3 = 5 factorisations:$$30=2\times 15=3\times 10=5\times 6=2\times 3\times 5$$Rhyme schemes

The Bell numbers also count the rhyme schemes of an n-line poem or stanza. A rhyme scheme describes which lines rhyme with each other, and so may be interpreted as a partition of the set of lines into rhyming subsets. Rhyme schemes are usually written as a sequence of Roman letters, one per line, with rhyming lines given the same letter as each other, and with the first lines in each rhyming set labeled in alphabetical order. Thus, the 15 possible four-line rhyme schemes are AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC, and ABCD.

Bell numbers can be prime and thus there are Bell primes. The first few are:$$B_2=2 \, ,B_3=5 \, , B_7=877 \text{ and }B_{13}=27644437$$The indices are prime as well but this is not always the case as the next two indices yielding prime numbers are 42 and 55 (and very large primes they are too). Bell is famous for his somewhat flawed 1937 book "Men of Mathematics" but he also wrote science fiction novels under the name John Taine.

Figure 4: cover of Bell's book

For some interesting biographical details on E. T. Bell, follow this link. There is an interesting comment made in A History of Mathematics: From Mesopotamia to Modernity by Luke Hodgkin (2005):

The fact that Wiles was stimulated in childhood by E. T. Bell's romantic personalized anecdotal book Men of Mathematics to nurse an ambition to solve the problem Fermat's Last Theorem is in itself an index of the power which a certain view of the history of mathematics can exercise.

On page 413 of Combinatorics and Number Theory of Counting Sequences, the author provides a table of the initial Bell numbers. This is shown in Figure 5:

Figure 5: the initial Bell numbers