The Last Occurrence of any Greatest Prime Factor

In summary: Essentially, it involves finding the solutions to a system of diophantine equations. In summary, if we have two integers n and n+1, it is possible to show that they do not share any prime factors. However, it is not known if there is a way to compute or bound the last occurrence of a prime as the maximum prime factor between two neighboring integers. This question has not been investigated in number theory and there is no known formula for it. There is a conjecture that for every prime p, there exists a number N such that the pairs (N,N+1) and (N+1,N+2) have a prime factor larger than p. This conjecture has been proven for p=3 and p=5
  • #1
DuckAmuck
238
40
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)
 
Mathematics news on Phys.org
  • #2
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
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
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.
 
  • Like
Likes QuantumQuest and DuckAmuck
  • #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).
 
  • #6
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.
 
  • Like
Likes QuantumQuest and DuckAmuck
  • #7
mfb said:
There is a good chance that more general questions (like this) are still unsolved.
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:
  • #8
fresh_42 said:
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\,.##
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.
 
  • Like
Likes fresh_42

Related to The Last Occurrence of any Greatest Prime Factor

1. What is "The Last Occurrence of any Greatest Prime Factor"?

"The Last Occurrence of any Greatest Prime Factor" is a mathematical concept that refers to the largest prime number that appears in a given series of numbers. It is the last time that a prime number occurs in that particular series.

2. How is "The Last Occurrence of any Greatest Prime Factor" calculated?

The calculation for "The Last Occurrence of any Greatest Prime Factor" involves finding the prime factors of each number in the given series and then identifying the largest prime number among them. This process is repeated until the end of the series is reached, and the last occurrence of the greatest prime factor is determined.

3. What is the significance of "The Last Occurrence of any Greatest Prime Factor"?

"The Last Occurrence of any Greatest Prime Factor" is significant because it helps identify the largest prime number in a series, which can have implications in various fields of mathematics, including number theory and cryptography.

4. Can "The Last Occurrence of any Greatest Prime Factor" be used to find prime numbers?

Yes, "The Last Occurrence of any Greatest Prime Factor" can be used to identify and locate prime numbers in a given series. By finding the largest prime factor in a series, we can determine if a number is prime or not.

5. Is there a formula or algorithm for calculating "The Last Occurrence of any Greatest Prime Factor"?

Yes, there are various algorithms and formulas that can be used to calculate "The Last Occurrence of any Greatest Prime Factor". These include the Sieve of Eratosthenes, Pollard's rho algorithm, and the quadratic sieve method, among others.

Similar threads

Replies
1
Views
889
Replies
1
Views
1K
Replies
13
Views
1K
Replies
4
Views
1K
Replies
35
Views
3K
  • General Math
Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
Replies
9
Views
1K
Replies
9
Views
2K
Replies
43
Views
5K
Back
Top