# A The Last Occurrence of any Greatest Prime Factor

Tags:
1. Jul 13, 2018

### DuckAmuck

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. Jul 13, 2018

### 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.

3. Jul 13, 2018

### DuckAmuck

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?

4. Jul 13, 2018

### 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.

5. Jul 13, 2018

### DuckAmuck

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).

6. Jul 13, 2018

### 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.

7. Jul 13, 2018

### 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
8. Jul 13, 2018

### 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.