1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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