MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Using the Chinese Remainder Theorem, it is very straight forward to find a sequence of consecutive integers starting at $x$ where each of the first $n$ prime numbers is a least prime factor for a given number in the sequence and no number in the sequence has a least prime factor greater than $p_n$. Trivially, we know that this first occurs for the first $n$ primes at $x=2$. For example, the first $3$ primes are least prime factors in $2,3,4,5$

Each of these sequences can be characterized by the prime ordering of least prime factors which can be represented as $$p_1:p_2:\cdots:p_n$$

A sequence with the first $4$ primes is trivially found at $x=2$ in $2,3,4,5,6,7$. In this sequence, the prime ordering of the first occurrence of least prime factors is $2:3:5:7$. The second trivial occurrence is found at $x=3$ since $3,4,5,6,7$ shows the prime ordering $3:2:5:7$ A third trivial occurrence is found at $x=4$ since $4,5,6,7,8,9$ shows the prime ordering $2:5:7:3$.

I consider these sequences as "trivial" because for $n \ge 3$, $2$ such sequences at $x=2$ and $x=3$. There are multiple of these sequences in sequential order at $y=x+i$ since if $2:p_i:p_{i+1}:\cdots$ is an ordering so is $p_i:2:p_{i+1}:\cdots$. Depending on the number of primes, the same type of pattern will work for $3$ or any other of the smaller primes. For example, if $x$ is such a sequence and has the prime ordering of $3:2:5:7$, then necessarily, $x+1$ is such a sequence and has the prime ordering of $2:5:7:3$ at $x+1$

The first nontrivial occurrence for the $7$ is found at $x=90$ since $90, 91, 92, 93, 94, 95$ shows the prime ordering of $2:7:3:5$ I consider this nontrivial because $x > p_{n+1}$. There is always a long sequence of consecutive integers where no least prime factor is greater than $p_n$ between $2$ and $p_{n+1}-1$.

I know that there's been very interesting work with Jacobthal's function that details the upper bound for this type of sequence. Iwaniec has shown that

$$ j(n) \ll (\log n)^2. $$

By $j(n)$, I mean the Jacobthal functions which is defined as (from the OEIS wiki):

The ordinary Jacobsthal function j(n) is defined as the smallest positive integer m, such that every sequence of m consecutive integers contains an integer coprime to n.

Is there any paper or work that talks about the lower bound for the first nontrivial occurrence of a sequence of consecutive integers where each of the first $n$ primes is a least prime factor of a given number in the sequence and no number in the sequence has a least prime factor greater than $p_n$? Or anything that talks about the ordering of the least prime factors in such a sequence?



Edit: I made mistake in my example. I had meant to use $x=90$ which I have fixed above. Add another example for $4$. Try to explain better what I mean by "trivial" and added a definition for $j(n)$.

share|cite|improve this question
Why use $x=84$ when $x=4$ works? – The Masked Avenger Dec 23 '13 at 16:40
Not clear to me how you distinguish trivial from non-trivial. Also, you introduce notation $j(n)$ without defining it. – Gerry Myerson Dec 23 '13 at 16:47
In fact, with 89 in your example, I think it does not work at all. You might try a formal definition along with a few more examples. – The Masked Avenger Dec 23 '13 at 16:48
Masked Avenger, you are right. It should be $x=90$. I added detail on why I consider $x=4$ as trivial. @Gerry Myerson, I added more details on distinguishing between trivial and non-trivial. Thanks for your comments! – Larry Freeman Dec 23 '13 at 17:39
up vote 2 down vote accepted

It was proved by Rankin in 1963 that there are infinitely many $n$ for which $$j(n) \geq (C+o(1) \frac{\log(n) \log_{2}(n) \log_{4}(n)}{\log^{2}_{3}(n)} $$ holds for some positive $C>0$. The value of $C$ has since been improved by Maier and Pomerance (1990) to $C=e^{\gamma} \times 1.3125...$ and Pintz (1997) to $C=2e^{\gamma}$ (where $\gamma$ is Euler's constant).

share|cite|improve this answer
Thanks very much for the reference! Would you know if there is any work which can prove a lower bound that is always true? For example, by my definition of "trivial", we know that the first nontrivial sequence for $p_n$ is found at $x > p_{n+1}$ – Larry Freeman Dec 23 '13 at 17:49
Since you need a number with LPF $p_n$, the next example is likely larger than $p_n^2$. – The Masked Avenger Dec 23 '13 at 17:57

Your conditions seem to imply a search for a confluence of a sizable prime gap in which a not very smooth number (one with least prime factor of $p_n$) occurs. You can limit the search by looking "between the totients" of P_n, the nth primorial, so a computer could find quickly some examples. However, I suspect that not much is known about the distribution of the totients of P_n; I'd be surprised if your question has been studied.

share|cite|improve this answer
In spite of my suspicions, it seems clear that you want to look mod $P_n$ at the $\phi(P_{n-1})$ many multiples of $p_n$ to find your example. You may get some nice results from this if you can show one nontrivial such sequence exists. – The Masked Avenger Dec 23 '13 at 18:07
This is becoming more interesting. Eventually, you can cut down on the number of candidates by looking at those multiples "on the edges" of large gaps between totients. You might try some numerical experiments for n=7 and 8. – The Masked Avenger Dec 23 '13 at 18:16

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.