Does doubling the sum of prime factors always lead to 16?

[thegreatjared]

Here is the process:

For example, take 28. Its prime factors (taken with multiplicity) are 2, 2, and 7. The sum of these is 11. Double it and you get 22. So, the sum of prime factors of 28 multiplied by 2 is 22. Repeat this process until you reach a loop or a stable number.

For 28, if you carry this process out to its conclusion it yields 28-->22-->26-->30-->20-->18-->16-->16-->…

As you can see, when you reach 16, the process remains "stuck." My question is this: Will any number, n, always reach 16 in this process, or are there perhaps loops that the process could reach, as well?

I think it is obvious that there are no other numbers besides 16 that the process could get hung up on, but this doesn't rule out the possibility that there are loops that the process could get stuck on. Although, it is my hunch that this is not the case and that the case of repeated 16s will prove to be the only ending to any number, n, in this process.

 

[RamaWolf]

Computer evidence: for n <= 10000, all end's up with -'16'

Longest item was:

7127->14254->14258->14262->4764->808->214->218->222->84->28->22->26->30->20->18->16->16

 

[Dr. Seafood]

^ Holy ****

 

[SW VandeCarr]

^ Holy ****

So is 16 the only number where twice the sum of its prime factors is equal to itself? My intuition tells me only a relatively low number can have this property. Four is the only composite number where the sum of its prime factors is equal to itself if you ignore 1. For composites whose prime factors are a large prime and 2, twice the sum will always exceed the composite.

 

[ramsey2879]

So is 16 the only number where twice the sum of its prime factors is equal to itself? My intuition tells me only a relatively low number can have this property. Four is the only composite number where the sum of its prime factors is equal to itself if you ignore 1. For composites whose prime factors are a large prime and 2, twice the sum will always exceed the composite.

Your intuition could be wrong!

 

[SW VandeCarr]

Your intuition could be wrong!

It could be. Can you suggest another composite number where twice the sum of its prime factors is equal to the composite number, or how to find such a number? The computation done by a previous poster (RamaWolf) shows how an arbitrary series converges to 16. The series started from a four digit number, ruling out any convergence to a lower number greater than 16. Perhaps your next post might provide a little more content.

 

[rasmhop]

16 is the only ending number. RamaWolf showed that for small numbers we always end up at 16 so I will just show that we always get to a small number (we can take small to mean <485, but if we are not lazy or didn't have RamaWolf's calculations we can manually reduce to much lower numbers) and then RamaWolf's argument shows that we will then go to 16. I will also assume that our number always has a factor of 2 for except for the very first number all numbers must be even.

All numbers in this reply shall be assumed to be integers unless otherwise stated.

Let us write a -> b to denote that taking twice the sum of a's prime factors result in b. I claim that if we start with a sufficiently high a, then we have a sequence
a -> b -> c -> d
such that one of b,c,d must be either small or < a. This shows that applying our operation repeatedly at some point we end up with a small enough number that RamaWolf's calculation applies.

Lemma 1: p^e \geq pe if p >1 and e > 0.
Proof sketch: Obvious if e=1, assume e > 1. We get p^2 \geq 2p by expanding (p-1)^2 \geq 1. If p^{e-1} \geq p(e-1), then,
p^e \geq p(e-1)p \geq 2(e-1)p \geq ep
QED.

Lemma 2:
2^ap^e &gt; 4a + 2pe + 8
if a > 1 or e >1, where we assume
2^ap^e
is large. Where we take large to mean that a > 2, e > 1, or p > 7 (may need slight adjustment, but I'm pretty sure this is sufficient).

I haven't bothered doing the actual proof in strict detail. The proof gets kinda messy with several different cases, but it's not really difficult where we use the inequality 2^ap^e \geq 2ape or 2^ap^e \geq 2^ape depending on which variable we assume is large (the last inequality is used when we assume a > 2, the first in the other two cases).

Lemma 3:
Let n=p^aq^br^c be the prime factorization of n with p < q <r. Then
n &gt; 2pa+2qb+2rc+8
Proof sketch:
p^aq^br^c \geq 2p^aq^b+2r^c+8 by expanding the inequality
(p^aq^b-2)(r^c-2) \geq 12
p^aq^b &gt; p^a + q^b by the inequality (p^a -1)(q^b-1) &gt; 1
QED

Theorem:
Let n=2^a p_1^{e_1} \cdots p_n^{e_n} be the prime factorization of a large even integer where 2 &lt; p_1 &lt; p_2 &lt; \cdots &lt; p_n. Unless a=e_1=n=1, then,
n &gt; 4a + 2p_1e_1 + 2p_2e_2 + \cdots + 2p_ne_n+8
If n=0, then the inequality reads 2^a &gt; 4a+8 which is true as long as we assume a > 4. So since n > 31 this holds (n was assumed large).
If n=1, then either a=e_1=n=1 or either a > 1 or e_1 &gt;1 in which case lemma 2 applies to prove the theorem.
If n=2, then lemma 3 applies to prove the theorem.
Let us now do n > 2 by induction.
2^a p_1^{e_1} \cdots p_{n-1}^{e_{n-1}}p_n^{e_n} &gt; (4a + 2p_1e_1 + 2p_2e_2 + \cdots + 2p_{n-1}e_{n-1}+8)p_n^{e_n} \geq 4a + 2p_1e_1 + 2p_2e_2 + \cdots + 2p_{n-1}e_{n-1} + 8p_n^{e_n}
p_n is at least 5 so p_n^{e_n} \geq p_ne_n + 1 (proof similar to that of lemma 1 except base case becomes strict). Thus we get
8p_n^{e_n} \geq 8 + 8p_ne_n
which gives us
n &gt; 4a + 2p_1e_1 + 2p_2e_2 + \cdots + 2p_{n-1}e_{n-1} + 8p_n{e_n}+8
QED

This shows that if n -> m, then m is more than 8 less than n unless n is twice an odd prime. If n=2p where p is an odd prime, then either p+2 or p+4 is not prime. If p+2 is not a prime, then we get
n -> 2(p+2) -> m
where m is more than 8 less than 2p+4, so m < n. On the other hand if p+2 is a prime, then,
n -> 2(p+2) -> 2(p+4) -> m
where m is more than 8 less than 2p+8 so m < n.

If n is not twice an odd prime then n -> m where m < n by the theorem.

 

[Mensanator]

Computer evidence: for n <= 10000, all end's up with -'16'

Longest item was:

7127->14254->14258->14262->4764->808->214->218->222->84->28->22->26->30->20->18->16->16

I wrote a Python program that checked out to 10,000,000. Found a sequence of
length 22: 7894631,15789266,831056,103898,103902,34644,5788,2902,2906,2910,214,218,
222,84,28,22,26,30,20,18,16.

 

[thegreatjared]

Very cool. So, the longest chain through the first 10,000 integers was 17 and then through 10,000,000 that could only be extended to 21 (I count 21, not 22). Somewhat surprising and interesting that the longest chain is lengthened so slowly, so to speak.

 

[RamaWolf]

The 'normal way in computing' for this problem is about like this:

...
66->32->20->18->16->16
67->134->138->56->26->30->20->18->16->16
68->42->24->18->16->16
69->52->34->38->42->24->18->16->16
70->28->22->26->30->20->18->16->16
71->142->146->150->30->20->18->16->16
72->24->18->16->16
73->146->150->30->20->18->16->16
74->78->36->20->18->16->16
75->26->30->20->18->16->16
76->46->50->24->18->16->16
77->36->20->18->16->16
78->36->20->18->16->16
79->158->162->28->22->26->30->20->18->16->16
...


But to understand things more clearly, it is perhaps worth, looking at this:

...
16<-18<-20<-32<-66
16<-18<-20<-30<-26<-56<-138<-134<-67
16<-18<-24<-42<-68
16<-18<-24<-42<-38<-34<-52<-69
16<-18<-20<-30<-26<-22<-28<-70
16<-18<-20<-30<-150<-146<-142<-71
16<-18<-24<-72
16<-18<-20<-30<-150<-146<-73
16<-18<-20<-36<-78<-74
16<-18<-20<-30<-26<-75
16<-18<-24<-50<-46<-76
16<-18<-20<-36<-77
16<-18<-20<-36<-78
16<-18<-20<-30<-26<-22<-28<-162<-158<-79
...


And sorted, this looks like;

...
16<-18<-20<-30<-26<-22<-28<-162
16<-18<-20<-30<-26<-22<-28<-162<-1095
16<-18<-20<-30<-26<-22<-28<-162<-1168
16<-18<-20<-30<-26<-22<-28<-162<-1168<-4039
16<-18<-20<-30<-26<-22<-28<-162<-1168<-5770
16<-18<-20<-30<-26<-22<-28<-162<-1168<-6924
16<-18<-20<-30<-26<-22<-28<-162<-1168<-7423
16<-18<-20<-30<-26<-22<-28<-162<-1314
16<-18<-20<-30<-26<-22<-28<-162<-1314<-2612
16<-18<-20<-30<-26<-22<-28<-162<-1314<-2612<-3909
16<-18<-20<-30<-26<-22<-28<-162<-1314<-2612<-6505
16<-18<-20<-30<-26<-22<-28<-162<-1314<-2612<-7806
16<-18<-20<-30<-26<-22<-28<-162<-1491
...


Have fun !

 

[Mensanator]

Very cool. So, the longest chain through the first 10,000 integers was 17 and then through 10,000,000 that could only be extended to 21 (I count 21, not 22). Somewhat surprising and interesting that the longest chain is lengthened so slowly, so to speak.

Sorry abput that. The correct count was, in fact, 22. I seemed to have omitted a number in the sequence. 7894631, 789262, 15789266, 831056, 103898,
103902, 34644, 5788, 2902,2906,2910, 214, 218, 222, 84,28,22,26, 30, 20, 18, 16

 

[Robert1986]

I haven't had much time to think about this, but we're really just finding the sum of the prime factors of n^2, right? This, to me, suggests that perfect squares are going to be involved, somehow (e.g. 16). Perhaps this has been mentioned and I haven't noticed, but I think it is worth considering.

 

[SW VandeCarr]

I haven't had much time to think about this, but we're really just finding the sum of the prime factors of n^2, right? This, to me, suggests that perfect squares are going to be involved, somehow (e.g. 16). Perhaps this has been mentioned and I haven't noticed, but I think it is worth considering.

Four is the only composite number where the sum of its prime factors (with multiplicity) is equal to the number. 16 is the only number where twice the sum of its prime factors is equal to the number. I'm not sure what you mean about perfect squares in general. Can you give an example of any other perfect squares where this is true (or in fact any other number)?

 

[Robert1986]

Well, I guess what I mean is that if S(n) is a function that maps n to the sum of its prime factors then when we double the sum of prime factors we are finding 2S(n), but this is really just S(n^2). So what I mean is that at every step (when we double the sum of the prime factors of a number) we are really just finding the sum of the prime factors of the square of that number (ie of a perfect square.) Like I said, I don't know if this can help to settle this matter. Since 16 is the only integer such that 2S(n) = n I guess we can conclude that any repeating pattern terminates in 16. But do we know that there are no infinite sequences?

 

[D H]

Lemma 1: p^e \geq pe if p >1 and e > 0.

False.

This is true if p=exp(1).
This is also true if p>exp(1) and e>1.

For 0<1<e, this is false if p>(1/e)^(1/(1-e)).

For e>1, this is false if 1<p<(1/e)^(1/(1-e)).
The upper limit will be between 1 (e→∞) and exp(1) (e→1).

 

[lpetrich]

Let's consider the problem more generally. Consider a number N equal to m * (sum of prime factors of N), or for short, m*pfsum(N)

This means that N is proportional to m, and we can simplify the problem by setting N = M*m, where M equals pfsum(M) + pfsum(m). Thus, a solution for one m gives a solution for every m with the same sum of prime factors.

Likewise, a limit cycle of N's found by iterating m*pfsum(N) can be found from a limit cycle of M's found by iterating pfsum(M) + pfsum(m). Multiply each member by m.

-

For m = 1, pfsum(m) = 0, and M is either a prime or 4. M can be any prime.
For m > 1, M is always composite.

I found solutions for pfsum(m) from 2 to 16, and here are my results for starting values <= 10,000. Solutions in {}'s are limit cycles.

pfsum(m) = 2, m = 2, M = 8
pfsum(m) = 3, m = 3, M = 9, 10
pfsum(m) = 4, m = 4, M = {11, 15, 12}, {13, 17, 21, 14}
pfsum(m) = 5, m = 5, 6, M = 12, 14, {13, 18}
pfsum(m) = 6, m = 8, 9, M = {14, 15}
pfsum(m) = 7, m = 7, 10, 12, M = 15
pfsum(m) = 8, m = 15, 16, 18, M = 16
pfsum(m) = 9, m = 14, 20, 24, 27, M = 22, {17, 26, 24, 18}
pfsum(m) = 10, m = 21, 25, 30, 32, 36, M = 18, {19, 29, 39, 26, 25, 20}
pfsum(m) = 11, m = 11, 28, 40, 45, 48, 54, M = 20, 21, 26
pfsum(m) = 12, m = 35, 42, 50, 60, 64, 72, 81, M = {22, 25}
pfsum(m) = 13, m = 13, 22, 56, 63, 75, 80, 90, 96, 108, M = {22, 26, 28, 24}, {23, 36}
pfsum(m) = 14, m = 33, 49, 70, 84, 100, 120, 128, 135, 144, 162, M = {23, 37, 51, 34, 33, 28, 25, 24}
pfsum(m) = 15, m = 26, 44, 105, 112, 125, 126, 150, 160, 180, 192, 216, 243, M = 24, 25, 34
pfsum(m) = 16, m = 39, 55, 66, 98, 140, 168, 189, 200, 225, 240, 256, 270, 288, 324, M = {25, 26, 31, 47, 63, 29, 45, 27}