Conjecture - no natural number $k$ exists such that:

  1. $P$ is the sequence of all primes starting from the $k$th prime

  2. $A$ is a sequence of natural numbers such that:

    • $\forall n : A_n<P_n<A_{n+1}$

    • $\forall n : F(A_n) \leq F(A_{n+1})$, where $F(x)$ is the number of primes in the factorization of $x$

Take $k=3$ for example:

  • $P=5,7,11,13,17,19,\dots$
  • Here, because of $11$ and $13$, we must use $12 \in A$
  • Then, because $F(12)=3$, we must use $16 \in A$
  • Then, because of $17$ and $19$, we must use $18 \in A$
  • But $F(18)<F(16)$, so we are unable to define $A$

How can I go about proving this conjecture?

The only lead I have on it, is that the sequence $A$ must include the "mid value" of every pair of twin primes (starting from the $k$th prime).


As a side note, I should mention that the motivation behind this, is an interest in finding a general definition for a sequence of natural numbers, such that between every two consecutive elements there exists exactly one prime number. So any insights or notions on this issue will also be appreciated...

  • $\begingroup$ This should follow from the (first) Hardy-Littlewood Conjecture. mathworld.wolfram.com/k-TupleConjecture.html I think the distribution of prime 4-tuples should be enough. $\endgroup$ – Tony Huynh Jun 1 '14 at 17:05
  • $\begingroup$ One sequence of natural number with the right property is $A_n=P_n-1$. $\endgroup$ – Anthony Quas Jun 1 '14 at 17:36
  • $\begingroup$ @AnthonyQuas, I think the OP wants the number of prime factors of $A_n$ (counting multiplicities) to be monotone, so that won't work. $\endgroup$ – Tony Huynh Jun 1 '14 at 17:43
  • $\begingroup$ @AnthonyQuas: Not so true. Take $59$ for example. $59-1=58$, so $58 \in A$. Now, $58$ is the product $2$ prime factors, so all the elements in $A$ prior to $58$ must also be the product of $2$ prime factors at most. As in the example I gave, this is impossible if you start the sequence $P$ at a low value. $\endgroup$ – barak manos Jun 1 '14 at 17:54

Indeed, as Tony Huynh expects, your conjecture follows from the prime triples conjecture. That conjecture imples that there exist infinitely many $k$ such that $k,6k-1,6k+1$ are all prime, and infinitely many $m$ such that $12m-1,12m+1$ are both prime. Whenever $P_n$ is one of these $6k+1$ primes, you're forced to take $A_n = 6k$, so $F(A_n)=3$; similarly, whenever $P_n$ is one of the $12m+1$ primes, we have $F(A_n) = F(12m) \ge 4$.

| cite | improve this answer | |
  • $\begingroup$ Thanks, but I don't understand the statement "Whenever $P_n$ is one of these $6k+1$ primes, you're forced to take $A_n=6k$". For example, let $P_n=79=6\cdot13+1$. You're suggesting that I must take $A_n=78$, but according to my definition, I can take $A_n$ to be any of the following numbers - $74,75,76,77,78$. Your suggestion holds only when $P_n$ is one of two twin primes. $\endgroup$ – barak manos Jun 2 '14 at 4:46
  • $\begingroup$ Right: I said "whenever $P_n$ is one of these $6k+1$ primes", meaning corresponding to a $k$ for which $k,6k-1,6k+1$ are all prime as in the prior sentence. $\endgroup$ – Greg Martin Jun 2 '14 at 4:58
  • $\begingroup$ Hmmmm... I assume that the conjecture you state in your answer has not been proved, otherwise it would imply that there are an infinite number of pairs of twin primes (which I know for sure has not been proved)... right? $\endgroup$ – barak manos Jun 2 '14 at 6:13
  • $\begingroup$ yep that's right $\endgroup$ – Greg Martin Jun 2 '14 at 8:24

I'd guess that there are infinitely many pairs $(p,p+2)$ of twin primes such that $p+1$ has four prime factors (or at least that this can't be ruled out even on heuristic grounds) but that sometimes there are more than four.

There is no proof that there are infinitely many twin primes, but there is every reason to expect that there are and even that the $k$th pair grows something like $k \log^2(k)$. Certainly for such a pair $p+1$ will be a multiple of $6$ .

I checked the last 100 out of 100000 twin prime pairs from the OEIS and found the number of prime factors to be $[[3, 7], [4, 48], [5, 34], [6, 9], [7, 2]]$.

The last two cases are $18408750=2\cdot 3 \cdot 5^4 \cdot 4904$ and $18408990=2 \cdot 3 \cdot 5 \cdot 613633.$

As I was typing this it was posted that it follows from a reasonable conjecture that three happens infinitely often. I still like having these examples around $18,000,000.$

| cite | improve this answer | |
  • $\begingroup$ Thanks. Indeed, if there was a proof that there are infinitely many twin primes $p,p+2$ such that $p+1$ is a product of at most $4$ primes (or in fact, any constant number of primes), then proving my conjecture would be trivial, since we must use $p+1 \in A$ (as I mentioned in the example). But to the best of my knowledge, there is no proof even for the fact that there are infinitely many twin primes. $\endgroup$ – barak manos Jun 2 '14 at 4:50
  • $\begingroup$ There is indeed no proof that there are infinitely many twin primes, but it is widely believed that much much more than that is true. $\endgroup$ – Aaron Meyerowitz Jun 2 '14 at 7:28

You can see below an argument that $A_n$ can't have a strictly increasing number of prime divisors. I like it but it was the result of not reading the question carefully. However I still wonder how your question advances your goal.

All I have to add is an observation and computation. The observation is that the (or at least a) main problem seems to be with twin primes. There is no proof that there are infinitely many, but no one doubts it. Then there is some fluctuation in the number of prime divisors of the one number between the two primes.

I somewhat arbitrarily looked] at the next $5000$ primes after $200,000,000.$ If $p_1,p_2,P_3$ are three consecutive primes and every integer in $[p_1+1,p_2-1$ has more prime divisors then anything in $[p_2+1,p_3-1]$ then there will be an immediate obstacle to starting the $A$ sequence before $p_2.$ I found $70$ cases where that happened. all of them were for $p1,p2$ a twin prime pair. There were $326$ such pairs.

A typical example is $200085887, [10], 200085889, [3, 3, 3, 3, 4, 3, 5, 4, 3, 3, 7, 2, 3, 6, 7, 3, 4, 4, 5, 4, 4, 2, 8, 3, 4,$$ 4, 3, 3, 5, 4, 8, 4, 3, 3, 5, 5, 3, 2, 5, 2, 7, 2, 3, 3, 3, 5, 8, 3, 3, 3, 4, 3, 5, 2, 4, 4, 3, 2, 6, 3, 4, 3, \mathbf{9}, 2, 5, 3, 5, 6, 2, 2, 8]$

This means that between the two primes indicated there is one integer and it has $10$ prime factors (with repetition) . Even though it is a pretty long way to the next prime, none of the integers in that range have more than $9$ prime factors.

OLD ANSWER Suppose merely that $P$ is the sequence of primes starting with the $k$th and that $A$ is a sequence of integers such that $A_m$ has at least $m$ prime factors. Then $A_m \ge 2^m.$ The primes grow much more slowly so, no matter how large $k$ is, $P_n \lt A_{n+1}$ will quickly be impossible.

The $j$th prime $p_j$ is roughly $j \ln{j}.$ Here is a reference for the claim $p_j \lt j(\ln{j}+\ln\ln{j}-9.4)$ for $j \ge 15985.$

A weak but absolute bound which will suffice is that $p_j<1.2^j$ for $j \ge 26.$ This follows from the facts that $p_{26}=101 \lt 1.2^{26} \approx 114$ and that there is always a prime between $x$ and $\frac{6}{5}x$ for $x \ge 26$.

So that is a proof for the question asked. It is not clear to me how this advances the goal of finding a sequence " such that between every two consecutive elements there exists exactly one prime number"

There are such sequences such as $A_n=p_{k+n}+1$. But, as you suspect, none with the number of prime divisors increasing.

It also seems unpromising to have any formula which does not reference the primes. There are many open questions such as this one form 1882 about $\pi(x)$, the number of primes less than $x$. So we shouldn't expect to be able to answer the corresponding questions for a sequence $A_n.$

| cite | improve this answer | |
  • $\begingroup$ Thanks, but I don't understand why have you decided that $A_m$ (which is the $m$th element in the sequence) must be the product of $m$ primes. There is no such restriction in my question, and in fact, in any sequence $A$ that I attempt to build, the $m$th element in the sequence is the product of much less than $m$ primes. $\endgroup$ – barak manos Jun 3 '14 at 8:11
  • $\begingroup$ Sorry, sloppy reading on my part. $\endgroup$ – Aaron Meyerowitz Jun 3 '14 at 10:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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