Problems & Puzzles: Conjectures

Conjecture 39. Ingala's Conjecture

Salvatore Ingala sent the following conjecture:

I want to propose you a conjecture related to prime numbers. I don't know if it is a new one or it has been studied yet.

Let n > 2 be an integer and let p be his greatest prime factor; we call S(n) the set of all positive integers relatively prime to n, and we call d(n) the biggest difference between two _consecutive_ elements in S(n).

I conjecture that d(n) < 2p.

The conjecture is probably more interesting when n = 2*3*...*p, because the set S(n) is the result of the application of Erathostene's sieve deleting all multiples of 2, 3, ..., p. But it is also more difficult, because the set S(n) becomes more sparse.

I have collected the results of some computations, which could be extended; here p# means 2*3*...*p

 n   d(n)
3#    4
 5#    6
 7#   10
11#   14
13#   22
17#   26
19#   34
23#   40
29#   46
31#   58
37#   66

Question: What do you say about  this conjecture?

This conjecture was disconfirmed for several puzzlers Rudolph Knjzek, John Calligy & J. K. Andersen. Other contributions came from Dan Lima and Farideh Firoozbakht.

Knjzek wrote:

If the conjecture were true, it would proof that there is at least one prime number between two square numbers. I have tried to proof this that way some years ago without success, because I have found counterexamples. There is one of them: n=2*3*5*7.....*47

All numbers between 456854489248342153 and 456854489248342249 are not coprime to n. The difference is 96 and this is greater than 2*47=94.


You asked:
Can you show please the correspondence between this conjecture and the other
you name "there is at least one prime number between two square numbers"?
I tried to prove the conjecture "There is at least one prime number between two square numbers" this way:
Between n^2 and (n+1)^2 are 2n numbers. If one of these numbers is composite, it has at least one prime factor less or equal than n or in other words, it is not coprime to p# =2*3*5*7*....*p, if p is the greatest prime number less or equal than n. On the other hand are all numbers between n^2 and (n+1)^2 prime numbers, if they are coprime to p#, because the next prime greater p is greater than n.
If Lngala's conjecture were true, the distance of two numbers coprime to p# would be less than 2p<=2n and we could follow, that there must be at least one prime number between n^2 and (n+1)^2.
Unfortunately Ingala's conjecture doesn't hold for large values of p#.
You asked:
Can you show the smaller example you know of failure of "there is at least
one prime number between two square numbers"?
I have no counterexample for this conjecture. It is an heuristic fact, that the large composite series which disprove Ingala's conjecture appear with numbers, much greater than n^2. Therefore they don't disprove the existence of at least one prime number between two square numbers. But I don't know how I could prove this.


John Calligy wrote:

Oh, wouldn't it be nice. If true, we could prove with one stroke: 1) Bertrand's postulate; 2) Dirichlet's theorem about primes in arithmetic sequences; and 3) the conjecture that there is always a prime between n^2 and (n+1)^2.

Unfortunately, let n=
1 (mod 2)
1 (mod 3)
3 (mod 5)
3 (mod 7)
1 (mod 11)
7 (mod 13)
4 (mod 17)
10 (mod 19)
22 (mod 23)
24 (mod 29)
15 (mod 31)
26 (mod 37)
1 (mod 41)
7 (mod 43)

Then all of the numbers from n+1 to n+90 have a prime factor <= 43. n = 5766753709862113


Andersen wrote:

The conjecture is wrong. n = 43# has d(n) >= 90:
The difference between 4838684447722067 and the next S(n) number is 90.
I don't know whether 90 is optimal.

n = 199# has d(n) >= 600, so d(p#) > 3p. The first of two S(n) numbers 600 apart:

I have searched large prime gaps with a program which finds intervals with
unusually many small factors:

Using the program, I have found d(n) >= 10^7 for p=1202689.
The S(n) number has 521984 digits so it is omitted here.
It gives d(p#) > 8.3p. I don't know how large the 8.3 ratio can become.


Faride wrote:

I think d(n) depends to the number of distinct prime factors of n and also depends to this fact that if 2 or
3 divides n or not.
So d(n) doesn't depend to the largest prime factor of n.

It seems that the following table is true.
(ki>0 and p,q,r,s,t,... are prime numbers)

n d(n)
p 1
p^k (k>1) 2
p^k1*q^k2 (2<p<q) 3
2^k1*p^k2 (p>2) 4
p^k1*q^k2*r^k3 (3<p<q<r) 4
3^k1*p^k2*q^k3 (3<p<q) 5
p^k1*q^k2*r^k3*s^k4 (3<p<q<r<s) 5
2^k1*p^k2*q^k3 (2<p<q) 6
3^k1*p^k2*q^k3*r^k4 (3<p<q<r) 7
p^k1*q^k2*r^k3*s^k4*t^k5 (3<p<q<r<s<t) 7
2^k1*p^k2*q^k3*r^k4 (3<p<q<r) 8
2^k1*3^k2*p^k3*q^k4 (3<p<q) 10
2^k1*p^k2*q^k3*r^k4*s^k5 (3<p<q<r<s) 10
3^k1*p^k2*q^k3*r^k4*s^k5 (3<p<q<r<s) 11


we can extend this table.

Example: d(3^3*1087)=3

Q. Does there exist a number n such that d(n)=9?


Dan Lima wrote:

It's enough to prove the conjecture only for primordials.
For any integer n take L(n) the product of all primes that occur in n - L(n) divides n.
Then S_n is the same with S_L(n) so d(n)=d(L(n)) and both n and L(n) have the same greatest prime factor.
So it's enough to prove the conjecture only for square free integers.

For any square free n take p the greatest prime factor and p# the corresponding primordial - n divides p#.
Both n and p# have the same greatest prime factor p while S_n contains S_p#, so d(p#)>=d(n).
That's why it's enough to prove the conjecture only for primordials:

Another trivial remark is: d(p#(k))=2p(k-1) for
k=2,3,4,5,6,7,8,10,11 and d(p#(k))<2p(k-1) for k=9,12.
The following stronger conjecture might be true:
Equivalent if p(k) is the greatest prime involved in n



Records   |  Conjectures  |  Problems  |  Puzzles