Tuesday 5 March 2024

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.

No comments:

Post a Comment