Wednesday, 2 July 2025

Prime Factor Sequences

I'm surprised I've not come across this type of sequence before. It has two variants and they are generated iteratively as follows:

  • number --> sum of prime factors without multiplicity
    For example, 24 with factors of 2 and 3 gives 5 and terminates after just one step

  • number --> sum of prime factors with multiplicity
    For example, 24 with factors of 2, 2, 2 and 3 gives 11 and terminates after just one step
Larger numbers of course take more than one step to terminate and it's of interest to consider those numbers that set records in term of trajectory lengths. In this context, let's consider OEIS A047830.


A047830  least number which becomes prime after exactly \(n\) iterations of f(\(x\)) = sum of prime factors of \(x\).


The members of this sequence are 4, 14, 26, 62, 134, 393, 1774, 13682, 41037 up to 100,000. The trajectories are shown in Figure 1 with length indicating the number of steps or iterations:


Figure 1: permalink

If the sum of prime factors with multiplicity is considered then we get OEIS A121360 with sequence members 1, 8, 14, 26, 62, 134, 393, 1257, 4659, 9314, 27933 up to 100,000. The trajectories are shown in Figure 2 with length indicating the number of steps or iterations:



Figure 2: permalink

The algorithms used to find the trajectories of record lengths can be easily modified to find numbers with trajectories of a specified length (number of steps or iterations). For example, how many numbers in the range up to 40000 require eight steps to reach a prime under the sum of prime factors without multiplicity algorithm. Here are the numbers (with 13682 being the first as we know already from Figure 1):

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

These numbers are the initial members of OEIS A047827. Figure 3 shows the details of their trajectories:


Figure 3: permalink

No comments:

Post a Comment