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

A The Last Occurrence of any Greatest Prime Factor

  1. Jul 13, 2018 #1
    If you have 2 integers n and n+1, it is easy to show that they have no shared prime factors.
    For example: the prime factors of 9 are (3,3), and the prime factors of 10 are (2,5).
    Now if we consider 9 and 10 as a pair, we can collect all their prime factors (2,3,3,5) and find the maximum, which is 5. But where is the last occurrence of 5 as the maximum prime factor between two neighboring integers? Is there a known way to compute this, or to get a bound on it?

    Essentially what I am looking for is a function that take a prime and tells me which integer n is part of the last pair of integers that have that prime as the greatest prime factor.

    n_last = f(p)
     
  2. jcsd
  3. Jul 13, 2018 #2

    fresh_42

    User Avatar
    2017 Award

    Staff: Mentor

    What do you mean exactly? Let's take 7 as an example. It's the largest prime factor in (6,7),(7,8),(14,15),(20,21),(27,28),(35,36),(48,49),(49,50), and whatever which pairs. Now are you asking about the maximal integer of all possible pairs?

    I don't think it has been investigated or that there is a formula. I'm not even sure, whether there is a maximum at all.
     
  4. Jul 13, 2018 #3
    Yes, that is correct, 7 is the largest prime factor present in the pairs (6,7),(7,8),(14,15),(20,21),(27,28),(35,36),(48,49),(49,50). But where does this stop? Is there some integer n such that factoring the pair (n,n+1) gives you the last instance of 7 being the largest prime factor?
     
  5. Jul 13, 2018 #4

    fresh_42

    User Avatar
    2017 Award

    Staff: Mentor

    I doubt it. We still could have an expression ##2^k3^m5^n\cdot 7^l - 2^{k'}3^{m'}5^{n'} = 1## with arbitrary ##k,m,n,l,k',m',n'## which is a real big number of possibilities. So unless there isn't some use of such question in number theory, I doubt that anyone has considered this question.
     
  6. Jul 13, 2018 #5
    It could become a big number of possibilities, but remember that if k > 0, then k' = 0, since n and n+1 do not share prime factors. So the number of combinations to evaluate is 2^a, where a is the number of primes below 7 (or whatever prime you are considering).
     
  7. Jul 13, 2018 #6

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    For 2 and 3 this is Catalan's conjecture - now a theorem. There are only three pairs without larger prime factors: The trivial (2,3), then (3,4) and finally (8,9). The proof was difficult and quite recent. There is a good chance that more general questions (like this) are still unsolved. You could check some small numbers or look for heuristic arguments to see if such a maximum exists at all.
     
  8. Jul 13, 2018 #7

    fresh_42

    User Avatar
    2017 Award

    Staff: Mentor

    But before you, @DuckAmuck , suggest a DuckAmuck conjecture, please make sure it isn't trivial on one hand, and solvable on the other. Will say, "Find a function" isn't a good conjecture. Better would be something like: For every ##p## there is a number ##N## such that ##p \,\mid \, N \cdot (N+1)## and ##p \,\nmid \, M \cdot (M+1)## for all ##M>N##, and all for ##q>p## : ##q\,\nmid\,N \cdot (N+1)\,.##

    And no, the pun with the margin isn't funny anymore!
     
    Last edited: Jul 13, 2018
  9. Jul 13, 2018 #8

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    That is certainly wrong as ##p \,\mid \, pM \cdot (pM+1) \forall M##. The conjecture would be:

    For every prime p there is a number N such that M(M+1) for M>N always has a prime factor larger than p.

    For p=3 we know it is true. For p=5 I checked all numbers up to 10 million. 2,3,4,5,6,9,10,16,25,81 are the only numbers where N and N-1 has no larger prime factor. So many numbers close together and then nothing for a very long time suggests this set is complete. I found it on oeis shifted by 1, and it turns out that someone called Størmer proved it is finite. But OEIS knows even more:

    Yes, there is a largest pair for every prime

    Størmer's theorem provides a way to find all these pairs.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted