Part 6: Sum of Prime Factors of Polynomial Functions 

Sum of Prime Factors of Linear Polynomials 

It appears that iterations of the form x ® 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 x(8x+1) always leads to the 23step 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 x(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 x(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 x(ax+b) satisfy 

_{} 

If we define the shifted variable y_{k} = x_{k}  x(c) we can write this in the form 

_{} 

Since A and B are coprime, it's clear that A and Ax(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 "linearx 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 x(13x+12), which has a period of 59 and appears to be the only possible limit loop for this function. The function x(13x+1) has limit loops of length 7 and 56. The function x(13x+2) has 6 distinct limit loops of length 1, 1, 1, 1, 15, and 23. 

Is it true that every linearsopf 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 nonzero intercept). 

Sum of Prime Factors of Quadratic Polynomials 

For any positive integer n let x(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 x(12) = 2 + 2 + 3 = 7. Given any quadratic polynomial f(x) = ax^{2} + bx + c for integers a,b,c we can consider iterations of the function x(f(x)), focusing especially on the cycles and fixed points. However, since the value of x(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 x(f(x)) = x. 

Interestingly, the quadratic f(x) = x^{2}  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^{2 } 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^{2} + 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 x2  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 x(f(x)) = x. Is there a relation between the period of cycles of x(f(x)) and the class number of the discriminant of f(x)? 

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

To illustrate, consider the iterations of x(x(x^{2 } 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 twentytwo 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(x^{2 } 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. 
