Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Aug 11, 2011 #1
    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.
     
  2. jcsd
  3. Aug 12, 2011 #2
    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
     
  4. Aug 12, 2011 #3
    ^ Holy ****
     
  5. Aug 12, 2011 #4
    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.
     
    Last edited: Aug 12, 2011
  6. Aug 13, 2011 #5
    Your intuition could be wrong!
     
  7. Aug 13, 2011 #6
    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.
     
    Last edited: Aug 13, 2011
  8. Aug 13, 2011 #7
    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: [tex]p^e \geq pe[/tex] if p >1 and e > 0.
    Proof sketch: Obvious if e=1, assume e > 1. We get [itex]p^2 \geq 2p[/itex] by expanding [itex](p-1)^2 \geq 1[/itex]. If [itex]p^{e-1} \geq p(e-1)[/itex], then,
    [itex]p^e \geq p(e-1)p \geq 2(e-1)p \geq ep[/itex]
    QED.

    Lemma 2:
    [tex]2^ap^e > 4a + 2pe + 8[/tex]
    if a > 1 or e >1, where we assume
    [tex]2^ap^e[/tex]
    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 [itex]2^ap^e \geq 2ape[/itex] or [itex]2^ap^e \geq 2^ape[/itex] 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 [itex]n=p^aq^br^c[/itex] be the prime factorization of n with p < q <r. Then
    [tex]n > 2pa+2qb+2rc+8[/tex]
    Proof sketch:
    [itex]p^aq^br^c \geq 2p^aq^b+2r^c+8[/itex] by expanding the inequality
    [itex](p^aq^b-2)(r^c-2) \geq 12[/itex]
    [itex]p^aq^b > p^a + q^b[/itex] by the inequality [itex](p^a -1)(q^b-1) > 1[/itex]
    QED

    Theorem:
    Let [itex]n=2^a p_1^{e_1} \cdots p_n^{e_n}[/itex] be the prime factorization of a large even integer where [itex]2 < p_1 < p_2 < \cdots < p_n[/itex]. Unless [itex]a=e_1=n=1[/itex], then,
    [itex]n > 4a + 2p_1e_1 + 2p_2e_2 + \cdots + 2p_ne_n+8[/itex]
    If n=0, then the inequality reads [itex]2^a > 4a+8[/itex] 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 [itex]a=e_1=n=1[/itex] or either a > 1 or [itex]e_1 >1[/itex] 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.
    [itex]2^a p_1^{e_1} \cdots p_{n-1}^{e_{n-1}}p_n^{e_n} > (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}[/itex]
    [itex]p_n[/itex] is at least 5 so [itex]p_n^{e_n} \geq p_ne_n + 1[/itex] (proof similar to that of lemma 1 except base case becomes strict). Thus we get
    [itex]8p_n^{e_n} \geq 8 + 8p_ne_n[/itex]
    which gives us
    [itex]n > 4a + 2p_1e_1 + 2p_2e_2 + \cdots + 2p_{n-1}e_{n-1} + 8p_n{e_n}+8[/itex]
    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.
     
  9. Aug 29, 2011 #8


    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.
     
  10. Aug 29, 2011 #9
    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.
     
  11. Aug 30, 2011 #10
    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 !
     
  12. Aug 30, 2011 #11
    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
     
  13. Aug 30, 2011 #12
    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.
     
  14. Aug 30, 2011 #13
    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)?
     
    Last edited: Aug 30, 2011
  15. Aug 31, 2011 #14
    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?
     
  16. Aug 31, 2011 #15

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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).
     
    Last edited: Aug 31, 2011
  17. Sep 5, 2011 #16
    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}
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Does doubling the sum of prime factors always lead to 16?
  1. Prime factorization (Replies: 2)

  2. Sum of primes (Replies: 13)

Loading...