What is the significance of the sopfr function in these cycles?

[erszega]

I posted this in another math forum, but have received no response:

Let sopfr(n) be the sum of prime factors of n (see http://mathworld.wolfram.com/SumofPrimeFactors.html ).
There have been observations that certain iterations involving the sopfr function seem to lead invariably to cycles, or closed loops (see for instance http://www.mathpages.com/home/kmath006/part6/part6.htm ).

I looked at iterations of the form F(n)=sopfr(F(n-1)+F(n-2)), where F(1) and F(2) are any positive integers. These sequences also appear to end in repeating cycles sooner or later, in fact I have found the following four cycles (of length 1, 4, 5, and 13):

8 (eg F(1) = 1, F(2) = 9, F(n) = sopfr(F(n-1)+F(n-2))
10,14,9,23 (eg F(1) = 1, F(2) = 12, F(n) = sopfr(F(n-1)+F(n-2))
10,10,9,19,11 (eg F(1) = 1, F(2) = 1, F(n) = sopfr(F(n-1)+F(n-2))
39,43,43,45,17,33,12,11,23,19,12,31,43.

Interestingly, there seem to be similar results when taking the sum of prime factors of more than two preceding terms. For instance, with
F(n)=sopfr(F(n-1)+F(n-2)+F(n-3)+F(n-4)+F(n-5)), a possible cycle is one that has a length of 31196 terms. You can start that cycle with, for instance,
49,93,435,98,92.

With F(n)=sopfr(F(n-1)+...+F(n-7)), a possible cycle has a length of 28274564 (if my computation was right).

Again similar results can be obtained by checking sequences of the type F(n) = sopfr(F(n-1)*F(n-2)) = sopfr(F(n-1)) + sopfr(F(n-2)), and so on.

Is there a proof that these sequences should always end in a cycle?

 

[ramsey2879]

I looked at iterations of the form F(n)=sopfr(F(n-1)+F(n-2)), where F(1) and F(2) are any positive integers. These sequences also appear to end in repeating cycles sooner or later, in fact I have found the following four cycles (of length 1, 4, 5, and 13):

8 (eg F(1) = 1, F(2) = 9, F(n) = sopfr(F(n-1)+F(n-2))
10,14,9,23 (eg F(1) = 1, F(2) = 12, F(n) = sopfr(F(n-1)+F(n-2))
10,10,9,19,11 (eg F(1) = 1, F(2) = 1, F(n) = sopfr(F(n-1)+F(n-2))
39,43,43,45,17,33,12,11,23,19,12,31,43.

Interestingly, there seem to be similar results when taking the sum of prime factors of more than two preceding terms. For instance, with
F(n)=sopfr(F(n-1)+F(n-2)+F(n-3)+F(n-4)+F(n-5)), a possible cycle is one that has a length of 31196 terms. You can start that cycle with, for instance,
49,93,435,98,92.

With F(n)=sopfr(F(n-1)+...+F(n-7)), a possible cycle has a length of 28274564 (if my computation was right).

Again similar results can be obtained by checking sequences of the type F(n) = sopfr(F(n-1)*F(n-2)) = sopfr(F(n-1)) + sopfr(F(n-2)), and so on.

Is there a proof that these sequences should always end in a cycle?

Some questions
1) for the sequence F(n) = sopfr(F(n-1) + F(n-2)) you state that you found 4 cycles. Why have you listed only the 4 cycles that you did. How far did you search? Shouldn't other cycles exist since you can include very high starting terms, or do you find that these too end up with the ending being one of the 4 listed cycles (unless of course you start with a prime which obviously has a cycle length of 1 from the very start).

2) for the sequence F(n) = sopfr(F(n-1) + F(n-2) + ... F(n-5)) you state that a "possible cycle" has a length of 31196 terms for the starting terms 49,93,435,98,92. Shouldn't you be able to provide the exact cycle length?

3) for the sequence F(n) = sopfr(F(n-1) +F(n-2) + ... F(n-7)) you state "With F(n)=sopfr(F(n-1)+...+F(n-7)), a possible cycle has a length of 28274564 (if my computation was right)." Do you have another set of starting terms in mind for this cycle length? If so what is it? If not, how did you arrive at this number?

 

[erszega]

The reason I posted this is just that I am curious to find out if this sort of iteration of the sopfr function necessarily leads to cycles.

1) I just wanted to provide examples.
By the way, a very simple example: sopfr(8+8) = 8, and so the cycle length is simply 1.

Another example:
start the sequence with 9,19;
sopfr(9+19) = 11
sopfr(19+11)=10
sopfr(11+10)=10
sopfr(10+10)=9
sopfr(10+9)=19, that is we have

9,19,11,10,10,9,19,..., and so obviously we have a cycle consisting of the terms 9,19,11,10,10, of length 5.

I did this some time ago. I am not a mathematician, neither do I have much time for this. I found those 4 cycles, and I have no idea whether other cycles also exist when you start the sequence with two terms.

2) By "possible cycle" I meant that possibly there are other cycles as well, although I don't know. Whether or not I should provide the exact cycle length, I actually did it: 31196. To check whether I am right, the following sequence needs to be constructed, starting with 49,93,435,98,92, and then:
sopfr(49+93+435+98+92) = 72,
sopfr(93+435+98+92+72) = 86,
sopfr(435+98+92+72+86) = 38,
etc.

3) Try with starting terms (in this order) 294, 1594, 760, 57, 937, 69739, 13716, and then iterate with the above method (taking the sum of the prime factors of the sum of the previous 7 terms to calculate the new term). If I am right (I may not be) then the starting seven term sequence will again appear right after the 28274564th term. Be prepared to calculate sopfr for relatively larger numbers: the maximum value of a term in that cycle is 309782951 (if I am right).

Thank you for your interest. You are the first person to make a comment on this in a public math forum.

 

[erszega]

Just to say that these cycles are like "attractors".
For instance, a sequence of type F(n) = sopfr(F(n-1)+F(n-2)) seems to get trapped in one of the four cycles I described in my first post, whatever the first two terms (although I admit I tested only a very small range). Eg:

20000, 20000, 32, 325, 27, 21, 11, 10, and

11, 10 already starts the cycle 11, 10, 10, 9, 19.

Is there a method to determine which "attractor" the sequence will end in without going through the sequence leading up to the cycle step by step?
Are there sequences "escaping" the attractors, with terms growing beyond any limit?

Another interesting point is the distribution of the values of the terms in such a sequence. Eg, for F(n) = sopfr(F(n-1)+F(n-2)+F(n-3)+F(n-4)+F(n-5)), it is worth plotting the (x,y) pairs on a graph, where x = the value of a term in the sequence (say, within the 31196 term cycle I referred to above), and y = the number of occurences of x within the sequence. I tried to attach a .pdf file with such a graph but I couldn't. I received similar patterns when 4 or 5 or 6 or 7 preceding terms determine the value of the next term. They seem to follow a "power law", by looking at the graph.

For instance, for my example of the 31196 term cycle, the value 21 occurs 414 times, the value 22 occurs 371 times, etc. Any term value > 18293 occurs only once, but there are only 94 terms with a value > 18293, the maximum value being 148997. Sorry if this is not a very useful description, I wish I could attach that .pdf file...

 

[shmoe]

I set my computer running and for your points in post #3:

1) looking at starting values F(1) and F(2) between 1 and 1000, all ended up in one of those 4 cycles.

2) This was easy enough to confirm.

3) Confirmed the cycle length, but didn't bother to keep track of the largest number appearing, what you said was 309782951.

I haven't bothered to muck around much, how did you get the cycles in 2 and 3? I assume you started with some smaller initial values and ran until you hit those cycles, but did you try other start values?

I don't see any obvious way of proving you'd always hit a cycle, though I haven't given it much thought. This could very easily turn out to be extremely difficult to prove if it's even true.

 

[ramsey2879]

Thanks to Shmoe, we have confirm that for 1,000,000 different initial starting possibilities (i.e. for F(1), F(2) each ranging from 1 to 1,000) the sequence F(n) = sopfr(F(n-1) + F(n-2)) always end up with one of the four cycles listed by Erszega. However I don't see any way to prove that this result holds no matter what values, however large, that the initial starting terms take. To gain more knowledge on this subject one might try grouping the possible starting pairs into each of the four possible categories to see if any patterns can be observed.

 

[erszega]

I am not sure if this can lead to any insights, but there seems to be something like a "power law" behind these cycles.
For instance, taking the cycle that F(n)=sopfr(F(n-1)+F(n-2)+F(n-3)+F(n-4)+F(n-5)) (often or always??) leads to (cycle length: 31196, take initial values 49,93,435,98,92, for instance), there are
1085 different numbers that occur once,
361 different numbers that occur twice,
198 different numbers that occur 3 times,
105 different numbers that occur 4 times, etc,
although the "power-law nature" gets lost as we continue.

Further, if we take the 1085 different numbers that occur only once in the cycle, sort them, and put a graph on the sorted list of the numbers, we get an "exponential-looking" curve. Similarly for the sorted lists of numbers that occur 2, 3, 4, etc times, although the curve looks more and more random as there are fewer numbers in the sorted list.

Sorry if the above description is amateurish, but I just wonder if this might lead anywhere.

 

[erszega]

This property seems to hold not only for cycles but for any sequence of such iterations if they are long enough without repititive cycles.
Something similar as a power law also appears when the size of the numbers and their frequency is analysed.
As an example, I looked at 65535 numbers in a sequence generated by F(n) =sopfr(F(n-1)+F(n-2)+ ... + F(n-6)), and found the following (left hand column: range of numbers; right hand column: frequency, the number of occurances of the numbers in a range):

0 to 1000 51644
1001 to 2000 5232
2001 to 3000 2389
3001 to 4000 1322
4001 to 5000 897
5001 to 6000 591
6001 to 7000 485
etc

 

[ramsey2879]

I posted this in another math forum, but have received no response:

Let sopfr(n) be the sum of prime factors of n (see http://mathworld.wolfram.com/SumofPrimeFactors.html ).
There have been observations that certain iterations involving the sopfr function seem to lead invariably to cycles, or closed loops (see for instance http://www.mathpages.com/home/kmath006/part6/part6.htm ).

I looked at iterations of the form F(n)=sopfr(F(n-1)+F(n-2)), where F(1) and F(2) are any positive integers. These sequences also appear to end in repeating cycles sooner or later, in fact I have found the following four cycles (of length 1, 4, 5, and 13):

8 (eg F(1) = 1, F(2) = 9, F(n) = sopfr(F(n-1)+F(n-2))
10,14,9,23 (eg F(1) = 1, F(2) = 12, F(n) = sopfr(F(n-1)+F(n-2))
10,10,9,19,11 (eg F(1) = 1, F(2) = 1, F(n) = sopfr(F(n-1)+F(n-2))
39,43,43,45,17,33,12,11,23,19,12,31,43.

It is intersting that out of 1,000,000 distinct sequences tried by Shmoe that one the above 4 cyclic combinations always appeared. You gave starting combinations for each of the 4 cycles except the 4th. In each of these, the first number is 1. An obvious challange is to find a starting combination including 1 as the first term for 39,43,43,45,17,33,12,11,23,19,12,31,43 and also to find starting combination of 1 and an integer for cyclic permutations such as (1,13) for 10,9,19,11,10 ... .
Also, it remains unshown whether there can never be a sequence that goes on infinitely without ending in a cyclic period or that these 4 cyclic periods or a cyclic permutation thereof are the only ones possible.

 

[ramsey2879]

It is intersting that out of 1,000,000 distinct sequences tried by Shmoe that one the above 4 cyclic combinations always appeared. You gave starting combinations for each of the 4 cycles except the 4th. In each of these, the first number is 1. An obvious challange is to find a starting combination including 1 as the first term for 39,43,43,45,17,33,12,11,23,19,12,31,43 and also to find starting combination of 1 and an integer for cyclic permutations such as (1,13) for 10,9,19,11,10 ... .
Also, it remains unshown whether there can never be a sequence that goes on infinitely without ending in a cyclic period or that these 4 cyclic periods or a cyclic permutation thereof are the only ones possible.

In another forum the following was posted in response to the above:
Starting with 1 and 65 gives the 13 cycle:

1,65,16,12,11,23,19,...

I also verified that all sequences terminate in one of those four
cycles for starting values of either number up to 100000.
The reason that all sequences terminate in only four chains can
probably be understood probabilistically somehow. The sopfr(N)
function has a strong downward bias for large values of N: it seems
the mean value of sopfr(n)/n is roughly between 1/ln(n) and 2/ln(n).
For large values of n it would be unlikely for a sequence to repeat
in only a few terms, but the magnitudes of the terms go down so fast
they don't have a chance to form long chains.

I tried replacing the sopfr function by functions with similar
probability distributions to see what would happen. One of the
simplest was just replacing sopfr(x) by sopfr(x+1). In that case all
sequences terminated in only one of two chains (of lengths 1 and 3
respectively);

10,10,...
20,25,25,20,25,25,...

I also tried replacing sopfr(n) with an artificial function created
using a random (Poisson) distribution with mean n/ln(n) and that
seemed to lead to a finite number terminating cycles also (the number
of distinct terminating cycles varied between 5 and 10 or so).