Part 6:  Sum of Prime Factors of Polynomials

Linear Polynomials

It appears that iterations of the form  x → ξ(ax+b)  invariably lead to closed loops for any fixed integers a and b. For example, with any initial value of x less than 100,000, iteration of ξ(8x+1) always leads to the 23-step cycle

66  46  47  42  337  63  106  286  119  953  76  39  313 

175  470  3761  30089  367  103  24  193  111  134  66 ...

On the other hand, iteration of ξ(7x+3) always leads to one of the following two cycles

cycle #1:  30  74  521  85  38  269  66  39  30 ...

cycle #2:  92  647  118  829  2905 10171  109  385  92 ...

We can limit our attention to functions with gcd(a,b) = 1, because if x_n is a sequence of iterates under ξ(ax+b) with gcd(a,b)=c, then letting A and B denote the coprime integers a/c and b/c we have

Thus the iterates of ξ(ax+b) satisfy

If we define the shifted variable y_k = x_k − ξ(c) we can write this in the form

Since A and B are coprime, it's clear that A and Aξ(c) + B are also coprime, so every sequence x_n is just a shifted version of a sequence y_n for a function with coprime coefficients.

I've determined all the "linear-ξ loops" for b < a < 14 for initial x values less than 100. It appears that all the loops are usually encountered from just the first 10 or 20 initial values, and the rest are repetions, so this may represent all possible loops. For selected functions I've checked up to very large initial values (e.g., 100000) and found that they all lead back down to the original set of loops.

The longest loop in this range is for ξ(13x+12), which has a period of 59 and appears to be the only possible limit loop for this function. The function ξ(13x+1) has limit loops of length 7 and 56. The function ξ(13x+2) has 6 distinct limit loops of length 1, 1, 1, 1, 15, and 23.

Is it true that every linear-sopf iteration sequence is eventually periodic? Is the number of limit cycles finite for any given function?

Another set of questions about the sum of prime factors has been posed by Thomas Volet, who suggested defining the function

and he asks for the distribution of integers n such that d(n) = 0. Also, letting D(n) denote the sum of d(j) for j = 2 to n, he asks for the asymptotic behavior of D(n). The figure below shows (in blue) the value of D(n) as n ranges from 1 up to 20000.

The green line represents the cumulative number of integers n up to that point for which d(n) = 0. Notice that D(x) can be either positive or negative for x up to about 14000, but beyond that it goes positive, and apparently continues to trend upward. Interestingly, there is a last downward spike that occurs at 14858, and it brings us precisely to zero, i.e., we have D(14858) = 0, but that is the lowest it goes on that excursion, and subsequently the value is always positive.

This is confirmed by the plot below, which shows D(x) for x up to 200,000 in blue. The trend is definitly upward, although it is certainly not monotonic.

Carrying this up another order of magnitude, the plot below shows D(x) for x up to 2 million.

In all these plots the green curve represents the cumulative number of integers n such that d(n) = 0. If s(x) denotes this cumulative sum, then a plot of ln(s(x)) versus ln(x) is quite linear, as shown below.

This indicates that s(x) may asymptotically approach x^m for some value of m that is around 0.35 (although this is a very rough estimate, and doesn't account for any non-zero intercept).

Quadratic Polynomials

For any positive integer n let ξ(n) denote the sum of the (absolute values of) the prime factors of n. For example, the integer 12 has the prime factorization (2)(2)(3), so we have ξ(12) = 2 + 2 + 3 = 7. Given any quadratic polynomial f(x) = ax² + bx + c for integers a,b,c we can consider iterations of the function ξ(f(x)), focusing especially on the cycles and fixed points. However, since the value of ξ(f(x)) is greater than x for most values of x, cycles are quite rare. In fact, the only known cycles are fixed points for certain polynomials f, i.e., values of x such that ξ(f(x)) = x.

Interestingly, the quadratic f(x) = x² − x + 41 seems be distinguished in this regard. This polynomial is famous because it gives primes for many values of x, related to the fact that the discriminant is −163, which is the largest with class number = 1. It happens that ξ(x² − x + 41) − x takes on the value −609 unusally often. For these cases if we replace x with (x − 609) we have solutions of

Of course, the quadratic x² + 1217x + 370313 still has discriminant −163. The following 27 values of x satisfy this equation:

In each case the quadratic splits into 3 primes, i.e.,

Given any two of the prime factors of a solution pqr, we can substitute into this equation to get a quadratic in the third factor, from which we can infer two possible values of the third factor. One of those values will be from the original triple. If the other root of the quadratic happens to be a prime, then it gives another solution of equation (1). (Integer solutions of equations of this form are discussed in the note Arranging the Solutions of f(x+y+z) = xyz.)

Obviously if we remove the requirement for p,q,r to be primes, then equation (2) infinitely many solutions, but can it be proven that it has infinitely many solutions in prime integers p,q,r?  Also, are there solutions of (1) such that x is not the product of three primes? 

It seems clear that the polynomial with discriminant –163 has so many prime solutions because x² − x + 41 is a prime for so many small values of x, so there is some relationship between the class number of the discriminant of f(x) and the number of solutions of ξ(f(x)) = x. Is there a relation between the period of cycles of ξ(f(x)) and the class number of the discriminant of f(x)?

Cycles of the iteration x → ξ(f(x))with periods greater than one are quite rare (if they exist at all), because ξ(f(x)) is so often larger than x. To produce a richer periodic structure, we can apply the ξ operator twice, i.e., we can consider functions of the form ξ(ξ(f(x))). These seem to yield cycles similar to those produced by apply the ξ operator just once to linear functions.

To illustrate, consider the iterations of  ξ(ξ(x² − x + 1)). In addition to the fixed points x = 1, x = 11, and x = 20, this function gives several periodic sequences of length greater than 1. For example, beginning with x = 2, we get the sequence

In other words, after twenty-two iterations, the sequence enters into a periodic cycle of length eleven. If we begin with x = 6, the subsequent sequence is 6, 31, 14,..., so this too leads to the cycle of length eleven. On the other hand, beginning with x = 4 we get

so this leads to a cycle of length three. We also have the cycles {49, 99} and {42, 1723, 119}. In summary, this function has the seven limit cycles

It seems that every initial value leads eventually to one of these cycles. For example, beginning with x = 17 we have

so this leads to the fixed point x = 11.

For another illustration, consider the iterations of  ξ(ξ(x² − x − 1)). This function has the fixed points {8}, {43}, {53}, {1619}, and the cycles shown below.

Applying this iterative function beginning with any integer less than 100, we eventually arrive at one of these fixed points or limit cycles, although it can take quite a few iterations. For example, beginning with x = 23, the iteration gives the values

Also, the iteration can pass through some very large values before reaching its limit cycle. For example, beginning with x = 92, the iteration passes through

2874700183441905088136471841546421149589

which factors as

(61)(13432819)(3991388853449)(878964871713667979)

Ultimately this leads back down to the fixed point 53.

Return to Table of Contents